Maximizing the spread of influence through a social network

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.

REFERENCES

• 1: R. Albert, H. Jeong, A. Barabasi. Error and attack tolerance of complex networks. Nature 406(2000), 378--382.
• 2: C. Asavathiratham, S. Roy, B. Lesieutre, G. Verghese. The Influence Model. IEEE Control Systems, Dec. 2001.
• 3: C. Asavathiratham. The Influence Model: A Tractable Representation for the Dynamics of Networked Markov Chains. Ph.D. Thesis, MIT 2000.
• 4: F. Bass. A new product growth model for consumer durables. Management Science 15(1969), 215--227.
• 5: Eli Berger, Dynamic monopolies of constant size, Journal of Combinatorial Theory Series B, v.83 n.2, p.191-200, November 2001 [doi>10.1006/jctb.2001.2045]
• 6: L. Blume. The Statistical Mechanics of Strategic Interaction. Games and Economic Behavior 5(1993), 387--424.
• 7: J. Brown, P. Reinegen. Social ties and word-of-mouth referral behavior. Journal of Consumer Research 14:3(1987), 350--362.
• 8: J. Coleman, H. Menzel, E. Katz. Medical Innovations: A Diffusion Study Bobbs Merrill, 1966.
• 9: G. Cornejols, M. Fisher, G. Nemhauser. Location of Bank Accounts to Optimize Float. Management Science, 23(1977).
• 10: Pedro Domingos , Matt Richardson, Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.57-66, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502525]
• 11: R. Durrett. Lecture Notes on Particle Systems and Percolation. Wadsworth Publishing, 1988.
• 12: G. Ellison. Learning, Local Interaction, and Coordination. Econometrica 61:5(1993), 1047--1071.
• 13: 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.
• 14: J. Goldenberg, B. Libai, E. Muller. Using Complex Systems Analysis to Advance Marketing Theory Development. Academy of Marketing Science Review 2001.
• 15: M. Granovetter. Threshold models of collective behavior. American Journal of Sociology 83(6):1420--1443, 1978.
• 16: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 17: T. M. Liggett. Interacting Particle Systems. Springer, 1985.
• 18: M. Macy, Chains of Cooperation: Threshold Effects in Collective Action. American Sociological Review 56(1991).
• 19: M. Macy, R. Willer. From Factors to Actors: Computational Sociology and Agent-Based Modeling. Ann. Rev. Soc. 2002.
• 20: 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.
• 21: S. Morris. Contagion. Review of Economic Studies 67(2000).
• 22: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 23: G. Nemhauser, L. Wolsey, M. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14(1978), 265--294.
• 24: M. Newman. The structure of scientific collaboration networks. Proc. Natl. Acad. Sci. 98(2001).
• 25: D. Peleg. Local Majority Voting, Small Coalitions, and Controlling Monopolies in Graphs: A Review. 3rd Colloq. on Structural Information and Communication, 1996.
• 26: Matthew Richardson , Pedro Domingos, Mining knowledge-sharing sites for viral marketing, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775057]
• 27: E. Rogers. Diffusion of innovations Free Press, 1995.
• 28: T. Schelling. Micromotives and Macrobehavior. Norton, 1978.
• 29: T. Valente. Network Models of the Diffusion of Innovations. Hampton Press, 1995.
• 30: S. Wasserman, K. Faust. Social Network Analysis. Cambridge University Press, 1994.
• 31: D. Watts. A Simple Model of Global Cascades in Random Networks. Proc. Natl. Acad. Sci. 99(2002), 5766--71.
• 32: H. Peyton Young. The Diffusion of Innovations in Social Networks. Santa Fe Institute Working Paper 02-04-018(2002).
• 33: H. Peyton Young. Individual Strategy and Social Structure: An Evolutionary Theory of Institutions. Princeton, 1998.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Keywords:
approximation algorithms, diffusion of innovations, social networks, viral marketing