全対全最短路と媒介中心性

日本語では媒介中心性とも言われる以下の指標であるが、始点の方はランダムサンプリングで数百点ぐらいを使用しても近似性能は良いようである（幾つかの論文によると）。



いろいろな近似手法を提案して、それらの性能評価するためには全対全の最短路を全て求めて置くのも良いだろう。ただしディスク容量が相当必要となるのでディスク容量の少ない新クラスタ計算機での実行には向いていない。現在のクラスタ計算機は 1 ノードあたり 5TB のディスク容量があるが、新クラスタ計算機は各ノードのディスク容量(73GB x 2)とメモリ量(128GB)はほぼ同じである。

ちなみに以下の計算サーバ（２４コア）で全米データ(点数 23,947,347, 枝数 58,333,344)の1対全最短路を 1,000 回解くと 232 秒になる(平均すると1回の実行で 5.6秒)。



全米データの全対全の最短路問題を解くためには、1対全の最短路問題を 2,394,7347 回解かなければならない。よって、以下の計算サーバだけで実行すると (23,947,347点 / 1,000点) * 232 秒 = 5,555,785秒 ≈ 1543.3時間 ≈ 64.3日 となる。ただし今年の暮れには研究室の計算機の総コア数が 400 を越えるので、数日で終わると予想される。

○計算サーバ (4 CPU x 6 コア = 24 コア)
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 13 for x86_64