Time Constrained Influence Maximization in Social Networks
-
Bo Liu, Gao Cong, Dong Xu, Yifeng Zeng
-
ICDM 2012
-
※Wei ChenのTime-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Processとは独立らしい
概要
-
時間制限付きinfluence maximizationを提案
-
NP-hardだけどmonotoneかつsubmodular
-
Influence Spreading Pathという速いアルゴリズムを提案
-
実験して提案手法とベースラインを比較
モデル・問題定義
Latency Aware Independent Cascade (LAIC) Model
-
uは時刻tにactiveになったとする
-
近傍のvを時刻t+δに確率p_uv*p_u^lat(δ)でactiveにする
-
遅延時間は(有限?)確率分布から選ばれる
Time Constrained Influence Maximization Problem
-
入力: グラフ,伝播確率p_uv,潜伏分布p_u^lat,時間制限T,シードサイズk
-
時刻Tまでにアクティブになる頂点数σ_T(S)を最大化
-
NP-hardでmonotoneでsubmodular
-
シミュレーションは時刻が非負整数なら下から数え上げれば線形で済む
Influence Spreading Path
-
MIAと大体同じコンセプト
-
長さがT以下で,確率がθ以上のパスを持っておく
-
Sから各uへのいろんなパスの発生確率を独立に足し合わせればOK
-
marginal influenece spreadを高速に計算するの(MISP)も提案
実験
-
伝播確率は入次数の逆数
-
遅延はポアソン分布
-
一応上の設定は提案手法とは関係無いことを明示している
-
MISPはθを小さくしても結構速いしいい感じのシードを出しているらしい
-
kにもあまり影響されない
まとめ
-
遅延が適当な分布で発生するのはなるほどそうかな~という感じ
-
伝播確率は変わらないのね
ICDM influence maximization modeling
2014-03-15 05:50:29 (Sat)
最終更新:2014年03月15日 05:50