betweenness centrality

グラフの特性を解析する指標の一つとして、centrality(中心性)がある。centrality にはいくつか種類があり、今回扱うのは betweenness centrality となっている。

betweenness centrality は点が全ての最短路にどれだけ寄与しているかを示している。betweenness centrality が高い点は何度も最短路に登場するので、重要な点であるといえる。

基本的に最短路を求める bfs か Dijkstra's Algorithm を用いて計算している。bfs だが cray の XMT を用いて並列で処理するという先行研究もある。