QUBE: a quick algorithm for updating betweenness centrality

Min-Joong Lee, Jungmin Lee, Jaimie Yejean Park, Ryan Hyun Choi, and Chin-Wan Chung. 2012. QUBE: a quick algorithm for updating betweenness centrality. In Proceedings of the 21st international conference on World Wide Web (WWW '12). ACM, New York, NY, USA, 351-360. DOI=10.1145/2187836.2187884 http://doi.acm.org/10.1145/2187836.2187884

論文読み再開だよ． WWW なのに (?) フツーにグラフアルゴリズムの論文．

• 問題
  • グラフの更新があるよ
  • betweenness centralityを全頂点について保持したい，効率的に update できる？
  • 既存研究ナシ
• アプローチ
  • 更新があり得る頂点集合というのを計算＆更新することができる
  • その部分だけ効率的に再計算する
• くわしく (斜め読み)
  • その頂点の Minimum Union Cycle のとこだけが更新され得る？
  • Minimum Cycle Basis とは，Cycle Basis であって，重みの和最低のもの
  • Minimum Union Cycle とは，Minimum Cycle Basis のサイクル達の頂点集合を頂点を共有する者たちを併合したもの
• 実験結果
  • うまいデータでは数十倍はやくなるが，それでも数千頂点で１０秒とかかあ
  • 半分ぐらいのデータではナイーブな再計算に比べ 2〜6 倍しか速くなっていない