CINEMA: Conformity-Aware Greedy Algorithm for Influence Maximization in ... - todo314 @ ウィキ

CINEMA: Conformity-Aware Greedy Algorithm for Influence Maximization in Online Social Networks

• Hui Li, Sourav S Bhowmick, Aixin Sun
• EDBT 2013

Contribution

1. conformity-aware cascade model(c^2 model) の提案
2. mag-list というデータ構造
3. CINEMA (Conformity-aware INfluEnce MAximization)
   • 部分グラフに分割する←a novel approach ???

何が問題なの？

• ぶっちゃけよく分からん
• とにかく普通のIC・LTモデルはダメでconformityを考慮せねばならんらしい
  • 別にp_uvを個別にちゃんと設定すればいいんじゃね？

Conformity-Aware Cascade Model

• 確率を$$ 1 - \prod_{u \in A_i: (u, v) \in E}[1 - \Phi(u)\Omega(v)] $$とする

CINEMA

• グラフを分割して、カスケードがそれぞれの中で閉じているとする
  • ほんとかよ
  • うまく分割できなかったら何か調整する
• 合計でk個選ぶ問題とすると、これもサブモジュラ
• ゲインの一番でかい部分グラフから頂点をとってくる
• mag-listというデータ構造で頑張る
• ゲインの更新もこれまた頑張る

実験

• データセット
  • |V|=15K~2M, |E|=60K~5M
• 比較手法
  • MixGreedy, DegreeDiscount, MIA, LDAG, SimPath
  • Wei Chenばっかじゃないか！
• 速度はあんまりMixGreedyと変わらん
  • Wiki-talkで動くのか！？これ
  • 100時間らしい

感想

• 特に見どころ無し