Editing Resistance distance

{{short description|Graph metric of electrical resistance between nodes}}

In [[graph theory]], the '''resistance distance''' between two [[vertex (graph theory)|vertices]] of a [[Graph (discrete mathematics)|simple]], [[connected graph]], {{mvar|G}}, is equal to the [[electrical resistance|resistance]] between two equivalent points on an [[electrical network]], constructed so as to correspond to {{mvar|G}}, with each [[graph (discrete mathematics)|edge]] being replaced by a [[electrical resistance|resistance]] of one [[ohm]]. It is a [[metric (mathematics)|metric]] on [[Graph (discrete mathematics)|graphs]].

==Definition==

On a [[Graph (discrete mathematics)|graph]] {{mvar|G}}, the '''resistance distance''' {{math|Ω{{sub|''i'',''j''}}}}  between two vertices {{mvar|v{{sub|i}}}} and {{mvar|v{{sub|j}}}} is<ref>{{Cite web|url=https://mathworld.wolfram.com/ResistanceDistance.html|title = 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 {{math|{{sup|+}}}} denotes the [[Moore–Penrose inverse]], {{mvar|L}} the [[Laplacian matrix]] of {{mvar|G}}, {{math|{{abs|''V''}}}} is the number of vertices in {{mvar|G}}, and {{math|Φ}} is the {{math|{{abs|''V''}} × {{abs|''V''}}}} matrix containing all 1s.

==Properties of resistance distance==

If {{math|1=''i'' = ''j''}} then {{math|1=Ω{{sub|''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 {{mvar|N}}-vertex [[graph (discrete mathematics)|simple connected graph]] {{math|1=''G'' = (''V'', ''E'')}} and arbitrary {{math|''N''×''N''}} [[matrix (mathematics)|matrix]] {{mvar|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 {{mvar|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 {{mvar|λ{{sub|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 {{math|1=''G'' = (''V'', ''E'')}}, the '''resistance distance''' between two vertices may be expressed as a [[Function (mathematics)|function]] of the [[Set (mathematics)|set]] of [[spanning tree (mathematics)|spanning trees]], {{mvar|T}}, of {{mvar|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 {{mvar|T'}} is the set of spanning trees for the graph {{math|1=''G' ''= (''V'', ''E'' + ''e''{{sub|''i'',''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>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>{{cite book |last1=Chandra, Ashok K and Raghavan, Prabhakar and Ruzzo, Walter L and Smolensky, Roman |title=Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 |chapter=The electrical resistance of a graph captures its commute and cover times |date=1989 |issue=21 |pages=574–685 |doi=10.1145/73007.73062 |isbn=0897913078 |chapter-url=https://dl.acm.org/doi/abs/10.1145/73007.73062}}</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 (graph theory)|degree]] of <math>u</math>.<ref>{{cite book |last1=Doyle |first1=Peter |last2=Snell |first2=J. Laurie |title=Random Walks and Electric Networks |date=1984 |publisher=American Mathematical Society |isbn=9781614440222}}</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 distance===
Since the Laplacian {{mvar|L}} is symmetric and positive semi-definite, so is 
:<math>\left(L+\frac{1}{|V|}\Phi\right),</math> 
thus its pseudo-inverse {{math|Γ}} is also symmetric and positive semi-definite.  Thus, there is a {{mvar|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 {{mvar|K}}.

===Connection with Fibonacci numbers ===
A fan graph is a graph on {{math|''n'' + 1}} vertices where there is an edge between vertex {{mvar|i}} and {{math|''n'' + 1}} for all {{math|1=''i'' = 1, 2, 3, …, ''n''}}, and there is an edge between vertex {{mvar|i}} and {{mvar|''i'' + 1}} for all {{math|1=i = 1, 2, 3, …, ''n'' – 1}}.

The resistance distance between vertex {{math|''n'' + 1}} and vertex {{math|''i'' ∈ {1, 2, 3, …, ''n''} }} is 
:<math>\frac{ F_{2(n-i)+1} F_{2i-1} }{ F_{2n} }</math> 
where {{mvar|F{{sub|j}}}} is the {{mvar|j}}-th Fibonacci number, for {{math|''j'' ≥ 0}}.<ref>{{cite journal
 | last1 = Bapat | first1 = R. B.
 | last2 = Gupta | first2 = Somit
 | doi = 10.1007/s13226-010-0004-2
 | issue = 1
 | journal = Indian Journal of Pure and Applied Mathematics
 | mr = 2650096
 | pages = 1–13
 | title = Resistance distance in wheels and fans
 | url = https://www.isid.ac.in/~rbb/somitnew.pdf
 | volume = 41
 | year = 2010}}</ref>

== See also ==
* [[Conductance (graph)]]

==References==
{{Reflist}}
* {{cite journal
|first1= D. J.
|last1=Klein
|first2=M. J.
|last2=Randic
|journal=J. Math. Chem.
|doi=10.1007/BF01164627
|title=Resistance Distance
|volume=12
|pages=81–95
|year=1993
|s2cid=16382100
}}
* {{cite journal
|first1=Ivan
|last1=Gutman
|first2=Bojan
|last2=Mohar
|title=The quasi-Wiener and the Kirchhoff indices coincide
|year=1996
|journal=J. Chem. Inf. Comput. Sci.
|volume=36
|issue=5
|pages=982–985
|doi=10.1021/ci960007t
}}
* {{cite journal
|title=Closed-form formulas for the Kirchhoff index
|first1=Jose Luis
|last1=Palacios
|journal=Int. J. Quantum Chem.
|year=2001
|volume=81
|issue=2
|pages=135–140
|doi=10.1002/1097-461X(2001)81:2<135::AID-QUA4>3.0.CO;2-G
}}
* {{cite journal
|first1=D.
|last1=Babic
|first2=D. J.
|last2=Klein
|first3=I.
|last3=Lukovits
|first4=S.
|last4=Nikolic
|first5=N.
|last5=Trinajstic
|title=Resistance-distance matrix: a computational algorithm and its application
|journal=Int. J. Quantum Chem.
|year=2002
|doi=10.1002/qua.10057
|volume=90
|number=1
|pages=166–167
}}
* {{cite journal
 |url         = http://www.stkpula.hr/ccacaa/CCA-PDF/cca2002/v75-n2/CCA_75_2002_633_649_KLEIN.pdf
 |journal     = Croatica Chem. Acta
 |last1       = Klein
 |first1      = D. J.
 |title       = Resistance Distance Sum Rules
 |year        = 2002
 |volume      = 75
 |number      = 2
 |pages       = 633–649
 |url-status     = dead
 |archiveurl  = https://web.archive.org/web/20120326104653/http://www.stkpula.hr/ccacaa/CCA-PDF/cca2002/v75-n2/CCA_75_2002_633_649_KLEIN.pdf
 |archivedate = 2012-03-26
}}
* {{cite journal
|first1=Ravindra B.
|last1=Bapat
|first2=Ivan
|last2=Gutman
|first3=Wenjun
|last3=Xiao
|title=A simple method for computing resistance distance
|journal=Z. Naturforsch.
|year=2003
|volume=58a
|issue=9–10
|pages=494–498
|url=http://www.znaturforsch.com/aa/v58a/c58a.htm#No9
|bibcode = 2003ZNatA..58..494B |doi = 10.1515/zna-2003-9-1003 |doi-access=free
}}
* {{cite journal
|first1=Jose Luis
|last1=Placios
|title=Foster's formulas via probability and the Kirchhoff index
|journal=Method. Comput. Appl. Probab.
|year=2004
|volume=6
|number=4
|pages=381–387
|doi=10.1023/B:MCAP.0000045086.76839.54
|s2cid=120309331
}}
* {{cite journal
|first1=Enrique
|last1=Bendito
|first2=Angeles
|last2=Carmona
|first3=Andres M.
|last3=Encinas
|first4=Jose M.
|last4=Gesto
|title=A formula for the Kirchhoff index
|journal=Int. J. Quantum Chem.
|year=2008
|doi=10.1002/qua.21588
|pages=1200–1206
|volume=108
|number=6
|bibcode = 2008IJQC..108.1200B }}
* {{cite journal
|journal=Int. J. Quantum Chem.
|first1=Bo
|last1=Zhou
|title=The Kirchhoff index and the matching number
|first2=Nenad
|last2=Trinajstic
|volume=109
|issue=13
|year=2009
|pages=2978–2981
|doi=10.1002/qua.21915
|bibcode = 2009IJQC..109.2978Z }}
* {{cite journal
|first1=Bo
|last1=Zhou
|first2=Nenad
|last2=Trinajstic
|title=On resistance-distance and the Kirchhoff index
|journal=J. Math. Chem.
|year=2009
|volume=46
|pages=283–289
|doi=10.1007/s10910-008-9459-3
|hdl=10338.dmlcz/140814
|s2cid=119389248
|hdl-access=free
}}
* {{cite journal
|first1=Bo
|last1=Zhou
|title=On sum of powers of Laplacian eigenvalues and Laplacian Estrada Index of graphs
|journal=Match Commun. Math. Comput. Chem
|volume=62
|pages=611–619
|arxiv=1102.1144
|year=2011
}}

* {{cite journal
|first1=Heping
|last1=Zhang
|first2=Yujun
|last2=Yang
|title=Resistance distance and Kirchhoff index in circulant graphs
|journal=Int. J. Quantum Chem.
|year=2007
|volume=107
|issue=2
|pages=330–339
|doi=10.1002/qua.21068
|bibcode = 2007IJQC..107..330Z }}

* {{cite journal
|first1=Yujun
|last1=Yang
|first2=Heping
|last2=Zhang
|title=Some rules on resistance distance with applications
|journal=J. Phys. A: Math. Theor.
|year=2008
|volume=41
|issue=44
|pages=445203
|doi=10.1088/1751-8113/41/44/445203
|bibcode = 2008JPhA...41R5203Y |s2cid=122226781
}}

[[Category:Electrical resistance and conductance]]
[[Category:Graph distance]]