Evaluation of Effective Resistances in Pseudo-Distance-Regular Resistor Networks

摘要

The effective resistance or two-point resistance between two nodes of a resistor network is the potential difference that appears across them when a unit current source is applied between the nodes as terminals. This concept arises in problems which deal with graphs as electrical networks including random walks, distributed detection and estimation, sensor networks, distributed clock synchronization, collaborative filtering, clustering algorithms and etc. In the previous paper (Jafarizadeh et al. in J. Math. Phys. 50: 023302, 2009) a recursive formula for evaluation of effective resistances on the so-called distance-regular networks was given based on the Christoffel-Darboux identity. In this paper, we consider more general networks called pseudo-distance-regular networks or QD type networks, where we use the stratification of these networks and show that the effective resistances between a given node, say alpha, and all of the nodes beta belonging to the same stratum with respect to a, are the same. Then, based on the spectral techniques, for those alpha, beta's which satisfy L-alpha alpha(-1) = L-beta beta(-1) (L-1 is the pseudo-inverse of the Laplacian of the network), an analytical formula for effective resistances R-alpha beta(m) (the equivalent resistance between terminals alpha and beta, so that beta belongs to the m-th stratum with respect to alpha) is given in terms of the first and second orthogonal polynomials associated with the network. From the fact that in distance-regular networks, L-alpha alpha(-1) = L-beta beta(-1) is satisfied for all nodes alpha, beta of the network, the effective resistances R-alpha beta(m) for m = 1, 2,..., d (d is diameter of the network which is the same as the number of strata) are calculated directly, by using the given formula.