「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を選んだ後に，ランダム，次数，貪欲を色々試す
* まとめ
- はい．
&tags()
&update()
