On the Submodularity of Influence in Social Networks

Details On the Submodularity of Influence in Social Networks On the Submodularity of Influence in Social Networks

2006-12-02

arxiv.org/abs/math/0612046v2

Mathematics

Probability

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the Submodularity of Influence in Social Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Submodularity of Influence in Social Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Submodularity of Influence in Social Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-671932