BFS と SP(Shortest Path) による Centrality

こちらのクラスタ計算機において、現在 DIMACS アメリカのデータに用いて以下の Centrality(中心性)の計算を行っている(特に BC:Betweenness Centrality)。



以前にこちらのブログから報告したように以下は NY(NewYork)データに対する(BFS:幅優先探索)を用いた BC の計算結果である。



次の結果は BFS ではなく、実際の枝の重みを考慮した SP(Shortest Path)による BC の計算結果である。ただし、まだ結果の正しさについての検証は終了していないので参考まで。



両者と実際の道路ネットワークを比較してみると面白いのだが、後者の方がより実際の道路ネットワークの形態に近いことは十分予想できる。