Influence Maximization in Near-Linear Time: A Martingale Approach - todo314 @ ウィキ

Influence Maximization in Near-Linear Time: A Martingale Approach

• Youze Tang, Yanchen Shi, Xiaokui Xiao
• SIGMOD 2015

概要

• TIMInfluence Maximization: Near-Optimal Time Complexity Meets Practical Efficiencyから更に改善しました
• 直接最適値の下限を推定するよ！
• TIMよりめっちゃ速くなった

TIMの問題点

1. 最悪時には下限が最適値よりn/k倍悪い
2. 下限の計算自体が結構（シード選択段階よりも）遅い

提案手法 Influence Maximization via Martingales (IMM)

• 違い
  1. RR集合を使いまわしていい
     • TIMでは独立でないと駄目
  2. 必要なRR集合の個数が少し改善（見た目が複雑だけど）
  3. 直接OPT_kの下限を推定
     • HINT：「最適値が大きい？」の検証に必要なRR集合の個数は小さい
• アルゴリズム
  1. 下限の候補値$$ x = n, n/2, n/4, \ldots $$
  2. $$ \lambda' / x $$個になるまでRR集合をサンプル
     • 倍々に増やすが使いまわす
  3. $$ ``下限 > x?'' $$を検証
     • 貪欲した解の影響拡散（の推定値）が(1+ε')x以上か確認
  4. yesだったら下限を適当に計算して抜ける
  5. $$ \theta = \lambda^* / 下限 $$としていつものをやる

そのた

• Reverse Influence Setを提案
  • RIS的な手法が使える条件を拡大
• 連続時間モデルへの適用例
  • RI集合は距離T以内で行ける所、なので、Dijkstra的な事をすればOK

実験

• 辺確率：1/入次数 ٩(๑òωó๑)۶
• 比較手法：TIM,TIM+,IRIE,SIMPATH
• ε=0.5ってでかくね？

まとめ

• はい。

SIGMOD 影響最大化

2017/10/01