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)に更新
-
入力
-
出力
-
頂点集合S
-
Σ_v∈S c_v ≦ B
-
E[Σf_t(v)]を最大化
定理とか
-
ランダムウォークに関連がある
-
近傍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