Time Constrained Influence Maximization in Social Networks

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
    • Sとuを固定した時の確率は若干めんどい
  • marginal influenece spreadを高速に計算するの(MISP)も提案

実験

  • 伝播確率は入次数の逆数
  • 遅延はポアソン分布
    • 一応上の設定は提案手法とは関係無いことを明示している
  • MISPはθを小さくしても結構速いしいい感じのシードを出しているらしい
  • kにもあまり影響されない

まとめ

  • 遅延が適当な分布で発生するのはなるほどそうかな~という感じ
  • 伝播確率は変わらないのね

ICDM influence maximization modeling

2014-03-15 05:50:29 (Sat)

最終更新:2014年03月15日 05:50