Maximizing the spread of influence through a social network | Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining
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]
E. Berger. Dynamic Monopolies of Constant Size. Journal of Combinatorial Theory Series B 83(2001), 191--200.
[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]
P. Domingos, M. Richardson. Mining the Network Value of Customers. Seventh International Conference on Knowledge Discovery and Data Mining, 2001.
[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]
V. Harinarayan, A. Rajaraman, J. Ullman. Implementing Data Cubes Efficiently. Proc. ACM SIGMOD 1996.
[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]
G. Nemhauser, L. Wolsey. Integer and Combinatorial Optimization. John Wiley, 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]
M. Richardson, P. Domingos. Mining Knowledge-Sharing Sites for Viral Marketing. Eighth Intl. Conf. on Knowledge Discovery and Data Mining, 2002.
[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.
Information & Contributors
Information
Published In
KDD '03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining
August 2003
736 pages
Copyright © 2003 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 August 2003
Permissions
Request permissions for this article.
Check for updates
Author Tags
Qualifiers
- Article
Conference
Acceptance Rates
KDD '03 Paper Acceptance Rate 46 of 298 submissions, 15%;
Overall Acceptance Rate 1,133 of 8,635 submissions, 13%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- Downloads (Last 12 months)1,404
- Downloads (Last 6 weeks)151
Reflects downloads up to 31 Jan 2025
Other Metrics
Citations
- Tian LJi XZhou Y(2025)Maximizing Information Dissemination in Social Network via a Fast Local SearchSystems10.3390/systems1301005913:1(59)Online publication date: 19-Jan-2025
- Medjahed FMolina ETejada J(2025)Effectiveness of Centrality Measures for Competitive Influence Diffusion in Social NetworksMathematics10.3390/math1302029213:2(292)Online publication date: 17-Jan-2025
- Wang GDu SJiang YLi X(2025)A homophilic and dynamic influence maximization strategy based on independent cascade model in social networksFrontiers in Physics10.3389/fphy.2024.150990512Online publication date: 3-Jan-2025
- Guo YXie WWang QYan DZhang Y(2025)Betweenness Approximation for Edge Computing with Hypergraph Neural NetworksTsinghua Science and Technology10.26599/TST.2023.901010630:1(331-344)Online publication date: Feb-2025
- Xujin CXiaodong HYingying SChenhao WXiaoying W(2025)The equilibrium existence of strategic influence games in social networksSCIENTIA SINICA Mathematica10.1360/SSM-2024-0148Online publication date: 3-Jan-2025
- He QZhang ZBi TFang HYi XYu K(2025)Adaptive Rumor Suppression on Social Networks: A Multi-Round Hybrid ApproachACM Transactions on Knowledge Discovery from Data10.1145/370173819:2(1-24)Online publication date: 11-Jan-2025
- Liu YChen XWang XSu ZFan SWang Z(2025)Efficient Continuous Network DismantlingIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2024.349669455:2(976-989)Online publication date: Feb-2025
- Liu YWang XWang XWang ZKurths J(2025)Diffusion Source Inference for Large-Scale Complex Networks Based on Network PercolationIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.332176736:1(1453-1466)Online publication date: Jan-2025
- Teng YShi YYang DTai CYu PChen M(2025)Multi-Grade Revenue Maximization for Promotional and Competitive Viral Marketing in Social NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.351835937:3(1339-1353)Online publication date: Mar-2025
- Liu XKato SGu WRen FSu GZhang M(2025)Diffusion of Ordinal Opinions in Social Networks: An Agent-Based Model and Heuristics for CampaigningIEEE Transactions on Computational Social Systems10.1109/TCSS.2024.345895012:1(335-347)Online publication date: Feb-2025
- Show More Cited By
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.