Time-Critical Influence Maximization in Social Networks with Time-Delayed ... - todo314 @ ウィキ

Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process

• Wei Chen, Wei Lu, Ning Zhang
• AAAI 2012

概要

• ICモデルは時間制限を設けないからダメ
• 締切＋時間の遅延付きモデルを考案
• 高速(?)アルゴリズムも提案して実験

Independent Cascade with Meeting events

• 遭遇確率 m(u,v)
• 伝搬確率 p(u,v)
• 各ステップtで、アクティブな頂点uは非アクティブな頂点に確率m(u,v)で遭遇する
• 一回目の遭遇において確率p(u,v)でアクティベーションが成功する
  • これは一回だけ
• つまり、mは遅延時間を表す
• m=1とすればICモデル
• 締切τ>0
• σ_τ: 2^V→R
  • 時刻τ以内にアクティブになる頂点の期待数
• time-critical influence maximization with a deadline constraint τ
  • σ_τを最大化
• submodularとかは成り立つ
• 証明のスケッチ
  • 各辺uvについて、
  • 1≦t≦τについて、確率m(u,v)のコインフリップ
  • 確率p(u,v)のコインフリップ
  • 到達可能性は？
    • uはvにt_v-t_uホップで到達可能
    • t_u: uに到達する時刻
    • t_v: t_u以降で初めてuがvに遭遇する時刻
  • vがSから到達可能 ⇔
  • (1): live-pathを辿って到達できる、かつ
  • (2): 最短ホップ数がτ以下

提案手法

MIA-M

• 複雑な何かをしている
• maximum influence pathのアイデア

MIA-C

• p_c(u,v) = p(u,v)[1-(1-m(u,v))^β]
  • β∈[1,τ]、τ/2とかにする

実験

• 色々やっている
• MIA系は早くて良い解を出力するよねという話

まとめ

• 手法はともかくモデルは、離散的なので取り組みやすい感があった
• 遅延時間を遭遇確率で表現したのも簡単
• MIAは良いものとして認知されているのか…（困惑）

AAAI influence maximization modeling

2014-03-09 00:11:50 (Sun)