Efficient Influence Maximization in Social Networks - todo314 @ ウィキ

• Efficient Influence Maximization in Social Networks
• Wei Chen, Yajun Wang, Siyu Yang
• In KDD
• 2009

概要

• Wei Chen 劇場の始まりっぽい
• influence maximization のアルゴリズムを2つ提案
  • greedy based algorithm の高速化
  • ヒューリスティックによるinfluence spreadの近似

アルゴリズム

NewGreedyIC

• seedを選ぶためにグラフをR=20000個作る
• Sから到達可能なノードは省く
• vから到達可能なノード数を計算、これがmarginに相当
  • これの計算は自明ではないが論文ではlinearでできるとかほざいている
  • 行列の演算は無理だねー
• R個の和が最大のノードをseedに加える

• 計算量: O(kRm)
  • と書かれているがさすがに嘘だと思う

DegreeDiscountIC

• influence spreadを近傍だけから近似
• $$ 1+(d_v-2t_v-(d_v-t_v)t_vp+o(t_v))p $$
  • こんな感じ
  • $$ d_v $$: vの次数
  • $$ t_v $$: カウンターみたいなの

• 計算量: O(klogn+m)

実験

グラフ

高エネルギー物理理論の共著ネットワーク

• NetHEPT
  • |V|=15K,|E|=59K
• NetPHY
  • |V|=37K,|E|=232K

結果

influence spread

• NewGreedyICはCLEFと同じ
• DegreeDiscountICはものによるけど良さそう（と主張）

実行時間

• NewGreedyICはCELFとあんまり変わらない
  • 混ぜるとちょびっとだけ早くなった
• DegreeDiscountICはめっちゃ速い

結論

• ヒューリスティックという方向性は有り
• 問題をもう少し現実的？にする

まとめ

• NewGreedyICはあれでいいのか？という位高速化されて「いなかった」
• それっぽい解析があればいいのかなあ
• DDも定理の仮定がひどいと思う（実際には多分成立しない

KDD influence maximization