A Note on Maximizing the Spread of Influence in Social Networks

A Note on Maximizing the Spread of Influence in Social Networks

  • Eyal Even-Dar, Asaf Shapira
  • WINE 2007

概要

  • 投票者モデルで考えてみたよ

投票者モデルと問題定義

  • f_t(v) = 0/1: 時刻tでのvの意見
  • f_t+1(v)…vの近傍uを等確率で選びf_t(u)に更新
  • 入力
    • 各頂点のコストc_v
    • 予算B
    • 目標時刻t
  • 出力
    • 頂点集合S
    • Σ_v∈S c_v ≦ B
    • E[Σf_t(v)]を最大化
      • 時刻0にSの頂点を1にする

定理とか

  • ランダムウォークに関連がある
  • 近傍1つ選んで採択するんだからそうか
  • Pr[f_t(v)=1]=Pr[vからの長さtのランダムウォークがSに到達する確率]

短期間の場合(t=poly(n))

  • 単一コストなら割と簡単に厳密に解ける
    • 遷移行列Mをt乗しておいて,一番良さそうな頂点集合をとっていく
  • 単一でないならナップサック問題になるのでFPTAS

長期間の場合(t≧n^5)

  • 線形時間FPTASがある
  • ランダムウォークはO(n^3)ステップで大体定常状態になるので,
  • t≧n^3だと遷移行列の要素がd_u/2|E|とかになってむしろ簡単になる

まとめ

  • 理論だけど分かりやすいかも
  • 後でちゃんと読むかも

WINE 影響最大化 投票者モデル

2014-09-23 00:53:12 (Tue)

最終更新:2014年09月23日 00:53