Stability of Influence Maximization

Stability of Influence Maximization

  • Xinran He, David Kempe
  • KDD 2014

動機付け

  • 影響最大化の高速手法と確率推定の手法は沢山研究されている
  • でも,ノイズは無視できない!
  • もし,推定確率でのσと真の確率でのσの差がでかかったら,
  • 推定σで影響最大化しても意味が無い
  • 確率を摂動しても安定かを判定する問題を定式化しよう

Influence Difference Maximization

  • p_uv: 推定した確率
  • I_uv = [l_uv, r_uv]: 摂動する範囲
  • $$ \max_S \max_{p' \in P} | \sigma_p(S) - \sigma_{p'}(S) | $$
    • 摂動させた中で一番ズレが大きいところを見つける
  • でも,p ≧ p'ならσ_p(S)≧σ_p'(S)なので,↑みたいにするのではなくて,端点だけ考えればOK
  • $$ max. \delta_{p, p'}(S) $$
  • $$ s.t. |S|=k $$
    • $$ \delta_{p, p'}(S) = \sigma_{p}(S) - \sigma_{p'}(S) $$

結果等

安定性の評価

  • 「δは非負,劣モジュラ,だけど単調ではない」
  • θ: 推定したパラメータ
  • θ': 真のパラメータ
  • θ+: σが最大となるパラメータ
  • θ-: σが最小となるパラメータ
  • これだけと,δで評価したずれから,σ'(A)とσ'(A')の不等式を導出できる
    • Aはσを1-1/e最大化した頂点集合,A'は真の最適解

非単調劣モジュラ関数最大化

  • Random Greedy
    • ゲインの大きいk頂点をとってきて,そこからランダムに一つ追加
  • Continuous Double Greedy
  • ↑2つの内結果の良かったものをとってくれば0.356近似
  • だけど,Random Greedyでも1/e近似くらいになる
  • 時間計算量がO(knmR)なので,CELF導入

実験

  • グラフは小さい,しょうがない
  • 10%のずれならなんとかなるけれど,20%を超えるとやばいことになる

まとめ

  • 問題への落とし方がちゃんとしているなあと思った
  • 安定性の評価まで出るのがよさげ
  • これ高速化するだけじゃ駄目だなあ…

KDD 影響最大化 情報拡散

2014-08-19 19:14:54 (Tue)

最終更新:2014年08月19日 19:14