Social Influence Spectrum with Guarantees: Computing More in Less Time - todo314 @ ウィキ

Social Influence Spectrum with Guarantees: Computing More in Less Time

• Dinh, Thang and Nguyen, Hung and Ghosh, Preetam and Mayo, Michael
• CSoNet 2015

概要

• 新しいアルゴリズムLISA
  • $$k=1,\ldots,n$$について同時に解けるよ！
  • $$ O(\epsilon^{-2}\ln \frac{2}{\delta} (n+m)) $$時間だよ！

提案手法 Linear-time Influence Spectrum Algorithm (LISA)

• 終了条件が重要

1. $$ \Upsilon_L = 1+4.6\epsilon^{-2} \ln \frac{2}{\delta} $$
2. $$\mathcal{R} \leftarrow$$ RR集合をサンプル
3. $$ \max_{v}F_{\mathcal{R}}(v) \times |\mathcal{R}| \geq \Upsilon_L $$となったら終了

• 貪欲した結果を1－nまで全部返す
• 証明の戦略
  • 貪欲解$$S_k$$と最適解$$S_k^*$$の推定がどれほど近いかを示す
  • $$ F_{\mathcal{R}}(S_k) $$ vs. $$ \mathsf{Inf}(S_k) $$
  • $$ F_{\mathcal{R}}(S_k^*) $$ vs. $$ \mathsf{Inf}(S_k^*) $$
• 時間計算量は自明（サンプル一回の時間とかをバウンドすればOK）
• $$k=1,2,\ldots,n$$について一度に保証OKらしい…

実験

• データセット：NetHEPT, NetPHY, DBLP, Twitter
• 比較手法：CELF++, SIMPATH, LDAG, TIM+
• 拡散モデル：もしかしてLTだけ？

まとめ

• ホントか？
• $$S_k$$が$$\mathcal{R}$$に依存しているので駄目だったりしそう？

CSoNet 影響最大化

2017/10/01