Betweenness Centrality (BC) と全米データ

全米データ (23,947,347 nodes, 58,333,344 edges ) に対して厳密な Betweenness Centrality (BC) を計算するとどの程度の時間がかかるのかということを最新のデータから推測してみる。


Magny-Cours 48 コアマシンでは、全米データ 768 SSSP, つまり 1対全最短路を 768 回解いたときの実行時間は 97.202 秒となる (このときの TEPS 値は 460.898 M)。そのため 1 コアで厳密な BC を計算すると約 35 日かかる。また計算上は 1M (100万)スレッドで同時計算した場合ではわずか 3 秒程度で計算が終了する。実用的にはクリアしなければならない点も多いのだが、将来的にはかなり大規模なグラフに対しても新世代スパコンを用いた実時間解析が可能になると推測する。


○Magny-Cours 計算サーバ : (4 CPU x 12 コア = 48 コア)
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4個
メモリ : 256GB (16 x 16GB / 1066MHz)
OS : Fedora 14 for x86_64