Suggesting Ghost Edges for a Smaller World - todo314 @ ウィキ

Suggesting Ghost Edges for a Smaller World

• Manos Papagelis, Francesco Bonchi, Aristides Gionis
• CIKM 2011

問題 平均最短経路長最小化

• G: 連結無向グラフ
• R⊆V×V-E(G) (|R|≦k)で
• 平均最短経路長L(V,E∪R))を最小化したい
  • 候補がO(n^2)あるので大変

手法

1. 貪欲
   • k回×n^2候補辺×n^3(WF)=O(kn^5)
     • やばお
2. ヒューリスティック
3. ヒューリスティック+標本抽出

実験

• |V|<3K, |E|<8K
• 適用的な貪欲が一番良い
• 速度：貪欲は遅い
  • ヒューリスティックはぼちぼち速い？（グラフ小さいし…）

まとめ

• 劣モジュラでも優モジュラでもない（はず）なので難しそう
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition (APPROX-RANDOM'09)は見といたほうが良さそう
• これも頭のいい（ry

CIKM 平均最短経路長最小化

2015/06/23 19:53