抵抗距離

任意のN頂点の単純連結グラフG = ( V , E )と任意のN × N行列Mに対して：

${\displaystyle \sum _{i,j\in V}(LML)_{i,j}\Omega _{i,j}=-2\operatorname {tr} (ML)}$

この一般化された和の法則から、 Mの選択に応じていくつかの関係式を導き出すことができる。注目すべき 2 つの例は次のとおりである。

${\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}}}$

ここで、λk_はラプラシアン行列の非ゼロ固有値である。この順不同の和

$\sum_{i<j}\Omega_{i,j}}$

これはグラフのキルヒホッフ指数と呼ばれます。

単純連結グラフG = ( V , E )の場合、 2 つの頂点間の抵抗距離は、Gの全域木の集合Tの関数として次のように表すことができます。

${\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}}}$

ここで、T'はグラフG' = ( V , E + e _{i , j} )の全域木の集合である。言い換えれば、エッジに対して${\displaystyle (i,j)\in E}$ノード間の抵抗距離${\displaystyle i}$そして${\displaystyle j}$エッジの確率は${\displaystyle (i,j)}$はランダムスパニングツリーの中にあります${\displaystyle G}$。

頂点間の抵抗距離${\displaystyle u}$そして${\displaystyle v}$通勤時間に比例する${\displaystyle C_{u,v}}$ランダムウォークの${\displaystyle u}$そして${\displaystyle v}$通勤時間は、出発地点から始まるランダムウォークにおける期待歩数です。${\displaystyle u}$訪問${\displaystyle v}$、そして${\displaystyle u}$グラフの場合${\displaystyle m}$エッジ、抵抗距離、通勤時間は次のように関係しています。${\displaystyle C_{u,v}=2m\オメガ _{u,v}}$[ ^{2 ]​}

抵抗距離は、 2つの頂点間の脱出確率にも関係しています。脱出確率${\displaystyle P_{u,v}}$間${\displaystyle u}$そして${\displaystyle v}$は、ランダムウォークが開始して${\displaystyle u}$訪問${\displaystyle v}$戻る前に${\displaystyle u}$脱出確率は

${\displaystyle P_{u,v}={\frac {1}{\deg(u)\Omega _{u,v}}},}$

どこ${\displaystyle \deg(u)}$の度合いは${\displaystyle u}$^{[ 3 ]}通勤時間とは異なり、脱出確率は一般的に対称ではありません。つまり、${\displaystyle P_{u,v}\neq P_{v,u}}$。

ラプラシアンLは対称かつ正半定値であるため、

${\displaystyle \left(L+{\frac {1}{|V|}}\Phi \right),}$

したがって、その擬似逆行列Γも対称かつ半正定値である。したがって、あるKが存在し、${\displaystyle \Gamma =KK^{\textsf {T}}}$そして、次のように書くことができます。

${\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}}$

抵抗距離の平方根が、Kによって張られる空間におけるユークリッド距離に対応することを示している。

ファングラフとは、 n + 1 個の頂点を持つグラフであり、すべての i = 1, 2, 3, …, n に対して頂点iとn + 1の間にエッジがあり、すべての i = 1, 2, 3, …, n – 1 に対して頂点iとi + 1の間にエッジがある。

頂点n + 1と頂点i ∈ {1, 2, 3, …, n }間の抵抗距離は

${\displaystyle {\frac {F_{2(ni)+1}F_{2i-1}}{F_{2n}}}}$

ここで、F _jはj ≥ 0のj番目のフィボナッチ数である。^{[ 4 ]}