Influence Maximization in Undirected Networks
-
Sanjeev Khanna Brendan Lucier
-
SODA 2014
難しいので概要だけ
-
無向グラフでのinfluence maximizationでは、貪欲アルゴリズムは1-1/eよりも良い近似比が保証できるという話
-
1-1/e+c
-
直感的な例
-
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