Maximizing Social Influence in Nearly Optimal Time - todo314 @ ウィキ

Maximizing Social Influence in Nearly Optimal Time

• Christian Borgs, Michael Brautbar, Jennifer Chayes, Brendan Lucier
  • first author有名？
• SODA 2014

概要

• influence maximization(IC model)の近似アルゴリズム
• 今までみたいに、各ノードからの到達可能ノード数や確率を求めるんじゃない
• 逆に考える
• 探索するノードの数をほぼ線形にboundしても良い解が出てくることを保証できる

提案手法

• 逆グラフを作る
• ノードをランダムに選び、逆グラフ上でシミュレートする
  • v「に」伝搬する頂点を選んでいることに等しい
• 各シミュレート結果をハイパーエッジとして保存
• R=144(m+n)ε^-3 log n個のノードを選んだら終了
• ハイパーエッジで考えた次数がデカイノードを選びシードに追加
• シードと共通部分を持つエッジを消して再び上の操作を繰り返す
  • 普通の貪欲アルゴリズム

定理

• O((m+n)ε^-3 log n)時間でアルゴリズムは終了し、その解は3/5以上の確率で1-1/e-ε近似

いくつかの補題

• Observation 3.2
  • σ(S)がランダムにノードを選び逆辺を辿った時にSに到達する確率に等しい
  • これがすごく良いと思った
• Lemma 3.3
  • ハイパーエッジの本数の下限、とその確率
  • 極端に辺が少なくなることは無い（少ないと近似が悪くなるから）
  • 本数の期待値出した後は、Markov不等式の典型的な適用例かな？
  • もし少なかったら、それは「ミス」であるとしてもう一回やり直しても良い
  • 検知できるのがうれしい
• Lemma 3.4
  • ↑の下限を超えている元でdeg_H(S)とσ(S)の差がεOPT以下に大体になる
  • 結構込み入っていてよく分からなかった
• Lemma 3.6
  • submodular関数を適当な誤差範囲で近似した時、その近似関数を最大化すると、
  • 元の関数の1-1/e-ε近似の解が得られる
  • これは一般的な話

• サブリニアで求めるのもあったけど良く分からない…

まとめ

• 理論系の論文では頑張って読んだほう
• 物凄く長い歴史のある問題に関する論文だとそれらを追うのがしんどいので、
• これみたいに、これがかなり初めてに近くて良かった

SODA influence maximization

2013-11-21 00:06:06 (Thu)