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への伝搬は最短経路だけを考える
-
しきい値θ以下の伝搬は無視する
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
伝播モデル
-
weighted cascade
-
trivalency
結果
-
良い、割りと速い
-
メモリ使用量(最短経路木の大きさ)
-
実行時間
結論
まとめ
-
なんかすごそう感あるアルゴリズムだったが、最短経路木だけでいいのか?と思い始めた
最終更新:2013年10月10日 00:11