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.

Definition

On a graph G, the resistance distance Ωi,j between two vertices vi and vj is

Ωi,j:=Γi,i+Γj,j−Γi,j−Γj,i,
where Γ=(L+1|V|Φ)+,

with + denotes the Moore–Penrose inverse, L the Laplacian matrix of G, |V| is the number of vertices in G, and Φ is the |V| × |V| matrix containing all 1s.

Properties of resistance distance

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

Ωi,j=Ωj,i=Γi,i+Γj,j−2Γi,j

General sum rule

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

∑i,j∈V(LML)i,jΩi,j=−2tr⁡(ML)

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

∑(i,j)∈EΩi,j=N−1∑i<j∈VΩi,j=N∑k=1N−1λk−1

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

∑i<jΩ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:

Ωi,j={|{t:t∈T,ei,j∈t}||T|,(i,j)∈E|T′−T||T|,(i,j)∉E

where T' is the set of spanning trees for the graph G' = (V, E + ei,j). In other words, for an edge (i,j)∈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 Cu,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 Cu,v=2mΩu,v.


Resistance distance is also related to the escape probability between two vertices. The escape probability Pu,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

Pu,v=1deg⁡(u)Ωu,v,

where deg⁡(u) is the degree of u. Unlike the commute time, the escape probability is not symmetric in general, i.e., Pu,v≠Pv,u.

As a squared Euclidean distance

Since the Laplacian L is symmetric and positive semi-definite, so is

(L+1|V|Φ),

thus its pseudo-inverse Γ is also symmetric and positive semi-definite. Thus, there is a K such that Γ=KK𝖳 and we can write:

Ωi,j=Γi,i+Γj,j−Γi,j−Γj,i=KiKi𝖳+KjKj𝖳−KiKj𝖳−KjKi𝖳=(Ki−Kj)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, …, n, and there is an edge between vertex i and i + 1 for all i = 1, 2, 3, …, n – 1.

The resistance distance between vertex n + 1 and vertex i ∈ {1, 2, 3, …, n} is

F2(n−i)+1F2i−1F2n

where Fj is the j-th Fibonacci number, for j ≥ 0.

See also