Submodularity conjecture for influence in social networks
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 , let 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 and every node , it satisfies
Influence submodularity conjecture. The function 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 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.