Resistance distance

From KYNNpedia

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<ref>"Resistance Distance".</ref>

<math>

\Omega_{i,j}:=\Gamma_{i,i}+\Gamma_{j,j}-\Gamma_{i,j}-\Gamma_{j,i}, </math>

where <math>\Gamma = \left(L + \frac{1}{|V|}\Phi\right)^+,</math>

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

<math>\Omega_{i,j}=\Omega_{j,i}=\Gamma_{i,i}+\Gamma_{j,j}-2\Gamma_{i,j}</math>

General sum rule

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

<math>\sum_{i,j \in V}(LML)_{i,j}\Omega_{i,j} = -2\operatorname{tr}(ML)</math>

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

<math>\begin{align}
 \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{align}</math>

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

<math>\sum_{i<j} \Omega_{i,j}</math>

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:

<math>

\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} </math>

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

Relationship to random walks

The resistance distance between vertices <math>u</math> and <math>u</math> is proportional to the commute time <math>C_{u,v}</math> of a random walk between <math>u</math> and <math>v</math>. The commute time is the expected number of steps in a random walk that starts at <math>u</math>, visits <math>v</math>, and returns to <math>u</math>. For a graph with <math>m</math> edges, the resistance distance and commute time are related as <math>C_{u,v}=2m\Omega_{u,v}</math>.<ref>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)</ref>

As a squared Euclidean distance

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

<math>\left(L+\frac{1}{|V|}\Phi\right),</math>

thus its pseudo-inverse Γ is also symmetric and positive semi-definite. Thus, there is a K such that <math>\Gamma = KK^\textsf{T}</math> and we can write:

<math>\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</math>

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

<math>\frac{ F_{2(n-i)+1} F_{2i-1} }{ F_{2n} }</math>

where Fj is the j-th Fibonacci number, for j ≥ 0.<ref>Bapat, R. B.; Gupta, Somit (2010). "Resistance distance in wheels and fans". Indian Journal of Pure and Applied Mathematics. 41: 1–13. CiteSeerX 10.1.1.418.7626. doi:10.1007/s13226-010-0004-2. S2CID 14807374.</ref><ref>http://www.isid.ac.in/~rbb/somitnew.pdf[bare URL PDF]</ref>

See also

References

<references group="" responsive="1"></references>
Retrieved from "https://kynnco.com:443/kynnpedia/index.php?title=Resistance_distance&oldid=7068"