In graph theory, the resistance distance between two vertices of a simple, connected graph, , is equal to the resistance between two equivalent points on an electrical network, constructed so as to correspond to , with each edge being replaced by a resistance of one ohm. It is a metric on graphs.
Definition
On a graph , the resistance distance between two vertices and is
:<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, the Laplacian matrix of , is the number of vertices in , and is the matrix containing all 1s.
Properties of resistance distance
If then . 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 -vertex simple connected graph and arbitrary matrix :
:<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 . 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 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 , the resistance distance between two vertices may be expressed as a function of the set of spanning trees, , of 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 is the set of spanning trees for the graph . 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>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>.
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>. 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 distance
Since the Laplacian 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 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 .
Connection with Fibonacci numbers
A fan graph is a graph on vertices where there is an edge between vertex and for all , and there is an edge between vertex and for all .
The resistance distance between vertex and vertex is
:<math>\frac{ F_{2(n-i)+1} F_{2i-1} }{ F_{2n} }</math>
where is the -th Fibonacci number, for .
See also
- Conductance (graph)