On minimizing budget and time in influence propagation over social networks
-
Amit Goyal, Francesco Bonchi, Laks V. S. Lakshmanan
-
Social Network Analysis and Mining (SNAM) 2012
MINTSS (minimum target set selection)
-
入力: 閾値η
-
出力: σ(S)≧ηなる最小サイズのS
-
提案手法: 貪欲算法
-
σ(S)<η-εの間,増量(min{σ(S+t),η}で考える)が最大の頂点をSに追加
-
定理1: 貪欲算法で双基準近似
-
σ(S)≧η-ε
-
|S|≦(1+ln(n/ε))OPT
-
関連
-
real-valued submodular set cover
MINTIME
-
入力: 閾値η,予算k
-
出力: S (|S|=k)と最小のt
-
定理4: 双基準近似は難しい
-
定理5も似た感じ?
-
定理6: 三基準近似
-
σ^R(S: 時刻Rでの影響拡散
-
以下の貪欲算法を考える
-
R=0 to n-1
-
σ^R()について貪欲
-
(時間,予算,被覆)の近似比として(1,1+ln(n/ε), 1-ε/n)が得られる
実験
-
貪欲の良さ
-
ヒューリスティクスとの乖離,次数とかPMIAとか
-
MINTSS
-
MINTIME
まとめ
SNAM 影響最大化 情報拡散
2015/05/18 15:18
最終更新:2015年05月18日 15:20