Influence Maximization in Undirected Networks

Influence Maximization in Undirected Networks

  • Sanjeev Khanna Brendan Lucier
  • SODA 2014

難しいので概要だけ

  • 無向グラフでのinfluence maximizationでは、貪欲アルゴリズムは1-1/eよりも良い近似比が保証できるという話
  • 1-1/e+c
    • cはタイトな値は示さずfuture work
  • 直感的な例
    • p12=1/2, p13=1/2のグラフを考える
    • 有向グラフだと、貪欲解={1,2}、最適解={2,3}で競合比が酷いことになる
    • 無向グラフだと、貪欲解={2,3}、最適解={2,3}で一致する
  • こういうのを考慮すると良いらしい
  • XYZ Lemma
    • x,y,zが確率pで連結なら、どれか1組はpよりはるかに大きい確率で連結になる

SODA influence maximization

2014-01-26 03:02:50 (Sun)

最終更新:2014年01月26日 03:02