-
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
SAEDV (Expected Diffusion Value)
Aによりactivateされるノード数の期待値は
$$ |A| + \sum_{v \in N^{out}(A), \not \in A}1-(1-p)^{r(v)} $$
実験
グラフ
-
Mobile,Epinions,Web,Amazon
-
|V|: 76K~345K
-
|E|: 422K~1.33M
パラメータ
結果
influence spread
実行時間
-
かなり速い
-
数秒から半分程度で終わる
-
DegreeDiscountより速いのはさすがにおかしいのでは?
結論
-
新しい手法を提案
-
state-of-the-artを完封
-
並列計算?
-
SA用の最適化を加えて更にパフォーマンスアップ
まとめ
-
さすがにおかしいのでは?
-
速すぎるというのもおかしい
-
influence spreadでgreedyに勝っているというのもおかしい
AAAI influence maximization
最終更新:2013年10月03日 19:26