logo

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

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

定義 1

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

説明

σst(v)\sigma_{st} (v)

σst\sigma_{st} の定義をよく読めば、s,ts,tの間の最短距離d(s,t)=d(t,s)d(s,t) = d(t,s)ではなくその最短距離になるパスの数で、全てのvVv \in Vに対してσvv=1\sigma_{vv} = 1であり、グラフの距離関数 dd に関してσst(v)\sigma_{st} (v)は次のようになる。 σst(v)={0,if d(s,t)<d(s,v)+d(v,t)σsvσvt,otherwise \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によって紹介された、最も古い中心性の一つであり、数式 CS(v)=svtVσst(v) C_{S} (v) = \sum_{s \ne v \ne t \in V} \sigma_{st} (v) を見れば、ノード vVv \in V が全ての二つのノード s,tVs, t \in V の間を仲介することによって、どれだけ最短距離のパスを多く作り出しているかを示すと考えることができる。自然界の多くの現象…例えば水滴が表面積を最小限にし、動作の作用が最小になるように、二つのノードをつなぐ方法の中では最も短かったり早かったりするパスに多くの関心があり、このように最短距離のパスに頻繁に属する点には多くのストレスがかかるだろう。この直感的な意味から、CS(v)C_{S} (v)をストレス中心性と呼ぶことはかなり意味がある。

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

一緒に見る

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


  1. Brandes. (2001). A Faster Algorithm for Betweenness Centrality. https://doi.org/10.1080/0022250X.2001.9990249 ↩︎