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 よりも有意に良い