Resistance distance

In graph theory, the resistance distance between two vertices of a simple, connected graph, $G$ , is equal to the resistance between two equivalent points on an electrical network, constructed so as to correspond to $G$ , with each edge being replaced by a resistance of one ohm. It is a metric on graphs.

On a graph $G$ , the resistance distance $Ω i, j$ between two vertices $v i$ and $v j$ is^[1]

\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$ , $| V |$ is the number of vertices in $G$ , and $Φ$ is the $| V | \times | V |$ matrix containing all 1s.

Properties of resistance distance

If $i = j$ then $Ω i, j = 0$ . 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 $G = (V, E)$ and arbitrary $N \times 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{aligned}\sum _{(i,j)\in E}\Omega _{i,j}&=N-1\\\sum _{i<j\in V}\Omega _{i,j}&=N\sum _{k=1}^{N-1}\lambda _{k}^{-1}\end{aligned}}

where the $λ k$ are the non-zero eigenvalues of the Laplacian matrix. This unordered sum

\sum _{i<j}\Omega _{i,j}

is called the Kirchhoff index of the graph.

Relationship to the number of spanning trees of a graph

For a simple connected graph $G = (V, E)$ , 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 $G' = (V, E + e i, j)$ . 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}$ .^[2]

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$ .^[3] 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_{i}K_{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 $i = 1, 2, 3, \dots, n$ , and there is an edge between vertex $i$ and $i + 1$ for all $i = 1, 2, 3, \dots, n - 1$ .

The resistance distance between vertex $n + 1$ and vertex $i \in {1, 2, 3, \dots, n}$ is

{\frac {F_{2(n-i)+1}F_{2i-1}}{F_{2n}}}

where $F j$ is the $j$ -th Fibonacci number, for $j \geq 0$ .^[4]