Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a ...

Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a Social Network

  • Peng Zhang, Wei Chen, Xiaoming Sun, Yajun Wang, Jialin Zhang
  • KDD 2014

概要

  • 大きいカスケードが「起こりやすい」ようにシードを選びたい
  • 期待値の代わりに確率を議論するのがミソ
  • この問題は劣モジュラでない
  • 色々解析

動機付け

  • トピックがある閾値まで広まって欲しい
    • tipping point
  • 当然シードセットは小さくしたい
  • しかも確率保証つきで

問題定義

  • 独立カスケードモデル
  • Seed Minimization with Probabilistic Coverage Guarantee (SM-PCG)
    • 確率的被覆保証付きシード最小化
  • 入力
    • G=(V,E,p)
    • U
    • η<|U|
    • 0<P<1
  • $$ 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