Simulated Annealing Based Influence Maximization in Social Networks - todo314 @ ウィキ

• Simulated Annealing Based Influence Maximization in Social Networks
• Qingye Jiang, Guojie Song, Cong Gao, Yu Wang, Wenjun Si, Kunqing Xie
• In AAAI
• 2011

概要

• influence maximizationに対する初の焼きなましベースアルゴリズム
• influence spreadを高速に近似計算

アルゴリズム

SA based

• 適当にseed setを変更するだけ

SAEDV (Expected Diffusion Value)

Aによりactivateされるノード数の期待値は

$$ |A| + \sum_{v \in N^{out}(A), \not \in A}1-(1-p)^{r(v)} $$

• r(v): Aからvにある辺の数

実験

グラフ

• Mobile,Epinions,Web,Amazon
• |V|: 76K~345K
• |E|: 422K~1.33M

パラメータ

• p: 0.01,0.02,…,0.09
  • 割と普通

結果

influence spread

• 概ね良好
  • greedyより良いのもある（？）

実行時間

• かなり速い
  • 数秒から半分程度で終わる
  • DegreeDiscountより速いのはさすがにおかしいのでは？

結論

• 新しい手法を提案
• state-of-the-artを完封
• 並列計算？
• SA用の最適化を加えて更にパフォーマンスアップ

まとめ

• さすがにおかしいのでは？
• 速すぎるというのもおかしい
• influence spreadでgreedyに勝っているというのもおかしい
  • σの計算を端折っているにも関わらず

AAAI influence maximization