「Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale ...」の編集履歴（バックアップ）一覧はこちら

「Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale ...」(2013/10/10 (木) 00:11:27) の最新版変更点

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

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

Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks
- Wei Chen, Chi Wang, Yajun Wang
- In KDD
- 2010

* 概要
- MIAモデルというのを使ってinfluence maximizationを高速化

* アルゴリズム
** maximum influence paths (MIP)
- v->uへの伝搬は最短経路だけを考える
- しきい値θ以下の伝搬は無視する
-- Dijkstraの途中で打ち切る

** maximum influence arborescence model
influence spreadを以下で近似
$$ \sigma_M(S) = \sum_{v \in V}ap(v,S,MIIA(v,\theta)) $$
- MIIA(v,θ): vからの最短経路木、ただしθ以下の確率は打ち切ってある
- ap(,,): Sがvをactivateする確率を最短経路木に沿って求める関数
- 再計算とかに工夫を入れて高速化

* 実験
** グラフ
- NetHEPT,DBLP,Epinions,Amazon
-- |V|=15K~655K,|E|=31K~2M
** 伝播モデル
- weighted cascade
- trivalency

** 結果
- 良い、割りと速い
- メモリ使用量（最短経路木の大きさ）
-- O(√1/θ)っぽい
- 実行時間
-- O(1/θ)っぽい

* 結論
- 並列化

* まとめ
- なんかすごそう感あるアルゴリズムだったが、最短経路木だけでいいのか？と思い始めた