ABSTRACT
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 [7,8] where the authors also impose several natural assumptions: the threshold values are (uniformly) random to account for our lack of knowledge of the true values; and the activation functions are monotone and submodular, i.e. have "diminishing returns." The monotonicity condition indicates that a node is more likely to become active if more of its neighbors are active, while the submodularity condition, indicates that the marginal effect of each neighbor is decreasing when the set of active neighbors increases.
For an initial set of active nodes s, let σ(S) denote the expected number of active nodes at termination. Here we prove a conjecture of KKT: we show that the function σ(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.
In other words, our results demonstrate that "local" submodularity is preserved "globally" under diffusion processes. This is of natural computational interest, as many optimization problems have good approximation algorithms for submodular functions. In particular, our results coupled with an argument in [7] imply that a greedy algorithm gives an (1-1/e-ε)-approximation algorithm for maximizing σ(S) among all sets s of a given size. This result has important practical implications for many social network analysis problems, notably viral marketing.
- Noam Berger, Christian Borgs, Jennifer T. Chayes, and Amin Saberi. On the spread of viruses on the internet. In SODA, pages 301--310, 2005. Google ScholarDigital Library
- P. Domingo and M. Richardson. Minning the network value of customers. In Proceedings of the 7th Intl. Conference on Knowledge Discovery and Data Minning, pages 57--66, 2001. Google ScholarDigital Library
- P. Domingo and M. Richardson. Minning knowledge-sharing sites for viral marketing. In Proceedings of the 8th Intl. Conference on Knowledge Discovery and Data Minning, pages 61--70, 2002. Google ScholarDigital Library
- Rick Durrett. Lecture notes on particle systems and percolation. 1988.Google Scholar
- Rick Durrett and Paul Jung. Two phase transitions for the contact process on small worlds. Submitted, 2006.Google Scholar
- M. Granovetter. Threshold models of collective behavior. American Journal of Sociology, 83(6):1420--1443, 1978.Google ScholarCross Ref
- D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2003. Google ScholarDigital Library
- D. Kempe, J. Kleinberg, and E. Tardos. Influential nodes in a diffusion model for social networks. In Proc. 32nd International Colloquium on Automata, Languages and Programming (ICALP), 2005. Google ScholarDigital Library
- Thomas M. Liggett. Interacting particle systems, volume 276 of Grundlehren der Mathematischen Wissenschaften {Fundamental Principles of Mathematical Sciences}. Springer-Verlag, New York, 1985.Google Scholar
- Thomas M. Liggett. Stochastic interacting systems: contact, voter and exclusion processes, volume 324 of Grundlehren der Mathematischen Wissenschaften {Fundamental Principles of Mathematical Sciences}. Springer-Verlag, Berlin, 1999.Google Scholar
- T. Lindvall. Lectures on the Coupling Method. Wiley, New York, 1992.Google Scholar
- M. Morris, editor. Network Epidemiology. Oxford University Press, 2004.Google Scholar
- G. Nemhauser and L. Wolsey. Integer and Combinatorial Optimization. John Wiley, 1988. Google ScholarDigital Library
- S. Wasserman and K. Faust. Social Network Analysis. Cambridge University Press, 1994.Google ScholarCross Ref
Index Terms
- On the submodularity of influence in social networks
Recommendations
Submodularity of Influence in Social Networks: From Local to Global
Social networks are often represented as directed graphs, 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 ...
An Analytical Way to Find Influencers on Social Networks and Validate their Effects in Disseminating Social Games
ASONAM '09: Proceedings of the 2009 International Conference on Advances in Social Network Analysis and MiningAs the weight of online social networks (OSNs) which provide powerful means of sharing common interests and communicating has gradually grown up, influencers are also given the great attention. This research proposes and evaluates a methodology for ...
Higher order monotonicity and submodularity of influence in social networks: From local to global
AbstractKempe, Kleinberg and Tardos (KKT) proposed the following conjecture about the general threshold model in social networks: local monotonicity and submodularity implies global monotonicity and submodularity. That is, if the threshold ...
Comments