Inferring the Underlying Structure of Information Cascades
-
Bo Zong, Yinghui Wu, Ambuj K. Singh, Xifeng Yan
-
ICDM 2012
概要
-
ICモデルのカスケードが部分的に与えられる
-
どういう経路を辿ったかの木を知りたい
-
時刻が厳密に一致する場合とそうでない場合の問題を定式化
-
難しいけど頑張って解く
-
実験したらいい感じ
問題定式化
-
カスケード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だけ残す
-
後は、何か複雑なことをしてボトムアップに構築
bounded treeでのアルゴリズム
-
NP-completeだけど近似できるらしい
-
できるだけ小さい辺を使って貪欲にくっつけていく感じ?
実験
-
適当なグラフとカスケードを持ってくる
-
伝播確率はEMアルゴリズムで推定
-
何%カスケードを残すかを考える
-
真のカスケードとの一致率で判定
-
適当なベースラインは当然だめで、提案手法はそこそこ
まとめ
-
木を出力するのはどうなんだろうか…
-
ICモデル自体が確率的なので、その辺でカスケードした確率を答えさせる方が良さそうに思った
-
もう少し調べるか…
ICDM information diffusion
2014-02-12 00:11:34 (Wed)
最終更新:2014年02月12日 00:11