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] $$
-
頂点当: $$ 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 \} $$
-
$$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