Holistic Influence Maximization: Combining Scalability and Efficiency with ... - todo314 @ ウィキ

Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models

• Sainyam Galhotra, Akhil Arora, Shourya Roy
• SIGMOD 2016

概要

• 新しいモデル opinion-cum-interaction
• 高速アルゴリズム
  • OSIM：OI用
  • EaSyIM：普通の影響最大化用
• 5%くらい質が悪いけど、良いよ！

モデル

• 省略します

  　　,r´⌒ヽ,⌒ヽ,ヽ
  　　　(⌒)､　　 .人　 λ＼､ .＿＿＿
  　　　 ＼. ＼　　　　、　ヽ.／ ー 　ー＼
  　　　　 |＼　＼ 　 　ヽ.／　（ ●）　（ ●）
  　　　　 |　 ＼　 ＼　／　　　　　（__人__） ＼　 
  　　　　 |.　　 ＼　 　|　　　　　　　｀ ⌒´ 　　|
  　　.　　 |.　　　|.＼_ノ＼ 　　　　 　　　　　　/
  　　.　　 |.　　　|　　 | 　 ＼＿＿＿＿＿_／
  　　.　　 |　　　)　　.|　 　　　　￣￣
  　　.　　 |　　　|　　.|
  　　　　　|　　 |.|　 .|
  　　.　　　|　　| .|　.|
  　　　　 ／ 　/ /　ヽ,
  　　　　(＿_ノ　 ヽ、__つ
  

アルゴリズムEaSyIM

• 影響拡散っぽいスコアを割り当てて貪欲するよ！
• $$ \Delta^i(u) \leftarrow \Delta^i(u) + p_{(u,v)}(1+\Delta^{i-1}(v)) $$を全体について実行×l反復
  • 気分としては、uから始まる長さ高々iの経路の重み和をボトムアップに求める感じ
  • 1が前の内容を保持する感じ
• つまり、$$ \mathbf{\Delta}^i = \mathbf{P}(\mathbf{1} + \mathbf{\Delta}^{i-1}) = \mathbf{P} + \mathbf{P}^2 + \cdots + \mathbf{P}^l $$
• 解析
  • DAGの時こんな感じですよ～みたいなよくある奴
• O(kl(m+n))時間、lは直径以下のパラメタとする

実験

• 辺確率：0.1と1/入次数
• TIM, CELF++と比較
• lを上げるとぼちぼち精度があがるっぽい
• soc-LiveJournalでTIMよりいい感じですよ、でもめっちょ時間かかっている

まとめ

• スコアの所は、アルゴリズムでは無くて、数式で普通に書いてくれれば良いなと思う。。。
• 別に難しい所は無い。

SIGMOD 影響最大化

2017/10/01