📂グラフ理論

ネットワーク理論における媒介中心性

定義 ¹

ストレス中心性

ネットワーク $\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)$$

媒介中心性

以下のように定義された $C_{S} : V \to \mathbb{R}$ をノード $v$ の媒介中心性^{betweenness Centrality}という。 $$C_{B} (v) := \sum_{s \ne v \ne t \in V} {{ \sigma_{st} (v) } \over { \sigma_{st} }}$$

説明

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

直感的な意味

$$C_{S} (v) = \sum_{s \ne v \ne t \in V} \sigma_{st} (v) \\ C_{B} (v) = \sum_{s \ne v \ne t \in V} {{ \sigma_{st} (v) } \over { \sigma_{st} }}$$ 媒介中心性は本質的にストレス中心性と同じ概念であり、自然と、そのノードが交通や通信の観点からどれだけ重要かを示すことになる。ストレス中心性とは異なり、$s,t$ 毎に $\sigma_{st}$ を分けて、そのノードがもう少し適切に評価されるように修正された。

参照

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

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