「Simulated Annealing Based Influence Maximization in Social Networks」の編集履歴（バックアップ）一覧はこちら

「Simulated Annealing Based Influence Maximization in Social Networks」(2013/10/03 (木) 19:26:15) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

- 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に勝っているというのもおかしい
-- σの計算を端折っているにも関わらず


&tags()