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モデルと同じランダムグラフを考える
-
カスケードの仕方が違う
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