Inferring Networks of Diffusion and Influence

Inferring Networks of Diffusion and Influence

  • Manuel Gomez-Rodriguez, Jure Leskovec, Andreas Krause
  • In KDD 2010
  • よしださん

概要

  • ネットワークは明示的に得られない
    • 薬物乱用者の注射針共有ネットワーク
  • 分かるのは現象、結果だけ
  • 結果からネットワークを推定できる?
  • 結果: O(n^2)時間でできる
    • グラフの候補は2^n*n通り

拡散モデル

  • 伝播時間: 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なので、貪欲に辺を選ぶ、というアルゴリズムを遅延評価付きでやる

実験

  • かなり良い
  • 10^4頂点を数時間

KDD information diffusion

2013-11-01 23:49:22 (Fri)

最終更新:2013年11月01日 23:49