Inferring Networks of Diffusion and Influence
-
Manuel Gomez-Rodriguez, Jure Leskovec, Andreas Krause
-
In KDD 2010
概要
-
ネットワークは明示的に得られない
-
分かるのは現象、結果だけ
-
結果からネットワークを推定できる?
-
結果: O(n^2)時間でできる
拡散モデル
-
伝播時間: P(Δ)∝exp(Δ/α) or 1/Δ^α
-
u->v の伝播の尤度を設定
-
外部からの伝播もあり
-
特定のカスケードに対して有向木Tの尤度を各辺について掛け合わせる
-
↑をカスケード集合について掛けあわせたら全体の尤度
-
$$ P(C|G) = \prod_{x \in C}P(c|G) $$
-
$$ P(c|G) = \sum_{T \in {\cal T}(G)}P(c|T)P(T|G) $$
-
P(C|G)が一番小さくなるようなk辺?以下のグラフを作りたい!!
-
P(c|G)は行列木定理を使うとO(n^3)
-
ちょっと変えてグラフGのスコアを最大対数尤度に変更
-
↑最大有効全域木の重み
-
$$ F_c(G) = \max_{T \in {\cal T}(G)} \log P(c|T) = \max_{T \in {\cal T}(G)} \sum_{(i,j) \in T}\log P_c(i,j) $$
-
この関数はsubmodularなので、貪欲に辺を選ぶ、というアルゴリズムを遅延評価付きでやる
実験
KDD information diffusion
2013-11-01 23:49:22 (Fri)
最終更新:2013年11月01日 23:49