Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a Social Network
-
Peng Zhang, Wei Chen, Xiaoming Sun, Yajun Wang, Jialin Zhang
-
KDD 2014
概要
-
大きいカスケードが「起こりやすい」ようにシードを選びたい
-
期待値の代わりに確率を議論するのがミソ
-
この問題は劣モジュラでない
-
色々解析
動機付け
-
トピックがある閾値まで広まって欲しい
-
当然シードセットは小さくしたい
-
しかも確率保証つきで
問題定義
-
独立カスケードモデル
-
Seed Minimization with Probabilistic Coverage Guarantee (SM-PCG)
-
入力
-
$$ S^* = \mathrm{argmin}_{S: \Pr[\sigma_U(S)\geq \eta] \geq P} |S| $$
-
難しさはset coverからの帰着
準備
確率の計算
-
Pr[σ(S)≧η]の計算
-
#P-hardなので,シミュレートする
-
Sからシミュレートして,U内の活性頂点数がηを超えたらカウントアップ
-
Hoeffding の不等式とかで抑える
-
max_{η: Pr[σ(S)≧η]≧P}ηの計算
近似アルゴリズム
-
毎回σのゲインが大きい頂点をシード集合に追加
-
条件を満たす(確率がη以上)なら今の集合を返す
-
定理
-
|S|≦ほげ×|S*|+ふが
-
の形の精度
-
大まかにはlog n+O(1)近似
実験
最終更新:2014年10月20日 20:07