📂グラフ理論

ネットワーク理論におけるストレス中心性

定義 ¹

ネットワーク $\left( V, E \right)$ で二つのノード $s,t \in V$ をつなぐ最短距離のパスの数を $\sigma_{st} = \sigma_{ts}$ とし、特に $s,t$ をつなぐパスの中で別のノード $v \in V$ を含むパスの数を $\sigma_{st} (v)$ と表示しよう。次のように定義される $C_{S} : V \to \mathbb{Z}$ をノード $v$ のストレス中心性^{stress Centrality}という。 $$ C_{S} (v) := \sum_{s \ne v \ne t \in V} \sigma_{st} (v) $$

説明

$\sigma_{st} (v)$

$\sigma_{st}$ の定義をよく読めば、$s,t$の間の最短距離$d(s,t) = d(t,s)$ではなくその最短距離になるパスの数で、全ての$v \in V$に対して$\sigma_{vv} = 1$であり、グラフの距離関数 $d$ に関して$\sigma_{st} (v)$は次のようになる。 $$ \sigma_{st} (v) = \begin{cases} 0 & , \text{if } d \left( s , t \right) < d \left( s , v \right) + d \left( v , t \right) \\ \sigma_{sv} \cdot \sigma_{vt} & , \text{otherwise} \end{cases} $$

直感的な意味

ストレス中心性は1953年にShimbelによって紹介された、最も古い中心性の一つであり、数式 $$ C_{S} (v) = \sum_{s \ne v \ne t \in V} \sigma_{st} (v) $$ を見れば、ノード $v \in V$ が全ての二つのノード $s, t \in V$ の間を仲介することによって、どれだけ最短距離のパスを多く作り出しているかを示すと考えることができる。自然界の多くの現象…例えば水滴が表面積を最小限にし、動作の作用が最小になるように、二つのノードをつなぐ方法の中では最も短かったり早かったりするパスに多くの関心があり、このように最短距離のパスに頻繁に属する点には多くのストレスがかかるだろう。この直感的な意味から、$C_{S} (v)$をストレス中心性と呼ぶことはかなり意味がある。

後に、ストレス中心性を補完する尺度として媒介中心性が紹介された。

一緒に見る

ネットワークの様々な中心性

• 次数中心性
• 媒介中心性
  • ストレス中心性
• 近接中心性
• 固有ベクトル中心性