The DOI matches its Crossref record; 67 of the 67 references it cites were found in a registry or an index.
Inferring networks of diffusion and influence
Abstract
Information diffusion and virus propagation are fundamental processes talking place in networks. While it is often possible to directly observe when nodes become infected, observing individual transmissions (i.e., who infects whom or who influences whom) is typically very difficult. Furthermore, in many applications, the underlying network over which the diffusions and propagations spread is actually unobserved. We tackle these challenges by developing a method for tracing paths of diffusion and influence through networks and inferring the networks over which contagions propagate. Given the times when nodes adopt pieces of information or become infected, we identify the optimal network that best explains the observed infection times. Since the optimization problem is NP-hard to solve exactly, we develop an efficient approximation algorithm that scales to large datasets and in practice gives provably near-optimal performance. We demonstrate the effectiveness of our approach by tracing information cascades in a set of 170 million blogs and news articles over a one year period to infer how information flows through the online media space. We find that the diffusion network of news tends to have a core-periphery structure with a small set of core media sites that diffuse information to the rest of the Web. These sites tend to have stable circles of influence with more general news media sites acting as connectors between them.
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
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,337
Infectious Diseases of Humans: Dynamics and Control
(1992) · Annals of Internal Medicine · doi:10.7326/0003-4819-117-2-174_4 · Cited by 7,746
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
The Mathematics of Infectious Diseases
Hethcote, H. W. (2000) · SIAM Review · doi:10.1137/s0036144500371907 · Cited by 6,687
Sparse inverse covariance estimation with the graphical lasso
Friedman, J., Hastie, T., & Tibshirani, R. (2008) · Biostatistics · doi:10.1093/biostatistics/kxm045 · Cited by 6,355
The Evolution of Random Graphs
(1986) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/062/06 · Cited by 5,543
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
Respondent-Driven Sampling: A New Approach to the Study of Hidden Populations
Heckathorn, D. D. (1997) · Social Problems · doi:10.1525/sp.1997.44.2.03x0221m · Cited by 4,409
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
High dimensional graphs and variable selection with the Lasso
Meinshausen, N., & Bühlmann, P. (2006) · Cited by 2,539
High-dimensional graphs and variable selection with the Lasso
Meinshausen, N., & Bühlmann, P. (2006) · The Annals of Statistics · doi:10.1214/009053606000000281 · Cited by 2,521
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
Self-citationGraph evolution: Densification and shrinking diameters
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217301 · Cited by 2,461
Self-citationGraphs over time: densification laws, shrinking diameters and possible explanations
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2005) · Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining · doi:10.1145/1081870.1081893 · Cited by 2,281
Self-citationThe origin of bursts and heavy tails in human dynamics
Barabási, A.-L. (2005) · Nature · doi:10.1038/nature03459 · Cited by 2,210
Hierarchical structure and the prediction of missing links in networks
Clauset, A., Moore, C., & Newman, M. E. J. (2008) · Nature · doi:10.1038/nature06830 · Cited by 2,171
Personal Influence: The Part Played by People in the Flow of Mass Communications
Willigan, W. L., Katz, E., & Lazarsfeld, P. F. (1956) · The American Catholic Sociological Review · doi:10.2307/3708755 · Cited by 2,157
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
Self-citationThe Mathematical Theory of Infectious Diseases and its applications
Ling, N. R. (1978) · Immunology · Cited by 1,934
Personal Influence: The Part Played by People in the Flow of Mass Communications
Roshwalb, I., Katz, E., & Lazarsfeld, P. F. (1956) · Journal of Marketing · doi:10.2307/1247718 · Cited by 1,880
Influentials, Networks, and Public Opinion Formation
Watts, D. J., & Dodds, P. S. (2007) · Journal of Consumer Research · doi:10.1086/518527 · Cited by 1,875
On the evolution of random graphs
Erdös, P., & Rényi, A. (2011) · The Structure and Dynamics of Networks · doi:10.1515/9781400841356.38 · Cited by 1,757
Diffusion in Organizations and Social Movements: From Hybrid Corn to Poison Pills
Strang, D., & Soule, S. A. (1998) · Annual Review of Sociology · doi:10.1146/annurev.soc.24.1.265 · Cited by 1,678
The link prediction problem for social networks
Liben-Nowell, D., & Kleinberg, J. (2003) · Proceedings of the twelfth international conference on Information and knowledge management · doi:10.1145/956863.956972 · Cited by 1,612
Meme-tracking and the dynamics of the news cycle
Leskovec, J., Backstrom, L., & Kleinberg, J. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557077 · Cited by 1,530
Self-citationKarnowski, V., & Kümpel, A. S. (2016) · Schlüsselwerke der Medienwirkungsforschung · doi:10.1007/978-3-658-09923-7_9 · Cited by 1,311
A Bayesian Networks Approach for Predicting Protein-Protein Interactions from Genomic Data
Jansen, R., Yu, H., Greenbaum, D., Kluger, Y., Krogan, N. J., Chung, S., Emili, A., Snyder, M., Greenblatt, J. F., & Gerstein, M. (2003) · Science · doi:10.1126/science.1087361 · Cited by 1,254
Wallinga, J. (2004) · American Journal of Epidemiology · doi:10.1093/aje/kwh255 · Cited by 1,197
Romero, D. M., Meeder, B., & Kleinberg, J. (2011) · Proceedings of the 20th international conference on World wide web · doi:10.1145/1963405.1963503 · Cited by 1,082
Information diffusion through blogspace
Gruhl, D., Guha, R., Liben-Nowell, D., & Tomkins, A. (2004) · Proceedings of the 13th international conference on World Wide Web · doi:10.1145/988672.988739 · Cited by 1,041
Learning 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
Supervised random walks: predicting and recommending links in social networks
Backstrom, L., & Leskovec, J. (2011) · Proceedings of the fourth ACM international conference on Web search and data mining · doi:10.1145/1935826.1935914 · Cited by 982
Self-citationBUTTE, A. J., & KOHANE, I. S. (1999) · Biocomputing 2000 · doi:10.1142/9789814447331_0040 · Cited by 945
Information diffusion through blogspace
Gruhl, D., Liben-Nowell, D., Guha, R., & Tomkins, A. (2004) · ACM SIGKDD Explorations Newsletter · doi:10.1145/1046456.1046462 · Cited by 927
Diffusion of Innovations, Fourth Edition
Rogers, E. M. (1982) · Cited by 914
Statistical properties of community structure in large social and information networks
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2008) · Proceedings of the 17th international conference on World Wide Web · doi:10.1145/1367497.1367591 · Cited by 860
Self-citationAn 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
Friedman, N., & Koller, D. (2003) · Machine Learning · doi:10.1023/a:1020249912095 · Cited by 811
Robust dynamic classes revealed by measuring the response function of a social system
Crane, R., & Sornette, D. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0803685105 · Cited by 786
Edmonds, J. (1967) · Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics · doi:10.6028/jres.071b.032 · Cited by 731
Learning dynamic Bayesian networks
Ghahramani, Z. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0053999 · Cited by 543
Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithm
Friedman, N., Nachman, I., & Pe’er, D. (1999) · arXiv (Cornell University) · doi:10.13140/2.1.1125.2169 · Cited by 501
Link Prediction in Relational Data
Taskar, B., Wong, M.-F., Abbeel, P., & Koller, D. (2003) · Cited by 452
Tracing information flow on a global scale using Internet chain-letter data
Liben-Nowell, D., & Kleinberg, J. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0708471105 · Cited by 422
Tracking Information Epidemics in Blogspace
Adar, E., & Adamic, L. A. (2005) · The 2005 IEEE/WIC/ACM International Conference on Web Intelligence (WI'05) · doi:10.1109/wi.2005.151 · Cited by 408
A Poissonian explanation for heavy tails in e-mail communication
Malmgren, R. D., Stouffer, D. B., Motter, A. E., & Amaral, L. A. N. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0800332105 · Cited by 397
The dynamics of viral marketing
Leskovec, J., Adamic, L. A., & Huberman, B. A. (2006) · Proceedings of the 7th ACM conference on Electronic commerce · doi:10.1145/1134707.1134732 · Cited by 391
Self-citationStructure and evolution of blogspace
Kumar, R., Novak, J., Raghavan, P., & Tomkins, A. (2004) · Communications of the ACM · doi:10.1145/1035134.1035162 · Cited by 371
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
Self-citationPatterns of Influence in a Recommendation Network
Leskovec, J., Singh, A., & Kleinberg, J. (2006) · Lecture Notes in Computer Science · doi:10.1007/11731139_44 · Cited by 307
Self-citationRecovering time-varying networks of dependencies in social and biological studies
Ahmed, A. A., & Xing, E. P. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0901910106 · Cited by 287
An Experimental Study of the Coloring Problem on Human Subject Networks
Kearns, M., Suri, S., & Montfort, N. (2006) · Science · doi:10.1126/science.1127207 · Cited by 269
The dissection of equilateral triangles into equilateral triangles
Tutte, W. T. (1948) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s030500410002449x · Cited by 267
Learning probabilistic models of link structure
Getoor, L., Friedman, N., Koller, D., & Taskar, B. (2003) · Journal of Machine Learning Research · Cited by 252
Implicit Structure and the Dynamics of Blogspace
Adar, E. (2004) · Cited by 236
Learning graphical model structure using L1-regularization paths
Schmidt, M., Niculescu-Mizil, A., & Murphy, K. J. (2007) · National Conference on Artificial Intelligence · Cited by 230
High-Dimensional Graphical Model Selection Using ell_1-Regularized Logistic Regression
Wainwright, M. J., Lafferty, J., & Ravikumar, P. (2006) · neural information processing systems · Cited by 192
Time-Varying Dynamic Bayesian Networks
Song, L., Kolar, M., & Xing, E. P. (2009) · Cited by 152
Cascading Behavior in Large Blog Graphs
Leskovec, J., McGlohon, M., Faloutsos, C., Glance, N., & Hurst, M. F. (2007) · Cited by 133
Self-citationCorrecting for missing data in information cascades
Sadikov, E., Medina, M., Leskovec, J., & García-Molina, H. (2011) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/1935826.1935844 · Cited by 128
Self-citationVert, J., & Yamanishi, Y. (2004) · neural information processing systems · Cited by 82
A framework for quantitative analysis of cascades on networks
Ghosh, R., & Lerman, K. (2011) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/1935826.1935917 · Cited by 60
What Stops Social Epidemics?Preprint
Steeg, G. V., Ghosh, R., & Lerman, K. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1102.1985 · Cited by 54
A kernel method for unsupervised structured network inference
Lippert, C., Stegle, O., Zoubin Ghahramani, A., & Borgwardt, K. M. (2009) · MDC Repository (Max-Delbrueck-Center for Molecular Medicine) · Cited by 11
Cited by
The role of social networks in information diffusion
Bakshy, E., Rosenn, I., Marlow, C., & Adamic, L. (2012) · Proceedings of the 21st international conference on World Wide Web · doi:10.1145/2187836.2187907 · Cited by 1,526
Supervised random walks: predicting and recommending links in social networks
Backstrom, L., & Leskovec, J. (2011) · Proceedings of the fourth ACM international conference on Web search and data mining · doi:10.1145/1935826.1935914 · Cited by 982
Self-citationWho says what to whom on twitter
Wu, S., Hofman, J. M., Mason, W. A., & Watts, D. J. (2011) · Proceedings of the 20th international conference on World wide web · doi:10.1145/1963405.1963504 · Cited by 957
SNAP: A General-Purpose Network Analysis and Graph-Mining Library
Leskovec, J., & Sosič, R. (2017) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/2898361 · Cited by 870
Self-citationSocial big data: recent achievements and new challenges
Bello-Orgaz, G., Jung, J. J., & Camacho, D. (2016) · Information Fusion · doi:10.1016/j.inffus.2015.08.005 · Cited by 846
“The NETINT method [78] has applied sub-modular, function-based iterative optimisation to discover the spreading cascade (path) that maximises the likelihood of the collected dataset.”
Method
Metadata
- Authors
- Gomez Rodriguez, M., Leskovec, J., & Krause, A.
- Venue
- Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining
- Publisher
- ACM
- Published
- 2010-07-25
- Pages
- 1019-1028
- OpenAlex
- W1996816151
- Cited by
- 679
- References
- 67
- FWCI
- 39.64
- 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.