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