Resistance distance

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

Definition

On a graph Template:Mvar, the resistance distance Ω_i,j between two vertices Template:Mvar and Template:Mvar is

${\mathrm{\Omega }}_{i,j}:={\mathrm{\Gamma }}_{i,i}+{\mathrm{\Gamma }}_{j,j}-{\mathrm{\Gamma }}_{i,j}-{\mathrm{\Gamma }}_{j,i},$

where $\mathrm{\Gamma }={(L+\frac{1}{|V|}\mathrm{\Phi })}^{+},$

with ⁺ denotes the Moore–Penrose inverse, Template:Mvar the Laplacian matrix of Template:Mvar, Template:Abs is the number of vertices in Template:Mvar, and Φ is the Template:Abs × Template:Abs matrix containing all 1s.

Properties of resistance distance

If i = j then Ω_i,j = 0. For an undirected graph

${\mathrm{\Omega }}_{i,j}={\mathrm{\Omega }}_{j,i}={\mathrm{\Gamma }}_{i,i}+{\mathrm{\Gamma }}_{j,j}-2{\mathrm{\Gamma }}_{i,j}$

General sum rule

For any Template:Mvar-vertex simple connected graph G = (V, E) and arbitrary N×N matrix Template:Mvar:

$\sum _{i,j\in V}(LML{)}_{i,j}{\mathrm{\Omega }}_{i,j}=-2\mathrm{tr}(ML)$

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

$\begin{array}{rl}\sum _{(i,j)\in E}{\mathrm{\Omega }}_{i,j}& =N-1\\ \sum _{i<j\in V}{\mathrm{\Omega }}_{i,j}& =N\sum _{k=1}^{N-1}{\lambda }_k^{-1}\end{array}$

where the Template:Mvar are the non-zero eigenvalues of the Laplacian matrix. This unordered sum

$\sum _{i<j}{\mathrm{\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, Template:Mvar, of Template:Mvar as follows:

${\mathrm{\Omega }}_{i,j}=\{\begin{array}{ll}\frac{|\{t:t\in T,e_{i,j}\in t\}|}{\left|T\right|},& (i,j)\in E\\ \frac{|T^{\prime }-T|}{\left|T\right|},& (i,j)\in ̸E\end{array}$

where Template:Mvar 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{\mathrm{\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}{\mathrm{deg}(u){\mathrm{\Omega }}_{u,v}},$

where $\mathrm{deg}(u)$ is the degree of $u$. Unlike the commute time, the escape probability is not symmetric in general, i.e., $P_{u,v}\ne P_{v,u}$.

As a squared Euclidean distance

Since the Laplacian Template:Mvar is symmetric and positive semi-definite, so is

$(L+\frac{1}{|V|}\mathrm{\Phi }),$

thus its pseudo-inverse Γ is also symmetric and positive semi-definite. Thus, there is a Template:Mvar such that $\mathrm{\Gamma }=K{K}^{\text{T}}$ and we can write:

${\mathrm{\Omega }}_{i,j}={\mathrm{\Gamma }}_{i,i}+{\mathrm{\Gamma }}_{j,j}-{\mathrm{\Gamma }}_{i,j}-{\mathrm{\Gamma }}_{j,i}=K_i{K}_i^{\text{T}}+K_j{K}_j^{\text{T}}-K_i{K}_j^{\text{T}}-K_j{K}_i^{\text{T}}={(K_i-K_j)}^2$

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

Connection with Fibonacci numbers

A fan graph is a graph on n + 1 vertices where there is an edge between vertex Template:Mvar and n + 1 for all i = 1, 2, 3, …, n, and there is an edge between vertex Template:Mvar and Template:Mvar for all i = 1, 2, 3, …, n – 1.

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 Template:Mvar is the Template:Mvar-th Fibonacci number, for j ≥ 0.

See also

• Conductance (graph)