Inferring Networks of Diffusion and Influence (KDD'10)

• 目には見えないネットワーク，現象の結果は目に見える
• 目に見える情報からネットワークを推定可能か？

• カスケードの拡散モデルの定義
  • 枝：伝搬確率，伝搬時間の分布
  • 有向木，ただ１つの親
• カスケードに対するグラフの尤度を定義
  • 確率
• グラフの尤度の効率的な計算
  • 行列木定理！！ 尤度は O(n^3) で計算可能
• 尤度を最大化するグラフの効率的な計算
  • グラフを見つけるのはむずいので別の定式化をしよう
  • 和じゃなくて max でいいや → 最大有向全域木
  • 劣モジュラ性 → greedy
• 実験
  • 人口データはうまくいった
  • 実データは orz