Resistance distance

Definition

On a graph G, the resistance distance Ω between two vertices v and v is : \Omega_{i,j}:=\Gamma_{i,i}+\Gamma_{j,j}-\Gamma_{i,j}-\Gamma_{j,i}, :where \Gamma = \left(L + \frac{1}{|V|}\Phi\right)^+, with denotes the Moore–Penrose inverse, L the Laplacian matrix of G, is the number of vertices in G, and Φ is the × matrix containing all 1s.

Properties of resistance distance

If then . For an undirected graph :\Omega_{i,j}=\Omega_{j,i}=\Gamma_{i,i}+\Gamma_{j,j}-2\Gamma_{i,j}

General sum rule

For any N-vertex simple connected graph and arbitrary N×N matrix M:

:\sum_{i,j \in V}(LML){i,j}\Omega{i,j} = -2\operatorname{tr}(ML)

From this generalized sum rule a number of relationships can be derived depending on the choice of M. Two of note are;

:\begin{align} \sum_{(i,j) \in E}\Omega_{i,j} &= N - 1 \ \sum_{i \end{align}

where the λ are the non-zero eigenvalues of the Laplacian matrix. This unordered sum :\sum_{i is called the Kirchhoff index of the graph.

Relationship to the number of spanning trees of a graph

For a simple connected graph , the resistance distance between two vertices may be expressed as a function of the set of spanning trees, T, of G as follows:

: \Omega_{i,j}=\begin{cases} \frac{\left | {t:t \in T,, e_{i,j} \in t} \right \vert}{\left | T \right \vert}, & (i,j) \in E\ \frac{\left | T'-T \right \vert}{\left | T \right \vert}, &(i,j) \not \in E \end{cases}

where T' is the set of spanning trees for the graph . In other words, for an edge (i,j)\in E, the resistance distance between a pair of nodes i and j is the probability that the edge (i,j) is in a random spanning tree of G.

Relationship to random walks

The resistance distance between vertices u and v is proportional to the commute time C_{u,v} of a random walk between u and v. The commute time is the expected number of steps in a random walk that starts at u, visits v, and returns to u. For a graph with m edges, the resistance distance and commute time are related as C_{u,v}=2m\Omega_{u,v}.

Resistance distance is also related to the escape probability between two vertices. The escape probability P_{u,v} between u and v is the probability that a random walk starting at u visits v before returning to u. The escape probability equals : P_{u,v} = \frac{1}{\deg(u)\Omega_{u,v}}, where \deg(u) is the degree of u. Unlike the commute time, the escape probability is not symmetric in general, i.e., P_{u,v}\neq P_{v,u}.

As a squared Euclidean distance

Since the Laplacian L is symmetric and positive semi-definite, so is :\left(L+\frac{1}{|V|}\Phi\right), thus its pseudo-inverse Γ is also symmetric and positive semi-definite. Thus, there is a K such that \Gamma = KK^\textsf{T} and we can write:

:\Omega_{i,j} = \Gamma_{i,i} + \Gamma_{j,j} - \Gamma_{i,j} - \Gamma_{j,i} = K_iK_i^\textsf{T} + K_j K_j^\textsf{T} - K_i K_j^\textsf{T} - K_j K_i^\textsf{T} = \left(K_i - K_j\right)^2

showing that the square root of the resistance distance corresponds to the Euclidean distance in the space spanned by K.

Connection with Fibonacci numbers

A fan graph is a graph on n + 1 vertices where there is an edge between vertex i and n + 1 for all , and there is an edge between vertex i and i + 1 for all .

The resistance distance between vertex n + 1 and vertex i ∈ {1, 2, 3, …, n} is :\frac{ F_{2(n-i)+1} F_{2i-1} }{ F_{2n} } where F is the j-th Fibonacci number, for j ≥ 0.{{cite journal

References

• {{cite journal

• {{cite journal

• {{cite journal

• {{cite journal

• {{cite journal |archive-url = https://web.archive.org/web/20120326104653/http://www.stkpula.hr/ccacaa/CCA-PDF/cca2002/v75-n2/CCA_75_2002_633_649_KLEIN.pdf |archive-date = 2012-03-26

• {{cite journal

• {{cite journal

• {{cite journal

• {{cite journal

• {{cite journal |hdl-access=free

• {{cite journal

• {{cite journal

• {{cite journal |article-number=445203

References

1. "Resistance Distance".
2. (1989). "Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89".
3. (1984). "Random Walks and Electric Networks". American Mathematical Society.