Scalable Influence Estimation in Continuous-Time Diffusion Networks

Scalable Influence Estimation in Continuous-Time Diffusion Networks

  • Nan Du, Le Song, Manuel Gomez-Rodriguez, Hongyuan Zha
  • NIPS 2013

概要

  • 連続時間拡散モデルで影響最大化
  • Cohenのフレームワークで全頂点の影響力を高速に計算
  • ICML'12に勝利!

問題定義

  • $$ f_{ji}(t_j \mid t_i) = f_{ji}(t_i - t_j) $$
    • つまり遅延時間がある分布に従う
  • t_i: 感染時間
  • $$ \sigma(A,T) = \mathbf{E}[\sum_{i \in V} [\![t_i \leq T]\!]] = \sum_{i \in V} \Pr[t_i \leq T] $$
    • つまり,距離T以内で到達できる頂点数の期待値
  • 頂点当: $$ O(E+V\log V) $$
  • 全頂点: $$ O(VE + V^2 \log V) $$
  • これを標本数×シード数回やるのはやばい

提案手法

  • 全頂点を$$ O(E \log V + V \log^2 V) $$で
  • $$ N(s,T) = \{ i \mid g_i(\{\tau_{ji}\}) \leq T \} $$
    • sから距離T以下で到達可能な頂点集合
  • $$r_i$$: 頂点iの乱ラベル
  • $$ r_* := \min_{i \in N(s,T)} r_i $$
  • 分布$$ r_i \sim \exp(-r_i) $$なら
  • 分布$$ r_* \sim \exp(-|N(s,T)|r_*) $$
  • mラベルとれば$$ |N(s,T)| \approx \frac{m-1}{\sum_{u} r_*^u} $$
    • 全頂点についてやるには,r_iの小さい順に逆向きにやる奴
  • 後は普通
  • 複数シードの場合: $$ r_* = \min_{i \in A} \min_{j \in N(i,T)} r_j $$

実験

  • 普通

まとめ

  • シンプルだけど,まぁスマート

NIPS 影響最大化 時変モデル

2016/02/23

最終更新:2016年02月23日 23:56