Importance Sketching of Influence Dynamics in Billion-scale Networks - todo314 @ ウィキ

Importance Sketching of Influence Dynamics in Billion-scale Networks

• Hung T. Nguyen, Tri P. Nguyen, NhatHai Phan, Thang N. Dinh
• ICDM 2017

概要

• RR集合のImportance sampling版を作った
• 既存のRISベースの手法に適用できますよ
• とても速いです

動機づけ

• 単一頂点からなるカスケードが良く発生する
  • メモリ消費✘処理時間✘推定効率✘
• 独立カスケードの場合
  • WCなら30%くらい、TRIなら90%くらいはsingular

枠組み$$\mathsf{SKIS}$$ と Importance Influence Sampling ($$\mathsf{IIS}$$)

• ぶっちゃけ SIGMETRICS'17 Outward Influence and Cascade Size Estimation in Billion-scale Networks と同じ
• 影響力推定はちょっとだけ補正する
  • (IISでの被覆)*(どれか成功する確率)+(単一点で終わる確率の総和)
• Γ=(普通にやったときにどれか成功する確率)とすると、
• Γが小さいほうが得する；普通のサンプリングに比べて$$ \Theta(\frac{\Gamma}{n}) $$倍得する
• ただのCoverageなので、貪欲をそのまますればOK
  • そのままIMMとかD-SSAに適用できる
• 線形閾値、連続時間にもかんたんに拡張できるよ

実験

• 比較手法：RIS、SKIM、PMC、IMM、D-SSA、D-SSA+SKIS
• 辺確率：WCとTRI
• 影響力推定
  • RIS、SKIMより平均相対誤差がとても良くなったよ！
  • 分布を見ても安定しているよ！
• 影響最大化
  • D-SSA+SKISはD-SSAより何倍か良い
  • 何かD-SSA速くない？
  • PMCとIMMは、WCではIMM、TRIではPMCが速い（それはそう）

まとめ

• 実質importance samplingをIC用に提案しただけだなぁ…。

ICDM 影響拡散 影響最大化

2017/10/02