Misplaced Pages

Resistance distance

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Graph metric of electrical resistance between nodes

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 , {\displaystyle \Omega _{i,j}:=\Gamma _{i,i}+\Gamma _{j,j}-\Gamma _{i,j}-\Gamma _{j,i},}
where Γ = ( L + 1 | V | Φ ) + , {\displaystyle \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| × |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 {\displaystyle \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×N matrix M:

∑ i , j ∈ V ( L M L ) i , j Ω i , j = − 2 tr ⁡ ( M L ) {\displaystyle \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;

∑ ( i , j ) ∈ E Ω i , j = N − 1 ∑ i < j ∈ V Ω i , j = N ∑ k = 1 N − 1 λ k − 1 {\displaystyle {\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

∑ i < j Ω i , j {\displaystyle \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:

Ω i , j = { | { t : t ∈ T , e i , j ∈ t } | | T | , ( i , j ) ∈ E | T ′ − T | | T | , ( i , j ) ∉ E {\displaystyle \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 + ei,j). In other words, for an edge ( i , j ) ∈ E {\displaystyle (i,j)\in E} , the resistance distance between a pair of nodes i {\displaystyle i} and j {\displaystyle j} is the probability that the edge ( i , j ) {\displaystyle (i,j)} is in a random spanning tree of G {\displaystyle G} .

Relationship to random walks

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

As a squared Euclidean distance

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

( L + 1 | V | Φ ) , {\displaystyle \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 Γ = K K T {\displaystyle \Gamma =KK^{\textsf {T}}} and we can write:

Ω i , j = Γ i , i + Γ j , j − Γ i , j − Γ j , i = K i K i T + K j K j T − K i K j T − K j K i T = ( K i − K j ) 2 {\displaystyle \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, …, 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

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

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

See also

References

  1. "Resistance Distance".
  2. Chandra, Ashok K and Raghavan, Prabhakar and Ruzzo, Walter L and Smolensky, Roman (1989). "The electrical resistance of a graph captures its commute and cover times". Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89. pp. 574–685. doi:10.1145/73007.73062. ISBN 0897913078.{{cite book}}: CS1 maint: multiple names: authors list (link)
  3. Bapat, R. B.; Gupta, Somit (2010). "Resistance distance in wheels and fans" (PDF). Indian Journal of Pure and Applied Mathematics. 41 (1): 1–13. doi:10.1007/s13226-010-0004-2. MR 2650096.
Categories:
Resistance distance Add topic