Outward Influence and Cascade Size Estimation in Billion-scale Networks - todo314 @ ウィキ

Outward Influence and Cascade Size Estimation in Billion-scale Networks]]

• Hung T. Nguyen, Tri P. Nguyen, Tam N. Vu, Thang N. Dinh
• SIGMETRICS 2017 （会議）
• Proceedings of the ACM on Measurement and Analysis of Computing Systems 2017 （ジャーナル）

概要

• 影響力推定の新しい指標outward influenceを作ったよ！…E[拡散サイズ]-|シードサイズ|
  • 相対誤差を保証するのが難しい
• 高速アルゴリズムを作ったよ
  • カスケードが小さくなり過ぎようにimportance samplingをします
  • Influence at Scale: Distributed Computation of Complex Contagion in NetworksよりΩ(log^4 n)倍速いよ！

定義・性質・予備知識

• outward influenceの定義：$$ I_{o}(S) = I(S)-|S| $$
  • 劣モジュラだけど、非単調
• 常に$$X_i \leq b$$なら、$$ O(\frac{1}{\epsilon^2} \ln (\frac{2}{\delta}) \frac{b}{\mu_X}) $$回のサンプリングでいつもの近似を達成できる
  • outwardは$$ \mu_X \approx 0 $$な時があり、やばお

アルゴリズム

importance sampling

• 条件付け＝Sの近傍の一つ以上が活性化する

1. Sの出近傍 $$\ell$$ 頂点を（適当に）順序付け
2. $$A_i = ``v_1, \ldots, v_{i-1}までは失敗、v_iで成功 ''$$
   • $$A_i$$同士は互いに素
   • $$ A_{\ell+1} $$は全てが失敗
3. $$ A_1,\ldots,A_\ell $$で正規化して確率的に選ぶ
   • $$ A_{\ell+1} $$の分だけ得する
4. $$ v_{i+1},\ldots,v_{\ell} $$は改めてサンプリング
5. 普通にサンプリング

• (期待値1以上の部分)×(条件付けの確率)

更に効率化

• $$\mathcal{AA}$$アルゴリズム [Dagum-Karp-Luby-Ross. SICOMP'00]を適用
• "a technical error in its proof"とか言っているけどホントか？
• サンプリング列が2つ必要らしい
• 最終的に計算時間が複雑だけど、$$ O(\frac{n \log(2/\delta)}{\epsilon^2}) $$らしい…

実験

• 比較手法：Monte-Carlo、KDD'15
• 辺確率：1/入次数、定数(0.1, 0.01, 0.001)
• 相対誤差の分布を見てみる（0で一致）
  • 0でspikeしてかなりいい感じ
  • oO(outward influenceならまぁそうだなぁという感じ)
• influence spreadも見てみる
  • 相対誤差がかなりいい感じ（平均も最悪も）

まとめ

• importance samplingはまぁ悪くない
• $$\mathcal{AA}$$アルゴリズムの部分は謎
• 実際に追実験しないと何とも言えない…

SIGMETRICS 影響拡散 影響最大化

2017/10/01