Scalable Methods for Adaptively Seeding a Social Network (WWW '15)

Thibaut Horel and Yaron Singer.

概要

Influence maximizationの亜種について考える。多くの応用において情報を拡散させるためのシードとして選べる人（core set）は限られており、core setに属する人が高い影響力（例えば次数）を持っているとは限らない。なので、まず第一段階としてまず与えられた予算の一部を用いてcore setの部分集合に対して彼らの友達に情報を拡散してもらうよう頼む、第二段階ではOKしてくれた人達に対して残りの予算を用いて情報の拡散を最大化してくれる人の部分集合を選ぶという方法を考える。２段階でやるというアイデアは多くの人は自分自身は影響力が強くなくても影響力が強いひとを知っているという事実 (Friendship paradox)に基づいている。

使用する情報拡散のモデルはvoter modelのように部分集合の影響力が各要素の影響力の和になるものなら良い。
サンプリングによらない手法
Core setがランダムに選ばれたものでない場合に対しても実験
２つのアルゴリズムを提案して、どちらも近似率は \(1 - \frac{1}{e} \)。サブモジュラ最大化っぽい。