ランダムウォークの近接中心性

ランダム ウォークの近接中心性は、ネットワークの中心性の尺度であり、ランダム ウォークのプロセスがネットワークの他のノードからノードに到達する平均速度を表します。近接中心性と似ていますが、遠さは最短経路ではなくランダム ウォークの予想される長さによって測定されます。

この概念は、ホワイトとスミス（2003）によってマルコフ中心性という名前で初めて提案されました。^[1]

有限数のノードと、特定のノードから始まりエッジに沿ってノードからノードへと進むランダム ウォーク プロセスを持つネットワークを考えてみましょう。各ノードから、たどるエッジをランダムに選択します。重み付けされていないネットワークでは、特定のエッジを選択する確率はすべての利用可能なエッジで等しくなりますが、重み付けされたネットワークでは、エッジの重みに比例します。ネットワークの任意のノードから開始されたランダム ウォーク プロセスが平均して比較的少ないステップでこの特定のノードに到達する場合、ノードは他のノードに近いとみなされます。

j=1,…,n で表される n 個のノードを持つ有向または無向の重み付きネットワークと、遷移行列 M を持つこのネットワーク上のランダム ウォーク プロセスについて考えます。Mの要素は、ノード i に到達したランダム ウォーカーが直接ノード j に進む確率を表します。これらの確率は次のように定義されます。 ${\displaystyle m_{ij}}$

${\displaystyle m_{ij}={\frac {a_{ij}}{\sum _{k=1}^{n}a_{ik}}}}$

ここで、ネットワークの重み行列 A の (i,j) 番目の要素です。2 つのノード間にエッジがない場合、A 行列の対応する要素は 0 になります。 ${\displaystyle a_{ij}}$

ノード i のランダム ウォークの近接中心性は、そのノードへの平均初回通過時間の逆数です。

${\displaystyle C_{i}^{RWC}={\frac {n}{\sum _{j=1}^{n}H(j,i)}}}$

ここで、ノード j からノード i までの平均初回通過時間です。 ${\displaystyle H(j,i)}$

ノード i からノード j への平均初回通過時間は、プロセスがノード i からノード j に初めて到達するまでにかかる予想されるステップ数です。

${\displaystyle H(i,j)=\sum _{r=1}^{\infty }rP(i,j,r)}$

ここで、P(i,j,r) は、i から j に初めて到達するのにちょうど r ステップかかる確率を表します。r ステップで初めてノードに到達するこれらの確率を計算するには、ターゲット ノードを吸収ノードと見なし、M の j 番目の行と列を削除して と表記する変換を導入すると便利です。i から開始して r-1 ステップ後に k にあるプロセスの確率は の (i,k) 番目の要素で簡単に与えられるため、P(i,j,r) は次のように表すことができます。 ${\displaystyle M_{-j}}$${\displaystyle M_{-j}^{r-1}}$

${\displaystyle P(i,j,r)=\sum _{k\neq j}((M_{-j}^{r-1}))_{ik}m_{kj}}$

これを平均初回通過時間の式に代入すると、

${\displaystyle H(i,j)=\sum _{r=1}^{\infty }r\sum _{k\neq j}((M_{-j}^{r-1}))_{ik}m_{kj}}$

行列の等比級数 の和の公式を用いると、

${\displaystyle H(i,j)=\sum _{k\neq j}((I-M_{-j})^{-2})_{ik}m_{kj}}$

ここで、Iはn-1次元の単位行列です。

計算の便宜上、この式は次のようにベクトル化できる。

${\displaystyle H(.,j)=(I-M_{-j})^{-1}e}$

ここで、はノード j で終了する歩行の最初の通過時間のベクトルであり、e は 1 の n-1 次元ベクトルです。 ${\displaystyle H(.,j)}$

平均初回通過時間は、無向グラフの場合でも対称ではありません。

Noh と Rieger (2004) が行ったシミュレーションによると、Barabási-Albert モデルにおけるランダム ウォークの近接中心性の分布は、主に次数分布によって決まります。このようなネットワークでは、ノードのランダム ウォークの近接中心性は次数にほぼ比例しますが、次数とともに単調に増加するわけではありません。

ランダム ウォークの近接中心性は、最短経路の概念が意味をなさないか、システムの性質を適切に評価するのに非常に制限的であるアプリケーションの場合、単純な近接中心性よりも適切な尺度です。 これは、たとえば、分析対象のプロセスが、特定のポイントに到達するという特別な意図なしに、またはターゲットに到達するための最短経路を見つける能力なしに、ネットワーク内で展開される場合に当てはまります。 ネットワーク内のランダム ウォークの一例は、特定のコインが経済で循環する方法です。コインは、特定の個人に到達するという意図なしに、トランザクションを通じて人から人へと渡されます。 最短経路の概念があまり役に立たない別の例は、密に接続されたネットワークです。 さらに、最短経路は自己ループの影響を受けないため、自己ループが重要なネットワークを分析する場合は、ランダム ウォークの近接中心性の方が近接中心性よりも適切な尺度です。

経済学の分野での重要な応用は、重要な自己ループを持つ密に接続された重み付きネットワークによって表される経済の投入産出モデルの分析である。^[2]

この概念は自然科学でも広く使われています。生物学的応用の1つは、タンパク質間相互作用の分析です。^[3]

^{ニューマン[4]}が提唱した関連概念は、ランダムウォーク媒介中心性である。ランダムウォーク近接中心性が近接中心性のランダムウォーク版であるのと同様に、ランダムウォーク媒介中心性も同様に媒介中心性のランダムウォーク版である。通常の媒介中心性測定とは異なり、特定のノードを通過する最短経路だけでなく、そのノードを横切るすべての可能な経路をカウントする。

正式には、ノードのランダムウォーク媒介中心性は

${\displaystyle C_{i}^{RWB}=\sum _{j\neq i\neq k}r_{jk}}$

ここで、行列 R の要素には、ノード j から始まり、吸収ノード k を経てノード i を通過するランダム ウォークの確率が含まれます。 ${\displaystyle r_{jk}}$

大規模ネットワークにおけるランダムウォークの媒介性を計算することは、計算量が非常に多い。^[5]

もう一つのランダムウォークに基づく中心性は、2次中心性である。^[6]与えられたノードを通過する最短経路を数える代わりに（ランダムウォークの媒介中心性のように）、グラフ上のランダムウォークの別の特性に焦点を当てる。ランダムウォークがノードに戻る時間の標準偏差の期待値がその中心性を構成する。その偏差が低いほど、そのノードはより中心的である。

大規模な任意のグラフ上での 2 次媒介性の計算も、その複雑さと同様に集中的に行われます(最悪のケースはロリポップ グラフで達成されます)。 ${\displaystyle O(n^{3})}$

• 中心性