Submodularity conjecture for influence in social networks

Let a social network be equipped with the increasing diffusion process described in the paper. For an initial active set SS, let σ(S)\sigma(S) denote the expected size of the set of active nodes at the end of the process. A set function is submodular when, for all sets ABA\subseteq B and every node vBv\notin B, it satisfies

σ(A{v})σ(A)σ(B{v})σ(B).\sigma(A\cup\{v\})-\sigma(A)\geq\sigma(B\cup\{v\})-\sigma(B).

Influence submodularity conjecture. The function σ\sigma is submodular.

Submodularity would yield strong approximation guarantees for the Influence Maximization Problem, allowing a near-optimal fixed-size initial set to be found efficiently. The cited results establish the algorithmic consequences if σ\sigma is submodular, but the supplied text does not state whether this conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Elchanan Mossel and Sebastien Roch, “On the Submodularity of Influence in Social Networks”, arXiv:math/0612046 (2009).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.