Maximizing the spread of influence through a social network
The DOI matches its Crossref record; 38 of the 38 references it cites were found in a registry or an index.
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
Cited by
Items 101–155 of 155
An event-based framework for characterizing the evolutionary behavior of interaction graphs
Asur, S., Parthasarathy, S., & Ucar, D. (2009) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1631162.1631164 · Cited by 291
Exploring social influence for recommendation: a generative model approach
Ye, M., Liu, X., & Lee, W.-C. (2012) · Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/2348283.2348373 · Cited by 288
Simulated Annealing Based Influence Maximization in Social Networks
Jiang, Q., Song, G., Gao, C., Wang, Y., Si, W., & Xie, K. (2011) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v25i1.7838 · Cited by 288
Saudi Journal of Business and Management Studies
(2019) · Saudi Journal of Business and Management Studies · doi:10.21276/sjbms · Cited by 285
Optimal and scalable distribution of content updates over a mobile social network
Ioannidis, S., Chaintreau, A., & Massoulie, L. (2009) · IEEE INFOCOM 2009 · doi:10.1109/infcom.2009.5062058 · Cited by 281
Decomposing the Value of Word-of-Mouth Seeding Programs: Acceleration versus Expansion
Libai, B., Muller, E., & Peres, R. (2013) · Journal of Marketing Research · doi:10.1509/jmr.11.0305 · Cited by 280
Cascading Behavior in Networks: Algorithmic and Economic Issues
Kleinberg, J. (2007) · Algorithmic Game Theory · doi:10.1017/cbo9780511800481.026 · Cited by 279
Self-citationGong, Z., Zhong, P., & Hu, W. (2019) · IEEE Access · doi:10.1109/access.2019.2917620 · Cited by 277
Graph Summarization Methods and Applications: A Survey
Liu, Y., Safavi, T., Dighe, A., & Koutra, D. (2019) · ACM Computing Surveys · doi:10.1145/3186727 · Cited by 274
Learning with Submodular Functions: A Convex Optimization Perspective
Bach, F. (2013) · now publishers, Inc. eBooks · doi:10.1561/9781601987570 · Cited by 273
Using Gossips to Spread Information: Theory and Evidence from Two Randomized Controlled Trials
Banerjee, A., Chandrasekhar, A. G., Duflo, E., & Jackson, M. O. (2019) · The Review of Economic Studies · doi:10.1093/restud/rdz008 · Cited by 272
Structure and dynamics of information pathways in online media
Gomez Rodriguez, M., Leskovec, J., & Schölkopf, B. (2013) · Proceedings of the sixth ACM international conference on Web search and data mining · doi:10.1145/2433396.2433402 · Cited by 271
Influence-Based Community Partition With Sandwich Method for Social Networks
Ni, Q., Guo, J., Wu, W., & Wang, H. (2023) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2022.3148411 · Cited by 265
Center-piece subgraphs: problem definition and fast solutions
Tong, H., & Faloutsos, C. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150448 · Cited by 264
A Survey on Information Diffusion in Online Social Networks: Models and Methods
Li, M., Wang, X., Gao, K., & Zhang, S. (2017) · Information · doi:10.3390/info8040118 · Cited by 262
A survey on influence maximization in a social network
Banerjee, S., Jenamani, M., & Pratihar, D. K. (2020) · Knowledge and Information Systems · doi:10.1007/s10115-020-01461-4 · Cited by 262
A Survey of Information Cascade Analysis: Models, Predictions, and Recent Advances
Zhou, F., Xu, X., Trajcevski, G., & Zhang, K. (2022) · ACM Computing Surveys · doi:10.1145/3433000 · Cited by 259
Temporal dynamics and network analysis
Blonder, B., Wey, T. W., Dornhaus, A., James, R., & Sih, A. (2012) · Methods in Ecology and Evolution · doi:10.1111/j.2041-210x.2012.00236.x · Cited by 254
Discovering important nodes through graph entropy the case of Enron email database
Shetty, J., & Adibi, J. (2005) · Proceedings of the 3rd international workshop on Link discovery · doi:10.1145/1134271.1134282 · Cited by 254
Information and Influence Propagation in Social Networks
Chen, W., Lakshmanan, L. V. S., & Castillo, C. (2013) · Synthesis lectures on data management · doi:10.2200/s00527ed1v01y201308dtm037 · Cited by 254
Applications, Architectures, and Protocol Design Issues for Mobile Social Networks: A Survey
Kayastha, N., Niyato, D., Wang, P., & Hossain, E. (2011) · Proceedings of the IEEE · doi:10.1109/jproc.2011.2169033 · Cited by 253
A framework for analysis of dynamic social networks
Berger-Wolf, T. Y., & Saia, J. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150462 · Cited by 253
Spreading dynamics in complex networks
Pei, S., & Makse, H. A. (2013) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2013/12/p12002 · Cited by 252
Information cascades in complex networks
Jalili, M., & Perc, M. (2017) · Journal of Complex Networks · doi:10.1093/comnet/cnx019 · Cited by 248
A social recommender mechanism for e-commerce: Combining similarity, trust, and relationship
Li, Y.-M., Wu, C.-T., & Lai, C.-Y. (2013) · Decision Support Systems · doi:10.1016/j.dss.2013.02.009 · Cited by 238
“[27] indicate that information spread by the people with higher closeness relationship would be more influential to other nodes in the network.”
BackgroundFake News Detection in Social Networks via Crowd Signals
Tschiatschek, S., Singla, A., Gomez Rodriguez, M., Merchant, A., & Krause, A. (2018) · Companion of the The Web Conference 2018 on The Web Conference 2018 - WWW '18 · doi:10.1145/3184558.3188722 · Cited by 229
Liu, S., Jiang, C., Lin, Z., Ding, Y., Duan, R., & Xu, Z. (2015) · Information Sciences · doi:10.1016/j.ins.2015.01.034 · Cited by 219
“We compare our algorithm with traditional algorithms such as the hill-climbing algorithm [43] and the general greedy algorithm [19].”
MethodBayesian Inference of Epidemics on Networks via Belief Propagation
Altarelli, F., Braunstein, A., Dall’Asta, L., Lage-Castellanos, A., & Zecchina, R. (2014) · Physical Review Letters · doi:10.1103/physrevlett.112.118701 · Cited by 218
A causal test of the strength of weak ties
Rajkumar, K., Saint-Jacques, G., Bojinov, I., Brynjolfsson, E., & Aral, S. (2022) · Science · doi:10.1126/science.abl4476 · Cited by 216
How does the data sampling strategy impact the discovery of information diffusion in social media?
De Choudhury, M., Lin, Y.-R., Sundaram, H., Candan, K. S., Xie, L., & Kelliher, A. (2010) · Proceedings of the International AAAI Conference on Web and Social Media · doi:10.1609/icwsm.v4i1.14024 · Cited by 209
“Diffusion has found extensive potential in addressing the propagation of medical and technological innovations (Newman 2002), cultural bias (Zachary 1977), (Bakshy, Karrer, and Adamic 2009) and understanding information roles of users (Kempe, Kleinberg, and Tardos 2003), (Watts and Dodds 2007).”
BackgroundHiding individuals and communities in a social network
Waniek, M., Michalak, T. P., Wooldridge, M. J., & Rahwan, T. (2018) · Nature Human Behaviour · doi:10.1038/s41562-017-0290-3 · Cited by 207
“Now consider the influence recovery problem in G under the Linear Threshold model, where: • Â = (V × V ) \ {(v†, S1), . . . , (v†, Sm)}; • tv = l for every node v ∈ {T1, . . . , Tm} and tv = 1 for every other node; • for individual influence recovery, ∀ui∈Uf(ui) = 1 and f(v) = 0 for every other node; • for global inf…”
BackgroundMethodInfluentialLi, Y., Chen, W., Wang, Y., & Zhang, Z.-L. (2013) · Proceedings of the sixth ACM international conference on Web search and data mining · doi:10.1145/2433396.2433478 · Cited by 194
“The initial work [20] proposes several influence diffusion m odels and provides the greedy approximation algorithm for influence maximization.”
BackgroundSocial Influence in Social Advertising: Evidence from Field Experiments
Bakshy, E., Eckles, D., Yan, R., & Rosenn, I. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1206.4327 · Cited by 182
DRIMUX: Dynamic Rumor Influence Minimization with User Experience in Social Networks
Wang, B., Chen, G., Fu, L., Song, L., & Wang, X. (2017) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2017.2728064 · Cited by 178
Core-like groups result in invalidation of identifying super-spreader by k-shell decomposition
Liu, Y., Tang, M., Zhou, T., & Do, Y. (2015) · Scientific Reports · doi:10.1038/srep09602 · Cited by 177
“The most influential nodes can maximize the speed and scope of information spreading compared with other nodes in a network [1].”
Yoo, E., Rand, W., Eftekhar, M., & Rabinovich, E. (2016) · Journal of Operations Management · doi:10.1016/j.jom.2016.05.007 · Cited by 173
“Traditionally, the LT model has not incorporated a p parameter, instead relying on the initial seeds of the network to propagate the information (Kempe et al., 2003; Watts and Dodds, 2007), but a p parameter playing the same role that it does in the IC model can be added to this model instead of an…”
BackgroundMethodInfluentialUsing crowdsourced data in location-based social networks to explore influence maximization
Cai, J. L. Z., Yan, M., & Li, Y. (2016) · IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications · doi:10.1109/infocom.2016.7524471 · Cited by 173
“The influence maximization problem in an online social network is to find a subset of nodes named seed nodes, so that the spread of influence could be maximized if we use the seed nodes to spread the influence [5].”
BackgroundMethodConjoining Speeds up Information Diffusion in Overlaying Social-Physical Networks
Yagan, O., Qian, D., Zhang, J., & Cochran, D. (2013) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2013.130606 · Cited by 166
“The techniques (and the model) presented in this paper can also pave the way in studying the influence maximization [29] problem over multiple networks.”
MethodConstrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms
Gupta, A., Roth, A., Schoenebeck, G., & Talwar, K. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17572-5_20 · Cited by 165
“The problem of selecting a subset of people in a social network to maximize their influence in a viral marketing campaign can be modeled as a constrained submodular maximization problem [21,30].”
BackgroundMeasuring and moderating opinion polarization in social networks
Matakos, A., Terzi, E., & Tsaparas, P. (2017) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-017-0527-9 · Cited by 164
“At a high level, our work is also related to the line of work on influence and opinion maximization (Kempe et al. 2003; Gionis et al. 2013).”
BackgroundPersonalized recommendation driven by information flow
Song, X., Tseng, B. L., Lin, C.-Y., & Sun, M.-T. (2006) · Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/1148170.1148258 · Cited by 164
“[11-13] attempt to model influence among consumers and understand how this influence propagates in the networks.”
BackgroundThe core decomposition of networks: theory, algorithms and applications
Malliaros, F. D., Giatsidis, C., Papadopoulos, A. N., & Vazirgiannis, M. (2020) · The VLDB Journal · doi:10.1007/s00778-019-00587-4 · Cited by 161
“[76], toward a scalable core-based influencemaximization algorithmwith theoretical guarantees.”
BackgroundMirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondrak, J., & Krause, A. (2015) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v29i1.9486 · Cited by 159
“It has also found numerous applications in machine learning and artificial intelligence such as influence maximization (Kempe, Kleinberg, and Tardos 2003 Krause 2011).”
MethodGossip: Identifying Central Individuals in a Social Network
Banerjee, A., Chandrasekhar, A., Duflo, E., & Jackson, M. (2014) · doi:10.3386/w20422 · Cited by 143
Flamino, J., Galeazzi, A., Feldman, S., Macy, M. W., Cross, B., Zhou, Z., Serafino, M., Bovet, A., Makse, H. A., & Szymanski, B. K. (2023) · Nature Human Behaviour · doi:10.1038/s41562-023-01550-8 · Cited by 113
Learning Personalized Preference of Strong and Weak Ties for Social Recommendation
Wang, X., Hoi, S. C. H., Ester, M., Bu, J., & Chen, C. (2017) · Proceedings of the 26th International Conference on World Wide Web · doi:10.1145/3038912.3052556 · Cited by 97
“Indeed, social influence tends to have strong effects in changing human behaviours [19, 4], such as adopting new opinions, technologies, and products.”
BackgroundDierkes, T., Bichler, M., & Krishnan, R. (2011) · Decision Support Systems · doi:10.1016/j.dss.2011.01.002 · Cited by 76
“Recent research on marketing applications has focused on models for simulating the spread of information in a social network [8, 24, 34, 61] or suggests techniques to maximize influence in social networks [27].”
BackgroundGroup interactions modulate critical mass dynamics in social convention
Iacopini, I., Petri, G., Baronchelli, A., & Barrat, A. (2022) · Communications Physics · doi:10.1038/s42005-022-00845-y · Cited by 69
Review of Extracting Information From the Social Web for Health Personalization
Fernandez-Luque, L., Karlsen, R., & Bonander, J. (2011) · Journal of Medical Internet Research · doi:10.2196/jmir.1432 · Cited by 61
Predicting happiness: user interactions and sentiment analysis in an online travel forum
Neidhardt, J., Rümmele, N., & Werthner, H. (2017) · Information Technology & Tourism · doi:10.1007/s40558-017-0079-2 · Cited by 61
“Typically diffusion models and other computational models are used (e.g., Kempe et al. 2003).”
MethodDrivers of social influence in the Twitter migration to Mastodon
Cava, L. L., Aiello, L. M., & Tagarelli, A. (2023) · Scientific Reports · doi:10.1038/s41598-023-48200-7 · Cited by 48
“…global patterns, not on “who-infects-whom”, thus in contrast to the approach underlying stochastic information diffusion and maximization models 43 which assume the availability of a network of connections among individuals, possibly with additional information about user-attributes 44 .”
ResultPersonalized chatbot trustworthiness ratings
Srivastava, B., Rossi, F., Usmani, S., & Bernagozzi, M. (2020) · IEEE Transactions on Technology and Society · doi:10.1109/tts.2020.3023919 · Cited by 40
“Moreover, shared information may spread when other users interact [16] over time.”
BackgroundDiffusion in networks and the virtue of burstiness
Akbarpour, M., & Jackson, M. O. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1722089115 · Cited by 33
Threat From Being Social: Vulnerability Analysis of Social Network Coupled Smart Grid
Pan, T., Mishra, S., Nguyen, L. N., Lee, G., Kang, J., Seo, J., & Thai, M. T. (2017) · IEEE Access · doi:10.1109/access.2017.2738565 · Cited by 20
Semantic Image Analysis on Social Networks and Data Processing: Review and Future Directions
Alzboon, M. S., Alqaraleh, M. K., Aljarrah, E. M., & Alomari, S. A. (2022) · Advances in Business Information Systems and Analytics · doi:10.4018/978-1-7998-9016-4.ch009 · Cited by 1
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.