More than 1 year has passed since last update.

媒介中心性 (Betweenness Centrality) を求めるためのBrandesアルゴリズム

Last updated at 2024-01-17Posted at 2022-06-05

媒介中心性 [1]

ネットワークの中心性: (ノードとエッジからなる) グラフにおける各ノードの重要度を示す指標
- 次数中心性 (次数: 各ノードの接続エッジ数) など、色々ある
媒介中心性 (ノード媒介中心性) : 最短経路を基にした中心性の一つ。ある着目ノード$v$について、グラフ内の任意の2ノード間の最短経路上に、着目ノードが存在する割合
```
c_B(v)= \sum_{\substack{s,t \in V \\ s \neq t \neq v}} \frac{\sigma(s,t|v)}{\sigma(s,t)}
```
- $V$: ノード集合
- $\sigma(s,t)$: ノード$s,t$間の最短経路数
- $\sigma(s,t|v)$: ノード$s,t$間の最短経路のうち、着目ノード$v$を経由するものの数
- pythonのnetworkxライブラリではbetweenness_centralityとして実装されている

(参考): ネットワークの中心性（媒介中心性と固有ベクトル中心性）

Brandes アルゴリズム [2]

One-sided Dependency (始点ノード$s$、着目ノード$v$の媒介中心性)
```
\delta(s|v)=\sum_{\substack{t \in V \\ t \neq v}} \frac{\sigma_(s,t|v)}{\sigma_(s,t)}
```
- 着目ノード$v$が受け取るフロー数 (後述)
$c(s|v)$: 着目ノード$v$が送り出す最短経路1本あたりのフロー数 (後述)

最終的に求めたい媒介中心性は、One-sided Dependencyから計算できる

c_B(v)= \sum_{\substack{s,t \in V \\ s \neq t \neq v}} \frac{\sigma(s,t|v)}{\sigma(s,t)} = \sum_{\substack{s \in V \\ s \neq v}} \delta(s|v)

アルゴリズム手順の概要

ある始点ノード$s$について、グラフ内の全てのノード$\forall v \in V$のOne-sided Dependency $\delta(s|v)$ を求めたい
- 幅優先探索で始点$s$から各ノードへの最短経路数を求める
- 末端ノードから始点ノードへ逆順に辿り、$\delta(s|v)$, $c(s|v)$を求めていく
これをグラフ内の全てのノード$\forall s \in V$について計算し、最終的な媒介中心性を求める

アルゴリズム手順(1): 始点$s$からの最短経路数を求める

以下のようなグラフを考える

例として、始点ノード$s=0$について、幅優先探索で最短経路のツリーを作り、始点ノードからの最短経路数を求める

One-sided Dependency $\delta$を求めるための考え方

始点ノード以外の各ノードは上のノードへ1.0だけフローを流す
- この例では、始点ノード以外のノード数は合計8なので、全部で8.0のフローがネットワーク上を流れる
始点ノード以外のそれぞれのノードについて、下のノードから流れてくるフローの合計($=\delta$)を求めたい

アルゴリズム手順(2): 逆順に辿り、$\delta(s|v)$, $c(s|v)$を求めていく

一番下のノードから、逆順で以下の値を求めていく
- $\delta$: 下のノードから受け取ったフロー数 (< >)
- $c$: 上のノードへ送り出す最短経路1本あたりのフロー数 (( ))
ノード#6,7,8 (最下段) の$\delta$, $c$
- 下にノードはないので$\delta=0.0$
- 各ノードは上のノードへ合計1.0だけフローを流す
  ⇒$c=$最短経路数の逆数

ノード#4の$\delta$
- 下方のノード#6,7,8から、自身の最短経路数2本分のフローを受け取る
  - ノード#8からは、合計1.0のフローの内、2/3のフローを受け取っている
  - 受け取ったフローの合計が$\delta(=2.666)$

ノード#4の$c$
- ノード#4自身も上のノードへフローを1.0だけ流す
  ⇒下から受け取ったフロー数$\delta$に1.0を足して、自身の経路数で割る
  ($c=1.833$)

ノード#3,5の$\delta$, $c$
- 同様の計算
  - ノード#5は、合計1.0のフローの内、1/3のフローをノード#8から受け取っている

ノード#1,2についても同様

アルゴリズム手順(3): 媒介中心性の計算

