Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency - todo314 @ ウィキ

Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency

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

概要

• RIS (SODA'14)を実用的に改良するよ！
• 提案手法 TIM, TIM+
  • サンプリング回数をいい感じにしました。
  • $$ O(\epsilon^{-2}(k+\ell)(n+m)\log n) $$時間
  • ヒューリスティックで更に効率改善→TIM+
• triggeringモデルにも拡張したよ

提案手法 Two-phase Influence Maximization (TIM)

1. フェーズ1：サンプリング回数θを決める
2. フェーズ2：RR集合をθ回サンプルして、貪欲アルゴリズムを走らせる

必要なサンプリング回数

• $$ \theta \geq (8+2\epsilon)n \cdot \frac{\ell \log n + \log {n \choose k} + \log 2}{OPT_k \cdot \epsilon^2} $$ならば、
• 確率$$ 1-n^\ell / {n \choose k} $$以上で、全ての高々k頂点集合について、絶対誤差が$$ \epsilon OPT_k/2 $$以下
• 出来るだけ正確な（k頂点集合の）最適値OPTを求められたら勝ち

OPTの下限推定

• 案①: 単一頂点の影響拡散の重み付き和
  • $$ \mathbf{E}_{v \sim \mathcal{D}}[I(\{v\})] = \frac{n}{m}EPT $$
    • ただし、Pr[vを標本する]∝ (vの入次数)
    • EPTは一回のRR集合サンプルで見る辺の数の期待値
  • 漸近的には良いけど、kが大きい時にはOPT_kとの差が出る
• 案②: k頂点集合の影響拡散の重み付き和
  • $$ KPT \equiv $$ k頂点集合（無作為）の影響拡散の期待値
  • これを直接は計算しない
  • $$ KPT = n \cdot \mathbf{E}_R\left[ 1-\Bigl( 1-\frac{w(R)}{m} \Bigr)^k \right] $$
    • w(R)は見た辺の数
  • KPTの推定…RR集合の数を倍々にしながら頑張る（保証付き）

改善TIM+

• もうちょっとヒューリスティックで良くする
• KPTを推定→KPT*
• KPT*個のRR集合上で貪欲→S'
• S'の影響拡散を"別の"KPT*個のRR集合で推定→KPT'
• return max{KPT*, KPT'}

実験

• 辺確率：1/入次数「だけ」
• 比較手法：RIS, CELF++, IRIE, SIMPATH
• データセットによっては、kが大きい方が実行時間が短い時がある
  • 推定の精度の問題っぽい

まとめ

• 読み直したらそれ程はやばくない
• 実験がちょっと適当

SIGMOD 影響最大化

2017/10/01