IRIE: Scalable and Robust Influence Maximization in Social Networks - todo314 @ ウィキ

• IRIE: Scalable and Robust Influence Maximization in Social Networks
• Kyomin Jung, Wooram Heo, Wei Chen
• In ICDM
• 2012

概要

• Influence maximizationを超高速に求めるアルゴリズムを開発
• しかもロバストに良い解を発見する

アルゴリズム

$$ \sigma(S \cup \{v\}) - \sigma(S) $$を次で近似する

$$ r(v) = (1-AP_S(v))\left[ 1+\alpha \sum_{vu}p_{vu}r(u) \right] $$

• AP_S(v): Sがvをactivateする確率
  • $$ AP_S(v) - \sum_{s \in S}AP_s(v) $$
  • で$$ AP_s(v) $$は$$ d_e=-\log p_e $$をコストとする最短経路長（dijkstra）
• α: 補正係数、実験では0.7

• つまり、vをseedに加えたことによるマージンを（vがSによりactiveにならない確率）×（vがactiveにするノード数）で表した。
  • 当然正しくはない。αは適当感ある。
• この式を収束するか、ある程度反復させたら終了する。
• あとはgreedyに選ぶ

実験

グラフ

• 最大はLiveJournal
  • |V|=4.8M、|E|=69M

確率モデル

• weighted cascade
  • $$ p_vu=1/d_u $$
• trivalency
  • 0.1,0.01,0.001から一様に選ぶ

結果

速度

• |E|に比例するので、かなり速い
  • $p_e$に依存するのは確率が大きくなると遅くなったり、メモリが足りなくなったりする
• 実データでも、速い
  • LiveJournalで1000s

influence spread

• original greedy 程ではないが、他の既存手法よりよい（と主張）
• 結構な数の手法と比較しているという意味ではよい

まとめ

• アルゴリズムの妥当性については全くといっていいほど触れられていないのが気になった
• 実験結果を見る限りでは良さそうに見えるが怪しい
• 途中で行列による議論をしていたが意味はなんだろう・・・？

ICDM influence maximization