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.
DefinitionEdit
On a graph Template:Mvar, the resistance distance Template:Math between two vertices Template:Mvar and Template:Mvar is<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</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 Template:Math denotes the Moore–Penrose inverse, Template:Mvar the Laplacian matrix of Template:Mvar, Template:Math is the number of vertices in Template:Mvar, and Template:Math is the Template:Math matrix containing all 1s.
Properties of resistance distanceEdit
If Template:Math then Template:Math. For an undirected graph
- <math>\Omega_{i,j}=\Omega_{j,i}=\Gamma_{i,i}+\Gamma_{j,j}-2\Gamma_{i,j}</math>
General sum ruleEdit
For any Template:Mvar-vertex simple connected graph Template:Math and arbitrary Template:Math matrix Template:Mvar:
- <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 Template:Mvar. 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 Template:Mvar 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 graphEdit
For a simple connected graph Template:Math, 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:
- <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 Template:Mvar is the set of spanning trees for the graph Template:Math. 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 walksEdit
The resistance distance between vertices <math>u</math> and <math>v</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>Template:Cite book</ref>
Resistance distance is also related to the escape probability between two vertices. The escape probability <math>P_{u,v}</math> between <math>u</math> and <math>v</math> is the probability that a random walk starting at <math>u</math> visits <math>v</math> before returning to <math>u</math>. The escape probability equals
- <math>
P_{u,v} = \frac{1}{\deg(u)\Omega_{u,v}}, </math> where <math>\deg(u)</math> is the degree of <math>u</math>.<ref>Template:Cite book</ref> Unlike the commute time, the escape probability is not symmetric in general, i.e., <math>P_{u,v}\neq P_{v,u}</math>.
As a squared Euclidean distanceEdit
Since the Laplacian Template:Mvar is symmetric and positive semi-definite, so is
- <math>\left(L+\frac{1}{|V|}\Phi\right),</math>
thus its pseudo-inverse Template:Math is also symmetric and positive semi-definite. Thus, there is a Template:Mvar 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 Template:Mvar.
Connection with Fibonacci numbersEdit
A fan graph is a graph on Template:Math vertices where there is an edge between vertex Template:Mvar and Template:Math for all Template:Math, and there is an edge between vertex Template:Mvar and Template:Mvar for all Template:Math.
The resistance distance between vertex Template:Math and vertex Template:Math is
- <math>\frac{ F_{2(n-i)+1} F_{2i-1} }{ F_{2n} }</math>
where Template:Mvar is the Template:Mvar-th Fibonacci number, for Template:Math.<ref>Template:Cite journal</ref>