Inferring the Underlying Structure of Information Cascades

Inferring the Underlying Structure of Information Cascades

  • Bo Zong, Yinghui Wu, Ambuj K. Singh, Xifeng Yan
  • ICDM 2012

概要

  • ICモデルのカスケードが部分的に与えられる
    • 時刻tにuがアクティブになったみたいな
  • どういう経路を辿ったかの木を知りたい
  • 時刻が厳密に一致する場合とそうでない場合の問題を定式化
  • 難しいけど頑張って解く
  • 実験したらいい感じ

問題定式化

  • カスケードC
    • 根付き木で時刻がある
  • bounded consistent tree
    • 木上での根sから頂点v_iまでの距離が観測時刻t_i以下
    • d(s,v_i)≦t_i
  • perfect consistent tree
    • 木上での根sから頂点v_iまでの距離が観測時刻t_iに一致
  • minimum weighted consistent tree
    • consistent treeの尤度を定義
    • 木に含まれる辺uvについて、log p(u,v)の総和をとったもの
  • minimum consistent tree
    • 辺の数を最小化(?)
  • 難しさ: NP-completeでAPX-hard

perfect treeでのアルゴリズム

  • 前処理: d(s,v_j)+d(v_j,v_i)≦t_iなv_jだけ残す
    • v_jを通るべきでない奴は全部消す
  • 後は、何か複雑なことをしてボトムアップに構築

bounded treeでのアルゴリズム

  • NP-completeだけど近似できるらしい
  • できるだけ小さい辺を使って貪欲にくっつけていく感じ?

実験

  • 適当なグラフとカスケードを持ってくる
  • 伝播確率はEMアルゴリズムで推定
  • 何%カスケードを残すかを考える
  • 真のカスケードとの一致率で判定
  • 適当なベースラインは当然だめで、提案手法はそこそこ

まとめ

  • 木を出力するのはどうなんだろうか…
  • ICモデル自体が確率的なので、その辺でカスケードした確率を答えさせる方が良さそうに思った
    • 難しそう
  • もう少し調べるか…

ICDM information diffusion

2014-02-12 00:11:34 (Wed)

最終更新:2014年02月12日 00:11