[論文紹介] Fast shortest path distance estimation in large networks

とりあえず最近読んだ論文の紹介でも．

Webやソーシャルネットワークなど，巨大なグラフに対して，データマイニングや情報検索を行う際に，頂点間の最短距離を計算するという処理は，しばしば必要されますが，この規模のグラフに対して，BFSやDijkstra法を直接行うと時間がかかりすぎるという問題があります．『Fast shortest path distance estimation in large networks』は，頂点の小さなサブセットに対して，予め最短距離を求めておくことで，最短距離クエリに対して高速に答えを近似する手法について議論した論文です．アルゴリズムは大体以下のようになります．

上手く頂点のサブセットを選ぶ．ここで選ばれた頂点をランドマークと呼ぶことにする．
グラフ内の任意の点vと，任意のランドマークuに対して，vからuへの最短距離を記録しておく．
sからtへの最短距離クエリが与えられたとき，全てのランドマークuに対して，
　　(sからuへの最短距離) + (tからuへの最短距離)
を2で記録した値から計算し，その最小値を最短距離の近似値として返す．

このアルゴリズムでは，1のランドマークの選び方によって，近似の良さが変化します．(sからuへの最短距離) + (tからuへの最短距離) が，(sからtへの最短距離) に一致する必要十分条件は，uがsからtへの最短経路上にあることなので，ランドマークは，できるだけ最短経路に多く含まれている頂点を選べば良さそうだという直観を得ることができます．しかし，最良のランドマークを選ぶ問題はNP困難であることが証明できるので，ランドマークはヒューリスティックに選ぶことになります．論文では，ランドマークの選択に使うヒューリスティックをいくつか提案し，それらを比較していました．平均的に最も良い結果を与えるとされたヒューリスティックは closeness centrality の考え方に基づくものでした．

頂点vの closeness centrality は，その頂点からグラフ内の全ての頂点への最短距離の平均で定義されます．直感的に，小さい closeness centrality を持つ頂点は，多くの最短経路に含まれていると考えられるので，よいランドマークの候補になります．closeness centrality は，真面目に全頂点への最短距離を求めなくても，頂点のサンプリングをすることで精度良く近似できるらしいです．

実験では，closeness centrality が小さい順にランドマークを選んだ場合，ランダムに選んだ場合と比べて，同じ近似精度を1/250のランドマーク数で達成しています．辺数が7000万以上あるグラフに対して，数十個のランドマークで，真の最短距離との相対誤差が10%以下に抑えられており，結構上手く近似できているようです．