09. Influence Maximization

背景

  • 68%の人は家電を買う前に家族か友人に相談する
  • 50%の人は家電を買う前にインターネットを調べる
  • viral marketing: SNS で影響力のある人にマーケティングして伝搬してもらう

問題

independent cascade model.各辺確率 $p_{vw}$ が与えられている.

頂点集合 S が最初に active な頂点集合.

その確率で辺が残るようなグラフを考えて,S から到達可能な頂点の集合 T に影響が伝わる.

サイズ k の初期頂点集合 S であって,f(S) := |T| の期待値が最大になるものを選べ.

性質

  • NP-Hard (Vertex Cover)
  • submodular, monotone -> 近似アルゴリズム!

アルゴリズム

貪欲法.最も f(S) が増えるような要素を加えることをサイズ k になるまでやる.

submodular かつ monotone なら,これは (1 - 1/e) (> 0.63) 近似を与える.

実験結果:degree や distance centrality よりも有意に良い