The DOI matches its Crossref record; 72 of the 72 references it cites were found in a registry or an index.
Influence Maximization on Social Graphs: A Survey
Abstract
Influence Maximization (IM), which selects a set of k users (called seed set) from a social network to maximize the expected number of influenced users (called influence spread), is a key algorithmic problem in social influence analysis. Due to its immense application potential and enormous technical challenges, IM has been extensively studied in the past decade. In this paper, we survey and synthesize a wide spectrum of existing studies on IM from an algorithmic perspective, with a special focus on the following key aspects: (1) a review of well-accepted diffusion models that capture the information diffusion process and build the foundation of the IM problem, (2) a fine-grained taxonomy to classify existing IM algorithms based on their design objectives, (3) a rigorous theoretical comparison of existing IM algorithms, and (4) a comprehensive study on the applications of IM techniques in combining with novel context features of social networks such as topic, location, and time. Based on this analysis, we then outline the key challenges and research directions to expand the boundary of IM research.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Centrality in social networks conceptual clarification
Freeman, L. C. (1978) · Social Networks · doi:10.1016/0378-8733(78)90021-7 · Cited by 17,062
(1999) · Cited by 12,854
A contribution to the mathematical theory of epidemics
Kermack, W. O., & McKendrick, A. G. (1927) · Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character · doi:10.1098/rspa.1927.0118 · Cited by 11,701
Maximizing the spread of influence through a social network
Kempe, D., Kleinberg, J., & Tardos, É. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956769 · Cited by 7,326
Threshold models of collective behavior
Granovetter, M. (1978) · American Journal of Sociology · doi:10.1086/226707 · Cited by 6,072
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
Compliance, identification, and internalization three processes of attitude change
Kelman, H. C. (1958) · Journal of Conflict Resolution · doi:10.1177/002200275800200106 · Cited by 3,830
Micromotives and Macrobehavior
Eaton, B. C., & Schelling, T. C. (1981) · The Canadian Journal of Economics · doi:10.2307/134812 · Cited by 3,758
OpenMP: an industry standard API for shared-memory programming
Dagum, L., & Menon, R. (1998) · IEEE Computational Science and Engineering · doi:10.1109/99.660313 · Cited by 3,343
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
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
Self-citationThe Complexity of Enumeration and Reliability Problems
Valiant, L. G. (1979) · SIAM Journal on Computing · doi:10.1137/0208032 · Cited by 2,076
Micromotives and Macrobehavior.
Connolly, T., & Schelling, T. C. (1979) · Administrative Science Quarterly · doi:10.2307/2989930 · Cited by 2,009
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
Scalable influence maximization for prevalent viral marketing in large-scale social networks
Chen, W., Wang, C., & Wang, Y. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835934 · Cited by 1,731
Self-citationLearning influence probabilities in social networks
Goyal, A., Bonchi, F., & Lakshmanan, L. V. S. (2010) · Proceedings of the third ACM international conference on Web search and data mining · doi:10.1145/1718487.1718518 · Cited by 1,022
The budgeted maximum coverage problem
Khuller, S., Moss, A., & Naor, J. (. (1999) · Information Processing Letters · doi:10.1016/s0020-0190(99)00031-9 · Cited by 982
Influential Nodes in a Diffusion Model for Social Networks
Kempe, D., Kleinberg, J., & Tardos, É. (2005) · Lecture Notes in Computer Science · doi:10.1007/11523468_91 · Cited by 948
CLIFFORD, P., & SUDBURY, A. (1973) · Biometrika · doi:10.1093/biomet/60.3.581 · Cited by 945
Social influence analysis in large-scale networks
Tang, J., Sun, J., Wang, C., & Yang, Z. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557108 · Cited by 927
Scalable Influence Maximization in Social Networks under the Linear Threshold Model
Chen, W., Yuan, Y., & Zhang, L. (2010) · 2010 IEEE International Conference on Data Mining · doi:10.1109/icdm.2010.118 · Cited by 924
Information diffusion in online social networks: a survey
Guille, A., Hacid, H., Favre, C., & Zighed, D. A. (2013) · ACM SIGMOD Record · doi:10.1145/2503792.2503797 · Cited by 851
An analysis of approximations for maximizing submodular set functions - 1Preprint
Fisher, M. L., Nemhauser, G. L., & Wolsey, L. A. (1978) · RePEc: Research Papers in Economics · Cited by 837
Limiting the spread of misinformation in social networks
Budak, C., Agrawal, D., & El Abbadi, A. (2011) · Proceedings of the 20th international conference on World wide web · doi:10.1145/1963405.1963499 · Cited by 807
Influence Maximization in Near-Linear Time: A Martingale Approach
Tang, Y., Shi, Y., & Xiao, X. (2015) · Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2723372.2723734 · Cited by 768
Maximizing Social Influence in Nearly Optimal Time
Borgs, C., Brautbar, M., Chayes, J., & Lucier, B. (2014) · Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms · doi:10.1137/1.9781611973402.70 · Cited by 624
Community-based greedy algorithm for mining top-K influential nodes in mobile social networks
Wang, Y., Cong, G., Song, G., & Xie, K. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835935 · Cited by 541
Self-citationSIMPATH: An Efficient Algorithm for Influence Maximization under the Linear Threshold Model
Goyal, A., Lu, W., & Lakshmanan, L. V. S. (2011) · 2011 IEEE 11th International Conference on Data Mining · doi:10.1109/icdm.2011.132 · Cited by 508
Tractable Models for Information Diffusion in Social Networks
Kimura, M., & Saito, K. (2006) · Lecture Notes in Computer Science · doi:10.1007/11871637_27 · Cited by 444
IRIE: Scalable and Robust Influence Maximization in Social Networks
Jung, K., Heo, W., & Chen, W. (2012) · Proceedings · doi:10.1109/icdm.2012.79 · Cited by 441
Prediction of Information Diffusion Probabilities for Independent Cascade Model
Saito, K., Nakano, R., & Kimura, M. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-85567-5_9 · Cited by 436
Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model
He, X., Song, G., Chen, W., & Jiang, Q. (2012) · Proceedings of the 2012 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972825.40 · Cited by 403
A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks
Narayanam, R., & Narahari, Y. (2011) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2010.2052042 · Cited by 382
Uncovering the Temporal Dynamics of Diffusion Networks
Gomez-Rodriguez, M., Balduzzi, D., & Schölkopf, B. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1105.0697 · Cited by 360
Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks
Nguyen, H. T., Thai, M. T., & Dinh, T. N. (2016) · Proceedings of the 2016 International Conference on Management of Data · doi:10.1145/2882903.2915207 · Cited by 346
Das, A., & Kempe, D. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1102.3975 · Cited by 330
Threshold Models for Competitive Influence in Social Networks
Borodin, A., Filmus, Y., & Oren, J. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17572-5_48 · Cited by 306
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
Self-citationExploring 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
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
Information and Influence Propagation in Social Networks
Chen, W., Lakshmanan, L. V. S., & Castillo, C. (2014) · Synthesis Lectures on Data Management · doi:10.1007/978-3-031-01850-3 · Cited by 248
Adaptive Influence Maximization in Dynamic Social Networks
Tong, G., Wu, W., Tang, S., & Du, D.-Z. (2017) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2016.2563397 · Cited by 219
On the submodularity of influence in social networks
Mossel, E., & Roch, S. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250811 · Cited by 217
A Survey of Models and Algorithms for Social Influence Analysis
Sun, J., & Tang, J. (2011) · Social Network Data Analytics · doi:10.1007/978-1-4419-8462-3_7 · Cited by 199
Li, 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
Self-citationEfficient location-aware influence maximization
Li, G., Chen, S., Feng, J., Tan, K., & Li, W.-S. (2014) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2588555.2588561 · Cited by 188
Self-citationTopic-Aware Social Influence Propagation Models
Barbieri, N., Bonchi, F., & Manco, G. (2012) · 2012 IEEE 12th International Conference on Data Mining · doi:10.1109/icdm.2012.122 · Cited by 186
Wen, S., Haghighi, M. S., Chen, C., Xiang, Y., Zhou, W., & Jia, W. (2015) · IEEE Transactions on Computers · doi:10.1109/tc.2013.2295802 · Cited by 185
Scalable and parallelizable processing of influence maximization for large-scale social networks?
Kim, J., Kim, S.-K., & Yu, H. (2013) · 2013 IEEE 29th International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2013.6544831 · Cited by 182
Opinion maximization in social networks
Gionis, A., Terzi, E., & Tsaparas, P. (2013) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972832.43 · Cited by 162
Chen, W., Lin, T., Tan, Z., Zhao, M., & Zhou, X. (2016) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2939672.2939745 · Cited by 155
Learning the graph of epidemic cascades
Netrapalli, P., & Sanghavi, S. (2012) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/2254756.2254783 · Cited by 147
Lei, S., Maniu, S., Mo, L., Cheng, R. C. K., & Senellart, P. P. (2015) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2783258.2783271 · Cited by 146
Scalable Influence Estimation in Continuous-Time Diffusion NetworksPreprint
Du, N., Song, L., Gomez-Rodriguez, M., & Hongyuan Zha, B. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1311.3669 · Cited by 137
Tang, J., Wu, S., & Sun, J. (2013) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2487575.2487691 · Cited by 123
Influence Maximization in Continuous Time Diffusion NetworksPreprint
Gomez-Rodriguez, M., & Schölkopf, B. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1205.1682 · Cited by 121
On the Upper Bounds of Spread for Greedy Algorithms in Social Network Influence Maximization
Zhou, C. D., Zhang, P., Zang, W., & Guo, L. (2015) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2015.2419659 · Cited by 120
Cost-aware Targeted Viral Marketing in billion-scale networks
Nguyen, H. T., Dinh, T. N., & Thaip, M. T. (2016) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2016.7524377 · Cited by 119
Holistic Influence Maximization
Galhotra, S., Arora, A., & Roy, S. (2016) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2882903.2882929 · Cited by 110
Influence Maximization over Large-Scale Social Networks: A Bounded Linear Approach
Liu, Q., Xiang, B., Chen, E., Xiong, H., Tang, F., & Yu, J. X. (2014) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2661829.2662009 · Cited by 100
Influence Estimation and Maximization in Continuous-Time Diffusion Networks
Gomez-Rodriguez, M., Song, L., Du, N., Hongyuan Zha, B., & Schölkopf, B. (2016) · ACM Transactions on Information Systems · doi:10.1145/2824253 · Cited by 97
Personalized influence maximization on social networks
Guo, J., Zhang, P., Zhou, C. D., Cao, Y., & Guo, L. (2013) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2505515.2505571 · Cited by 95
Lin, S.-C., Lin, S.-D., & Chen⋆, M.-S. (2015) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2783258.2783392 · Cited by 87
Dynamic influence analysis in evolving networks
Ohsaka, N., Akiba, T., Yoshida, Y., & Kawarabayashi, K. (2016) · Proceedings of the VLDB Endowment · doi:10.14778/2994509.2994525 · Cited by 80
Efficient discovery of influential nodes for SIS models in social networks
Saito, K., Kimura, M., Ohara, K., & Motoda, H. (2011) · Knowledge and Information Systems · doi:10.1007/s10115-011-0396-2 · Cited by 76
Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware ModelsPreprint
Galhotra, S., Arora, A., & Roy, S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.03110 · Cited by 61
Recent Advances in Information Diffusion and Influence Maximization of Complex Social Networks
Zhang, H., Mishra, S., & Thai, M. T. (2014) · CRC Press eBooks · doi:10.1201/b17231-3 · Cited by 60
Stability of influence maximization
He, X., & Kempe, D. (2014) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2623330.2623746 · Cited by 54
Kutzkov, K., Bifet, A., Bonchi, F., & Gionis, A. (2013) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2487575.2487657 · Cited by 51
Opinion Maximization in Social NetworksPreprint
Gionis, A., Terzi, E., & Tsaparas, P. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.7455 · Cited by 42
On Influential Nodes Tracking in Dynamic Social Networks
Chen, X., Song, G., He, X., & Xie, K. (2015) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611974010.69 · Cited by 36
Metadata
- Authors
- Li, Y., Fan, J., Wang, Y., & Tan, K.-L.
- Venue
- IEEE Transactions on Knowledge and Data Engineering
- Published
- 2018-10-01
- Volume
- 30
- Issue
- 10
- Pages
- 1852-1872
- ISSN
- 1041-4347 (ISSN-L)
- 1558-2191
- 2326-3865
- OpenAlex
- W2792990871
- Cited by
- 659
- References
- 72
- FWCI
- 32.64
- Type
- journal article
- 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.