David Kempe
Jon Kleinberg
Éva Tardos
ABSTRACT
Models for the processes by which ideas and influence propagate through a social network have been studied in a number of domains, including the diffusion of medical and technological innovations, the sudden and widespread adoption of various strategies in game-theoretic settings, and the effects of "word of mouth" in the promotion of new products. Recently, motivated by the design of viral marketing strategies, Domingos and Richardson posed a fundamental algorithmic problem for such social network processes: if we can try to convince a subset of individuals to adopt a new product or innovation, and the goal is to trigger a large cascade of further adoptions, which set of individuals should we target?We consider this problem in several of the most widely studied models in social network analysis. The optimization problem of selecting the most influential nodes is NP-hard here, and we provide the first provable approximation guarantees for efficient algorithms. Using an analysis framework based on submodular functions, we show that a natural greedy strategy obtains a solution that is provably within 63% of optimal for several classes of models; our framework suggests a general approach for reasoning about the performance guarantees of algorithms for these types of influence problems in social networks.We also provide computational experiments on large collaboration networks, showing that in addition to their provable guarantees, our approximation algorithms significantly out-perform node-selection heuristics based on the well-studied notions of degree centrality and distance centrality from the field of social networks.
- R. Albert, H. Jeong, A. Barabasi. Error and attack tolerance of complex networks. Nature 406(2000), 378--382.Google Scholar
Cross Ref
- C. Asavathiratham, S. Roy, B. Lesieutre, G. Verghese. The Influence Model. IEEE Control Systems, Dec. 2001.Google Scholar
- C. Asavathiratham. The Influence Model: A Tractable Representation for the Dynamics of Networked Markov Chains. Ph.D. Thesis, MIT 2000.Google Scholar
- F. Bass. A new product growth model for consumer durables. Management Science 15(1969), 215--227.Google ScholarDigital Library
- E. Berger. Dynamic Monopolies of Constant Size. Journal of Combinatorial Theory Series B 83(2001), 191--200. Google ScholarDigital Library
- L. Blume. The Statistical Mechanics of Strategic Interaction. Games and Economic Behavior 5(1993), 387--424.Google ScholarCross Ref
- J. Brown, P. Reinegen. Social ties and word-of-mouth referral behavior. Journal of Consumer Research 14:3(1987), 350--362.Google ScholarCross Ref
- J. Coleman, H. Menzel, E. Katz. Medical Innovations: A Diffusion Study Bobbs Merrill, 1966.Google Scholar
- G. Cornejols, M. Fisher, G. Nemhauser. Location of Bank Accounts to Optimize Float. Management Science, 23(1977).Google Scholar
- P. Domingos, M. Richardson. Mining the Network Value of Customers. Seventh International Conference on Knowledge Discovery and Data Mining, 2001. Google ScholarDigital Library
- R. Durrett. Lecture Notes on Particle Systems and Percolation. Wadsworth Publishing, 1988.Google Scholar
- G. Ellison. Learning, Local Interaction, and Coordination. Econometrica 61:5(1993), 1047--1071.Google ScholarCross Ref
- J. Goldenberg, B. Libai, E. Muller. Talk of the Network: A Complex Systems Look at the Underlying Process of Word-of-Mouth. Marketing Letters 12:3(2001), 211--223.Google ScholarCross Ref
- J. Goldenberg, B. Libai, E. Muller. Using Complex Systems Analysis to Advance Marketing Theory Development. Academy of Marketing Science Review 2001.Google Scholar
- M. Granovetter. Threshold models of collective behavior. American Journal of Sociology 83(6):1420--1443, 1978.Google ScholarCross Ref
- V. Harinarayan, A. Rajaraman, J. Ullman. Implementing Data Cubes Efficiently. Proc. ACM SIGMOD 1996. Google ScholarDigital Library
- T. M. Liggett. Interacting Particle Systems. Springer, 1985.Google ScholarCross Ref
- M. Macy, Chains of Cooperation: Threshold Effects in Collective Action. American Sociological Review 56(1991).Google Scholar
- M. Macy, R. Willer. From Factors to Actors: Computational Sociology and Agent-Based Modeling. Ann. Rev. Soc. 2002.Google Scholar
- V. Mahajan, E. Muller, F. Bass. New Product Diffusion Models in Marketing: A Review and Directions for Research. Journal of Marketing 54:1(1990) pp. 1--26.Google ScholarCross Ref
- S. Morris. Contagion. Review of Economic Studies 67(2000).Google Scholar
- G. Nemhauser, L. Wolsey. Integer and Combinatorial Optimization. John Wiley, 1988. Google ScholarDigital Library
- G. Nemhauser, L. Wolsey, M. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14(1978), 265--294.Google ScholarDigital Library
- M. Newman. The structure of scientific collaboration networks. Proc. Natl. Acad. Sci. 98(2001).Google Scholar
- D. Peleg. Local Majority Voting, Small Coalitions, and Controlling Monopolies in Graphs: A Review. 3rd Colloq. on Structural Information and Communication, 1996.Google Scholar
- M. Richardson, P. Domingos. Mining Knowledge-Sharing Sites for Viral Marketing. Eighth Intl. Conf. on Knowledge Discovery and Data Mining, 2002. Google ScholarDigital Library
- E. Rogers. Diffusion of innovations Free Press, 1995.Google Scholar
- T. Schelling. Micromotives and Macrobehavior. Norton, 1978.Google Scholar
- T. Valente. Network Models of the Diffusion of Innovations. Hampton Press, 1995.Google Scholar
- S. Wasserman, K. Faust. Social Network Analysis. Cambridge University Press, 1994.Google ScholarCross Ref
- D. Watts. A Simple Model of Global Cascades in Random Networks. Proc. Natl. Acad. Sci. 99(2002), 5766--71.Google ScholarCross Ref
- H. Peyton Young. The Diffusion of Innovations in Social Networks. Santa Fe Institute Working Paper 02-04-018(2002).Google Scholar
- H. Peyton Young. Individual Strategy and Social Structure: An Evolutionary Theory of Institutions. Princeton, 1998.Google Scholar
Index Terms
- Maximizing the spread of influence through a social network
Recommendations
Maximizing influence in a competitive social network: a follower's perspective
ICEC '07: Proceedings of the ninth international conference on Electronic commerceWe consider the problem faced by a company that wants to use viral marketing to introduce a new product into a market where a competing product is already being introduced. We assume that consumers will use only one of the two products and will ...
Information diffusion and external influence in networks
KDD '12: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data miningSocial networks play a fundamental role in the diffusion of information. However, there are two different ways of how information reaches a person in a network. Information reaches us through connections in our social networks, as well as through the ...
Maximizing influence spread in modular social networks by optimal resource allocation
Highlights► We transform the influence maximization problem in modular socialnetworks to a resource allocation problem. ► We derive a recursive relationship for optimal allocation in a modular social network. ► We prove that the ...
AbstractInfluence maximization in a social network is to target a given number of nodes in the network such that the expected number of activated nodes from these nodes is maximized. A social network usually exhibits some degree of modularity. ...
Comments