Maximizing Influence in a Competitive Social Network: A Follower's Perspective

Maximizing Influence in a Competitive Social Network: A Follower's Perspective

  • Tim Carnes, Chandrashekhar Nagarajan, Stefan M. Wild, Anke van Zuylen
  • ICEC 2007

概要

  • 既に敵対するカスケードが広がっている時に,自分はどうシード集合を選択するか
  • 2つのモデルを提案
  • NP-hardだけど1-1/e近似可能

モデル

  • Aが自分で,Bが敵
  • I_B: すでにBのシード集合
  • σ(I_A | I_B)が最大となるI_Aを選びたい
  • ベースはICモデルと同じランダムグラフを考える
    • E_a: 残った辺
  • カスケードの仕方が違う

Distance-based Model

  • d_u(I, E_a): E_a上でのuからIの距離
  • ν_u(I_A, d_u(I, E_a)): uからの距離がd_u(I, E_a)かつI_Aに含まれる頂点集合
  • 頂点uがi(=A/B)を選ぶ確率は
  • ν_u(I_i,・) / [ν_u(I_A, ・)+ν_u(I_B,・)]
    • 要するにuからしたらシードの中も一番近いのだけしか眼中にない
    • 眼中にある奴の中で割合を考える

Wave Propagation Model

  • Pr[u] = Σ_{v∈S}Pr[v] / |S|
    • u: Iからの距離がdとする
    • Pr[u]: uがAを選ぶ確率
    • S: Aの近傍でかつIからの距離がd-1の頂点集合
    • 一番近いところから伝播していく

定理

  • 色々頑張っているがNP-hardってことと,non-negative, monotone, submodularくらい

実験

  • I_Bを選んだ後に,ランダム,次数,貪欲を色々試す

まとめ

  • はい.

ICEC 影響最大化 情報拡散 情報拡散モデル

2014-05-02 01:56:46 (Fri)

最終更新:2014年05月02日 01:56