Today I read a paper titled “On the Submodularity of Influence in Social Networks”
The abstract is:
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.