Computing Top-k Closeness Centrality Faster in Unweighted Graphs - todo314 @ ウィキ

Computing Top-k Closeness Centrality Faster in Unweighted Graphs

• Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi, Andrea Marino, Henning Meyerhenke
• ALENEX 2016

概要

• 近接中心性の上位k頂点を厳密に得たい
• 値が似通っているので，近似だと不十分
• 2種類の距離和の下限を使った簡単な枝刈り手法を提案
• 実験したら既存の枝刈り手法より探索辺数の意味で良かった

提案手法

戦略

• 各頂点からの距離和の下限を計算
• 下限の小さい順に見ていって遅延評価的にBFSをして確定させていく
• 最悪でn回BFSする

階層に基づく下限

• どこかの頂点sからBFSする
• 三角不等式でd(v,w)を見積もる
  • 距離1は近傍で，距離2は適当にやると，もう少しタイトになる
• 距離は高々直径までなので，全頂点で(直径)^2+(線形)時間以下でできる
• 有向グラフも大体似た感じ

近傍に基づく下限

• #vから距離dの経路≧#vから最短距離dの頂点
• 経路数は全頂点についても，m×(直径)時間くらいでできる

その他高速化

• 階層に基づく下限を途中で更新する
  • 何かの頂点からのBFSを終えたら同様に加減を計算できる
• CutClos（既存手法）を導入
  • 暫定k番目のスコアを超えたら途中でBFSを打ち切る
• ただし，両者は共存しないように見える…

実験

• 道路と複雑
• nm/(探索辺数)はかなりでかい，数万まで行く
• kが大きくなると流石に辛くなる

困難性

• SETHの元で最高中心性を持つ頂点の計算は$$O(m^{2-\epsilon})$$時間は達成できない

まとめ

• 厳密は大変だなあ
• 道路ネットワークで中心性をやるモチベが謎なので調べる
• もっと沢山手法が提案されてそうだけど，あんまないのかな
• どれが効果的とかの実験結果が論文中には少なめ

ALENEX 近接中心性

2016/05/03