On the Submodularity of Influence in Social Networks
<|reference_start|>On the Submodularity of Influence in Social Networks: We prove and extend a conjecture of Kempe, Kleinberg, and Tardos (KKT) on the spread of influence in social networks. A social network can be represented by a directed graph where the nodes are individuals and the edges indicate a form of social relationship. A simple way to model the diffusion of ideas, innovative behavior, or ``word-of-mouth'' effects on such a graph is to consider an increasing process of ``infected'' (or active) nodes: each node becomes infected once an activation function of the set of its infected neighbors crosses a certain threshold value. Such a model was introduced by KKT in \cite{KeKlTa:03,KeKlTa:05} where the authors also impose several natural assumptions: the threshold values are (uniformly) random; and the activation functions are monotone and submodular. For an initial set of active nodes $S$, let $\sigma(S)$ denote the expected number of active nodes at termination. Here we prove a conjecture of KKT: we show that the function $\sigma(S)$ is submodular under the assumptions above. We prove the same result for the expected value of any monotone, submodular function of the set of active nodes at termination.<|reference_end|>
@article{mossel2006on,
    title={On the Submodularity of Influence in Social Networks},
    author={Elchanan Mossel, Sebastien Roch},
    journal={arXiv preprint arXiv:math/0612046},
    year={2006},
    archivePrefix={arXiv},
    eprint={math/0612046},
    primaryClass={math.PR cs.GT cs.SI}
}