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

# 媒介中心性 [1]
- ネットワークの中心性: (ノードとエッジからなる) グラフにおける各ノードの重要度を示す指標
    - 次数中心性 (次数: 各ノードの接続エッジ数) など、色々ある

- __媒介中心性 (ノード媒介中心性)__ : 最短経路を基にした中心性の一つ。ある着目ノード$v$について、グラフ内の任意の2ノード間の最短経路上に、着目ノードが存在する割合
  ```math
  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として実装されている

(参考): [ネットワークの中心性（媒介中心性と固有ベクトル中心性）](https://qiita.com/igenki/items/a673140ecbfda4ee7dba)

# Brandes アルゴリズム [2]
- One-sided Dependency (始点ノード$s$、着目ノード$v$の媒介中心性)
  ```math
  \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から計算できる
  ```math
  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$からの最短経路数を求める
- 以下のようなグラフを考える

![graph.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/907348/d01a65c7-0f6b-98b3-9951-e5e1bdca5da7.png)
- 例として、始点ノード$s=0$について、幅優先探索で最短経路のツリーを作り、始点ノードからの最短経路数を求める

![shortest_path.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/907348/9a8c4ea4-0f8c-5fec-2dfb-7638f557d7bf.png)

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

## アルゴリズム手順(2): 逆順に辿り、$\delta(s|v)$, $c(s|v)$を求めていく
- 一番下のノードから、逆順で以下の値を求めていく
  - <font color="red">$\delta$</font>: 下のノードから受け取ったフロー数 (<font color="red">< ></font>)
  - <font color="green">$c$</font>: 上のノードへ送り出す最短経路1本あたりのフロー数 (<font color="green">( )</font>)

- ノード#6,7,8 (最下段) の<font color="red">$\delta$</font>, <font color="green">$c$</font>
  - 下にノードはないので$\delta=0.0$
  - 各ノードは上のノードへ合計1.0だけフローを流す
  ⇒$c=$最短経路数の逆数

![delta_level0.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/907348/f78458b9-2c80-98c7-b320-3534c28eca5f.png)
- ノード#4の<font color="red">$\delta$</font>
  - 下方のノード#6,7,8から、自身の最短経路数<font color="blue">2</font>本分のフローを受け取る
    - ノード#8からは、合計1.0のフローの内、2/3のフローを受け取っている
    - 受け取ったフローの合計が$\delta(=2.666)$

![delta_level1_node4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/907348/396064b0-0a05-b727-f0ce-46aeaf64330a.png)

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

![coeff_level1_node4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/907348/75cec662-1232-6d67-2fa1-927c84f302f9.png)
- ノード#3,5の<font color="red">$\delta$</font>, <font color="green">$c$</font>
  - 同様の計算
    - ノード#5は、合計1.0のフローの内、1/3のフローをノード#8から受け取っている
  
![delta_level1_node5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/907348/b8bc9ddd-0cc4-0068-3222-56f293360d3c.png)

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

![delta_level2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/907348/50bdf6ad-308b-224c-8b7e-5b932d46e0dd.png)

## アルゴリズム手順(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)
```python: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.