Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale ... - todo314 @ ウィキ

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/θ)っぽい

結論

• 並列化

まとめ

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