The DOI matches its Crossref record; 38 of the 38 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Rogers, E. M., Singhal, A., & Quinlan, M. M. (2019) · An Integrated Approach to Communication Theory and Research · doi:10.4324/9780203710753-35 · Cited by 37,322
Social Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-L. (2000) · Nature · doi:10.1038/35019019 · Cited by 7,534
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-Ĺ. (2000) · RePEc: Research Papers in Economics · Cited by 6,469
Threshold models of collective behavior
Granovetter, M. (1978) · American Journal of Sociology · doi:10.1086/226707 · Cited by 6,072
(2017) · The SAGE Encyclopedia of Communication Research Methods · doi:10.4135/9781483381411.n575 · Cited by 6,008
A new product growth for model consumer durables
Bass, F. M. (1969) · Management Science · doi:10.1287/mnsc.15.5.215 · Cited by 6,008
Integer and Combinatorial Optimization
Williams, H. P., Nemhauser, G. L., & Wolsey, L. A. (1990) · Journal of the Operational Research Society · doi:10.2307/2583737 · Cited by 5,485
The structure of scientific collaboration networks
Newman, M. E. J. (2001) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.98.2.404 · Cited by 4,482
An analysis of approximations for maximizing submodular set functions—I
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978) · Mathematical Programming · doi:10.1007/bf01588971 · Cited by 4,412
A New Product Growth Model for Consumer Durables
Bass, F. M. (1976) · Lecture Notes in Economics and Mathematical Systems · doi:10.1007/978-3-642-51565-1_107 · Cited by 3,948
Micromotives and Macrobehavior
Eaton, B. C., & Schelling, T. C. (1981) · The Canadian Journal of Economics · doi:10.2307/134812 · Cited by 3,758
(2016) · Foundations of Physically Based Modeling and Animation · doi:10.1201/9781315373140-16 · Cited by 3,267
Liggett, T. M. (1985) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-1-4613-8542-4 · Cited by 2,942
Mining the network value of customers
Domingos, P., & Richardson, M. (2001) · Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/502512.502525 · Cited by 2,830
A simple model of global cascades on random networks
Watts, D. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.082090499 · Cited by 2,673
Social Ties and Word-of-Mouth Referral Behavior
Brown, J. J., & Reingen, P. H. (1987) · Journal of Consumer Research · doi:10.1086/209118 · Cited by 2,378
New Product Diffusion Models in Marketing: A Review and Directions for Research
Mahajan, V., Muller, E., & Bass, F. M. (1991) · Diffusion of Technologies and Social Behavior · doi:10.1007/978-3-662-02700-4_6 · Cited by 2,088
Talk of the Network: A Complex Systems Look at the Underlying Process of Word-of-Mouth
Goldenberg, J., Libai, B., & Muller, E. (2001) · Marketing Letters · doi:10.1023/a:1011122126881 · Cited by 1,995
Network models of the diffusion of innovations
Valente, T. (1996) · Computational and Mathematical Organization Theory · doi:10.1007/bf00240425 · Cited by 1,630
Mining knowledge-sharing sites for viral marketing
Richardson, M., & Domingos, P. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775057 · Cited by 1,612
From Factors to Actors: Computational Sociology and Agent-Based Modeling
Macy, M. W., & Willer, R. (2002) · Annual Review of Sociology · doi:10.1146/annurev.soc.28.110601.141117 · Cited by 1,443
The Statistical Mechanics of Strategic Interaction
Blume, L. E. (1993) · Games and Economic Behavior · doi:10.1006/game.1993.1023 · Cited by 1,402
Implementing data cubes efficiently
Harinarayan, V., Rajaraman, A., & Ullman, J. D. (1996) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/233269.233333 · Cited by 1,364
Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model
Holley, R. A., & Liggett, T. M. (1975) · The Annals of Probability · doi:10.1214/aop/1176996306 · Cited by 1,109
Learning, Local Interaction, and Coordination
Ellison, G. (1993) · Econometrica · doi:10.2307/2951493 · Cited by 1,106
New Product Diffusion Models in Marketing: A Review and Directions for Research
Mahajan, V., Muller, E., & Bass, F. M. (1990) · Journal of Marketing · doi:10.2307/1252170 · Cited by 915
Individual Strategy and Social Structure: An Evolutionary Theory of Institutions
Mezzetti, C., & Young, H. P. (1999) · Southern Economic Journal · doi:10.2307/1061165 · Cited by 851
Cornuejols, G., Fisher, M. L., & Nemhauser, G. L. (1977) · Management Science · doi:10.1287/mnsc.23.8.789 · Cited by 793
Morris, S. (2000) · Review of Economic Studies · doi:10.1111/1467-937x.00121 · Cited by 639
Lecture notes on particle systems and percolation
Durrett, R. T. (1988) · Medical Entomology and Zoology · Cited by 535
Chains of Cooperation: Threshold Effects in Collective Action
Macy, M. W. (1991) · American Sociological Review · doi:10.2307/2096252 · Cited by 490
Structure and Strategy in Collective Action
Chwe, M. S. (1999) · American Journal of Sociology · doi:10.1086/210269 · Cited by 378
Libai, B., Muller, E., Recanati, L., Givon, M. M., & Hogan, J. E. (2001) · Cited by 351
Local majorities, coalitions and monopolies in graphs: a review
Peleg, D. (2002) · Theoretical Computer Science · doi:10.1016/s0304-3975(01)00055-x · Cited by 200
(2001) · IEEE Control Systems · doi:10.1109/37.969135 · Cited by 183
The Diffusion of Innovations in Social Networks
Young, H. P. (2005) · The Economy as an Evolving Complex System, III · doi:10.1093/acprof:oso/9780195162592.003.0011 · Cited by 166
Dynamic Monopolies of Constant Size
Berger, E. (2001) · Journal of Combinatorial Theory Series B · doi:10.1006/jctb.2001.2045 · Cited by 122
Cited by
What is Twitter, a social network or a news media?
Kwak, H., Lee, C., Park, H., & Moon, S. (2010) · Proceedings of the 19th international conference on World wide web · doi:10.1145/1772690.1772751 · Cited by 6,652
Epidemic processes in complex networks
Pastor-Satorras, R., Castellano, C., Van Mieghem, P., & Vespignani, A. (2015) · Reviews of Modern Physics · doi:10.1103/revmodphys.87.925 · Cited by 3,697
Cost-effective outbreak detection in networks
Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., & Glance, N. (2007) · Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1281192.1281239 · Cited by 2,502
Efficient influence maximization in social networks
Chen, W., Wang, Y., & Yang, S. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557047 · Cited by 2,156
The dynamics of viral marketing
Leskovec, J., Adamic, L. A., & Huberman, B. A. (2007) · ACM Transactions on the Web · doi:10.1145/1232722.1232727 · Cited by 2,032
Metadata
- Authors
- Kempe, D., Kleinberg, J., & Tardos, É.
- Venue
- Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining
- Publisher
- ACM
- Published
- 2003-08-24
- Pages
- 137-146
- OpenAlex
- W2061820396
- Cited by
- 7,326
- References
- 38
- FWCI
- 40.61
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.