手順(1),(2)を全てのノードを始点ノードとして行い、各ノード上での$\delta$の値を合計したものが媒介中心性
(無向グラフの場合はさらに1/2をかけた値)
- 例えば、ノード#1の媒介中心性は、始点ノード#1以外の$\delta$の値がそれぞれ
  $\delta(0|1)=2.833,$
  $\delta(2|1)=0.5,$
  $\delta(3|1)=4.0,$
  $\delta(4|1)=1.5,$
  $\delta(5|1)=0.0,$
  $\delta(6|1)=1.0,$
  $\delta(7|1)=1.5,$
  $\delta(8|1)=0.333$
  なので、媒介中心性は
  $(2.833 + 0.5 + 4.0 + 1.5 + 0.0 + 1.0 + 1.5 + 0.333) / 2 = 5.833$
- $\frac{1}{(n-1)(n-2)}$ ($n$: ノード数) をかけて正規化されることが多い (無向グラフの場合は$\frac{2}{(n-1)(n-2)}$)

networkxでの挙動

networkxでbetweenness_centralityを計算する際、内部で以下の関数が呼び出されている
- 手順(1) 最短経路の導出のための _single_source_shortest_path_basic
- 手順(2) 逆順での$\delta, c$の導出のための _accumulate_basic

(Python 3.9.12, networkx=2.7.1)

bc.py

import networkx as nx
from networkx.algorithms.centrality.betweenness import _single_source_shortest_path_basic, _accumulate_basic

G = nx.Graph()
G.add_nodes_from(range(9))
G.add_edges_from([(0,1),(0,2),(1,2),(1,3),(1,4),(2,4),(2,5),(3,5),(4,6),(4,7),(4,8),(5,8),(6,7),(6,8)])
print("edges:", G.edges)

source = 0
S, P, sigma, _ = _single_source_shortest_path_basic(G, source)
betweenness_s, delta_s = _accumulate_basic(dict.fromkeys(G, 0.0), S, P, sigma, source)
print("bc for source #{}:".format(source), betweenness_s)
print("deltas for source #{}:".format(source), delta_s)

vertice = 1
delta_v = list()
betweenness = dict.fromkeys(G, 0.0)
for s in range(9):
    S, P, sigma, _ = _single_source_shortest_path_basic(G, s)
    betweenness, delta = _accumulate_basic(betweenness, S, P, sigma, s)
    delta_v.append(delta[vertice])
print("deltas on node #{}".format(vertice), delta_v, ", sum:", sum(delta_v[:vertice] + delta_v[(vertice+1):]))

bc_won = nx.betweenness_centrality(G,normalized=False)
bc = nx.betweenness_centrality(G)
print("bc_wo_normalization:", bc_won)
print("bc:", bc)

(実行結果)

edges: [(0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (2, 4), (2, 5), (3, 5), (4, 6), (4, 7), (4, 8), (5, 8), (6, 7), (6, 8)]
bc for source #0: {0: 0.0, 1: 2.833333333333333, 2: 3.1666666666666665, 3: 0.0, 4: 2.6666666666666665, 5: 0.3333333333333333, 6: 0.0, 7: 0.0, 8: 0.0}
deltas for source #0: {0: 7.999999999999999, 1: 2.833333333333333, 2: 3.1666666666666665, 3: 0, 4: 2.6666666666666665, 5: 0.3333333333333333, 6: 0, 7: 0, 8: 0}
deltas on node #1 [2.833333333333333, 8.0, 0.5, 4.0, 1.5, 0, 1.0, 1.5, 0.3333333333333333] , sum: 11.666666666666666
bc_wo_normalization: {0: 0.0, 1: 5.833333333333333, 2: 4.499999999999999, 3: 0.5, 4: 10.833333333333334, 5: 2.833333333333333, 6: 0.8333333333333333, 7: 0.0, 8: 2.6666666666666665}
bc: {0: 0.0, 1: 0.20833333333333331, 2: 0.16071428571428567, 3: 0.017857142857142856, 4: 0.3869047619047619, 5: 0.10119047619047618, 6: 0.029761904761904757, 7: 0.0, 8: 0.09523809523809523}

なぜこの考え方でうまくいくのか？

(編集中)

参考文献

[1]Z. Alghamdi, F. Jamour, S. Skiadopoulos, and P. Kalnis, “A Benchmark for Betweenness Centrality Approximation Algorithms on Large Graphs,” Jun. 2017, pp. 1–12. doi: 10.1145/3085504.3085510.
[2]U. Brandes, “A faster algorithm for betweenness centrality,” The Journal of Mathematical Sociology, vol. 25, no. 2, pp. 163–177, Jun. 2001, doi: 10.1080/0022250X.2001.9990249.

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up