  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.

Probability;Computer Science and Game Theory;Social and Information Networks