Graphs over time: densification laws, shrinking diameters and possible explanations
Abstract
How do real graphs evolve over time? What are "normal" growth patterns in social, technological, and information networks? Many studies have discovered patterns in static graphs, identifying properties in a single snapshot of a large network, or in a very small number of snapshots; these include heavy tails for in- and out-degree distributions, communities, small-world phenomena, and others. However, given the lack of information about network evolution over long periods, it has been hard to convert these findings into statements about trends over time.Here we study a wide range of real graphs, and we observe some surprising phenomena. First, most of these graphs densify over time, with the number of edges growing super-linearly in the number of nodes. Second, the average distance between nodes often shrinks over time, in contrast to the conventional wisdom that such distance parameters should increase slowly as a function of the number of nodes (like O(log n) or O(log(log n)).Existing graph generation models do not exhibit these types of behavior, even at a qualitative level. We provide a new graph generator, based on a "forest fire" spreading process, that has a simple, intuitive justification, requires very few parameters (like the "flammability" of nodes), and produces graphs exhibiting the full range of properties observed both in prior work and in the present study.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The study of networks in a variety of applications assumes static networks, with some notable exceptions.
“Finally, the study of networks in a variety of applications assumes static networks, with some notable exceptions.21”
From A Big Data Guide to Understanding Climate Change: The Case for Theory-Guided Data Science (2014) · cites this paper as [21]
Cites
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060 · see citing works
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 · see citing works
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719 · see citing works
Milgram, S. (1967) · PsycEXTRA Dataset · doi:10.1037/e400002009-005 · Cited by 5,528 · see citing works
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · doi:10.1145/316188.316229 · Cited by 4,245 · see citing works
Self-citationDiameter of the World-Wide Web
Albert, R., Jeong, H., & Barabási, A.-Ĺ. (1999) · Nature · doi:10.1038/43601 · Cited by 4,240 · see citing works
The NBER Patent Citation Data File: Lessons, Insights and Methodological Tools
Hall, B. H., Jaffe, A. B., & Trajtenberg, M. (2001) · National Bureau of Economic Research · doi:10.3386/w8498 · Cited by 3,659 · see citing works
A Brief History of Generative Models for Power Law and Lognormal Distributions
Mitzenmacher, M. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129088 · Cited by 1,809 · see citing works
R-MAT: A Recursive Model for Graph Mining
Chakrabarti, D., Zhan, Y., & Faloutsos, C. (2004) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972740.43 · Cited by 1,275 · see citing works
Self-citationIdentity and Search in Social Networks
Watts, D. J., Dodds, P. S., & Newman, M. E. J. (2002) · Science · doi:10.1126/science.1070120 · Cited by 1,060 · see citing works
The NBER Patent Citations Data File: Lessons, Insights and Methodological Tools
Hall, B. H., Jaffe, A. B., & Trajtenberg, M. (2001) · Cited by 1,030 · see citing works
The Web as a Graph: Measurements, Models, and Methods
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48686-0_1 · Cited by 1,027 · see citing works
Self-citationTrawling the Web for emerging cyber-communities
Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (1999) · Computer Networks · doi:10.1016/s1389-1286(99)00040-7 · Cited by 999 · see citing works
The average distances in random graphs with given expected degrees
Chung, F., & Lü, L. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.252631999 · Cited by 891 · see citing works
Growth dynamics of the World-Wide Web
Huberman, B. A., & Adamic, L. A. (1999) · Nature · doi:10.1038/43604 · Cited by 868 · see citing works
Fractals, chaos, power laws: minutes from an infinite paradise
(1992) · Choice Reviews Online · doi:10.5860/choice.29-2770 · Cited by 811 · see citing works
Stochastic models for the Web graph
Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., & Upfal, E. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892065 · Cited by 682 · see citing works
The Diameter of a Scale-Free Random Graph
Bollob�s*, B., & Riordan, O. M. (2004) · COMBINATORICA · doi:10.1007/s00493-004-0002-2 · Cited by 597 · see citing works
Ntoulas, A., Cho, J. J., & Olston, C. (2004) · International World Wide Web Conference (WWW) · doi:10.1145/988672.988674 · Cited by 452 · see citing works
Small-World Phenomena and the Dynamics of Information
Kleinberg, J. M. (2002) · The MIT Press eBooks · doi:10.7551/mitpress/1120.003.0060 · Cited by 386 · see citing works
Self-citationCooper, C., & FRIEZE, A. M. (2003) · Random Structures and Algorithms · doi:10.1002/rsa.10084 · Cited by 345 · see citing works
Abello, J. M. (2002) · Massive computing · doi:10.1007/978-1-4615-0005-6 · Cited by 290 · see citing works
Gehrke, J. E., Ginsparg, P., & Kleinberg, J. M. (2003) · ACM SIGKDD Explorations Newsletter · doi:10.1145/980972.980992 · Cited by 285 · see citing works
Self-citationPalmer, C. R., Gibbons, P. B., & Faloutsos, C. (2002) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/775047.775059 · Cited by 266 · see citing works
Self-citationThe self-similar science system
Katz, J. S. (1999) · Research Policy · doi:10.1016/s0048-7333(99)00010-4 · Cited by 133 · see citing works
The "DGX" distribution for mining massive, skewed data
Bi, Z., Faloutsos, C., & Korn, F. R. (2001) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/502512.502521 · Cited by 118 · see citing works
Self-citationA Functional Approach to External Graph Algorithms
Abello, Buchsbaum, & Westbrook (2002) · Algorithmica · doi:10.1007/s00453-001-0088-5 · Cited by 108 · see citing works
Growing and navigating the small world Web by local content
Menczer, F. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.212348399 · Cited by 104 · see citing works
Citation Statistics From More Than a Century of Physical ReviewPreprint
Redner, S. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.physics/0407137 · Cited by 74 · see citing works
Scale-Independent Bibliometric Indicators
Katz, J. S. (2005) · Measurement Interdisciplinary Research and Perspectives · doi:10.1207/s15366359mea0301_3 · Cited by 46 · see citing works
Citation Statistics From More Than a Century of Physical ReviewPreprint
Redner, S. (2005) · Cited by 27 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293 · see citing works
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 · see citing works
Controllability of complex networks
Liu, Y., Slotine, J.-J. E., & Barabási, A.-Ĺ. (2011) · Nature · doi:10.1038/nature10011 · Cited by 3,238 · see citing works
Leskovec, J., Kleinberg, J. M., & Faloutsos, C. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217301 · Cited by 2,494 · see citing works
Self-citationLeskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2009) · Internet Mathematics · doi:10.1080/15427951.2009.10129177 · Cited by 1,867 · see citing works
Self-citationGraph based anomaly detection and description: a survey
Akoglu, L., Tong, H., & Koutra, D. (2015) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-014-0365-y · Cited by 1,504 · see citing works
The Origins of Scaling in Cities
Bettencourt, L. M. A. (2013) · Science · doi:10.1126/science.1235823 · Cited by 1,498 · see citing works
Asymmetric Transitivity Preserving Graph Embedding
Ou, M., Cui, P., Pei, J., Zhang, Z., & Zhu, W. (2016) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2939672.2939751 · Cited by 1,298 · see citing works
Higher-order organization of complex networks
Benson, A. R., Gleich, D. F., & Leskovec, J. (2016) · Science · doi:10.1126/science.aad9029 · Cited by 1,284 · see citing works
Self-citationLeskovec, J., & Faloutsos, C. (2006) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1150402.1150479 · Cited by 1,190 · see citing works
Self-citationYanardag, P., & Vishwanathan, S. V. N. (2015) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2783258.2783417 · Cited by 1,108 · see citing works
Structure and evolution of online social networks
Kumar, R., Novak, J., & Tomkins, A. (2006) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1150402.1150476 · Cited by 1,091 · see citing works
Bäckström, L., & Leskovec, J. (2011) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/1935826.1935914 · Cited by 979 · see citing works
Self-citationData Mining: Concepts and Techniques (2nd edition)
Han, J., & Kamber, M. (2006) · Cited by 968 · see citing works
Analysis of topological characteristics of huge online social networking services
Ahn, Y., Han, S., Kwak, H., Moon, S. B., & Jeong, H. (2007) · International World Wide Web Conference (WWW) · doi:10.1145/1242572.1242685 · Cited by 955 · see citing works
Leskovec, J., & Sosič, R. (2016) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/2898361 · Cited by 885 · see citing works
Self-citationStatistical properties of community structure in large social and information networks
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2008) · International World Wide Web Conference (WWW) · doi:10.1145/1367497.1367591 · Cited by 862 · see citing works
Self-citationA Survey of Statistical Network Models
Goldenberg, A., Zheng, A. X., Fienberg, S. E., & Airoldi, E. M. (2010) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000005 · Cited by 815 · see citing works
Qiu, J., Chen, Q., Dong, Y., Zhang, J., Yang, H., Ding, M., Wang, K., & Tang, J. (2020) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3394486.3403168 · Cited by 834 · see citing works
Kronecker Graphs: An Approach to Modeling NetworksPreprint
Leskovec, J., Chakrabarti, D., Kleinberg, J. M., Faloutsos, C., & Zoubin Ghahramani, A. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0812.4905 · Cited by 836 · see citing works
Self-citationInformation contagion: an empirical study of the spread of news on digg and twitter social networks
Lerman, K., & Ghosh, R. (2010) · Proceedings of the International AAAI Conference on Web and Social Media · doi:10.1609/icwsm.v4i1.14021 · Cited by 813 · see citing works
Collaborative Filtering beyond the User-Item Matrix
Shi, Y., Larson, M., & Hanjalić, A. (2014) · ACM Computing Surveys · doi:10.1145/2556270 · Cited by 805 · see citing works
4 Community Detection in Networks with Node Attributes
Yang, J., McAuley, J., & Leskovec, J. (2013) · Cited by 797 · see citing works
Self-citationInferring networks of diffusion and influence
Gomez-Rodriguez, M., Leskovec, J., & Krause, A. (2010) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1835804.1835933 · Cited by 699 · see citing works
Self-citationChakrabarti, D., & Faloutsos, C. (2006) · ACM Computing Surveys · doi:10.1145/1132952.1132954 · Cited by 606 · see citing works
Self-citationManaging and Mining Graph Data
Aggarwal, C. C., & Wang, H. (2010) · The Kluwer international series on advances in database systems · doi:10.1007/978-1-4419-6045-0 · Cited by 597 · see citing works
Zafarani, R., Abbasi, M. A., & Liu, H. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781139088510 · Cited by 608 · see citing works
A Survey of Link Prediction in Social Networks
Hasan, M. A., & Zaki, M. J. (2011) · Springer eBooks · doi:10.1007/978-1-4419-8462-3_9 · Cited by 571 · see citing works
Evolutionary dynamics on any population structure
Allen, B., Lippner, G., Chen, Y.-T., Fotouhi, B., Momeni, N., Yau, S.-T., & Nowak, M. A. (2017) · Nature · doi:10.1038/nature21723 · Cited by 534 · see citing works
Sun, J., Faloutsos, C., Papadimitriou, S., & Yu, P. S. (2007) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1281192.1281266 · Cited by 532 · see citing works
Self-citationLink prediction techniques, applications, and performance: A survey
Kumar, A., Singh, S. S., Singh, K., & Biswas, B. (2020) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2020.124289 · Cited by 525 · see citing works
Social network analysis: An overview
Tabassum, S., Pereira, F. S. F., Fernandes, S., & Gama, J. (2018) · Wiley Interdisciplinary Reviews Data Mining and Knowledge Discovery · doi:10.1002/widm.1256 · Cited by 513 · see citing works
Community Discovery in Dynamic Networks
Rossetti, G., & Cazabet, R. (2018) · ACM Computing Surveys · doi:10.1145/3172867 · Cited by 512 · see citing works
dyngraph2vec: Capturing network dynamics using dynamic graph representation learning
Goyal, P., Chhetri, S. R., & Canedo, A. (2019) · Knowledge-Based Systems · doi:10.1016/j.knosys.2019.06.024 · Cited by 468 · see citing works
Main-memory triangle computations for very large (sparse (power-law)) graphs
Matthieu Latapy, B. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.07.017 · Cited by 455 · see citing works
Inferring Networks of Diffusion and Influence
Gomez-Rodriguez, M., Leskovec, J., & Krause, A. (2012) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/2086737.2086741 · Cited by 451 · see citing works
Self-citationStructure and Evolution of Online Social Networks
Kumar, R., Novak, J., & Tomkins, A. (2010) · Springer eBooks · doi:10.1007/978-1-4419-6515-8_13 · Cited by 438 · see citing works
The science of science: From the perspective of complex systems
Zeng, A., Shen, Z., Zhou, J., Wu, J., Fan, Y., Wang, Y., & Stanley, E. (2017) · Physics Reports · doi:10.1016/j.physrep.2017.10.001 · Cited by 406 · see citing works
Patterns and dynamics of users' behavior and interaction: Network analysis of an online community
Panzarasa, P., Opsahl, T., & Carley, K. M. (2009) · Journal of the American Society for Information Science and Technology · doi:10.1002/asi.21015 · Cited by 416 · see citing works
Lin, Y., Chi, Y., Shenghuo Zhu, B., Sundaram, H., & Tseng, B. L. (2008) · International World Wide Web Conference (WWW) · doi:10.1145/1367497.1367590 · Cited by 408 · see citing works
Sybil Attacks and Their Defenses in the Internet of Things
Zhang, K., Liang, X., Lu, R., & Shen, X. (2014) · IEEE Internet of Things Journal · doi:10.1109/jiot.2014.2344013 · Cited by 403 · see citing works
Fast exact shortest-path distance queries on large networks by pruned landmark labeling
Akiba, T., Iwata, Y., & Yoshida, Y. (2013) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2463676.2465315 · Cited by 404 · see citing works
A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning
Jin, D., Yu, Z., Jiao, P., Pan, S., He, D., Wu, J. X., Yu, P., & Zhang, W. (2021) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2021.3104155 · Cited by 410 · see citing works
Topic modeling with network regularization
Mei, Q., Cai, D., Zhang, D., & Zhai, C. (2008) · International World Wide Web Conference (WWW) · doi:10.1145/1367497.1367512 · Cited by 396 · see citing works
Accurate Estimation of the Degree Distribution of Private Networks
Hay, M., Li, C., Miklau, G., & Jensen, D. D. (2009) · Proceedings · doi:10.1109/icdm.2009.11 · Cited by 394 · see citing works
Control Profiles of Complex Networks
Ruths, J., & Ruths, D. A. (2014) · Science · doi:10.1126/science.1242063 · Cited by 393 · see citing works
The dynamics of viral marketing
Leskovec, J., Adamic, L. A., & Huberman, B. A. (2006) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1134707.1134732 · Cited by 391 · see citing works
Self-citationSocial Network Analysis and Mining for Business Applications
Bonchi, F., Castillo, C., Gionis, A., & Jaimes, A. (2011) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/1961189.1961194 · Cited by 361 · see citing works
Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication
Leskovec, J., Chakrabarti, D., Kleinberg, J. M., & Faloutsos, C. (2005) · Lecture notes in computer science · doi:10.1007/11564126_17 · Cited by 362 · see citing works
Self-citationThe convergence of social and technological networks
Kleinberg, J. M. (2008) · Communications of the ACM · doi:10.1145/1400214.1400232 · Cited by 346 · see citing works
Self-citationFoundations and Modeling of Dynamic Networks Using Dynamic Graph Neural Networks: A Survey
Skarding, J., Gabryś, B., & Musiał, K. (2021) · IEEE Access · doi:10.1109/access.2021.3082932 · Cited by 337 · see citing works
Efficient semi-streaming algorithms for local triangle counting in massive graphs
Becchetti, L., Boldi, P., Castillo, C., & Gionis, A. (2008) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1401890.1401898 · Cited by 317 · see citing works
Detecting communities and their evolutions in dynamic social networks—a Bayesian approach
Yang, T., Chi, Y., Shenghuo Zhu, B., Gong, Y., & Jin, R. (2010) · Machine Learning · doi:10.1007/s10994-010-5214-7 · Cited by 318 · see citing works
Aggarwal, C. C., & Subbian, K. (2014) · ACM Computing Surveys · doi:10.1145/2601412 · Cited by 313 · see citing works
Information network or social network?
Myers, S. A., Sharma, A., Gupta, P. K., & Lin, J. (2014) · International World Wide Web Conference (WWW) · doi:10.1145/2567948.2576939 · Cited by 313 · see citing works
An Introduction to Social Network Data Analytics
Aggarwal, C. C. (2011) · Springer eBooks · doi:10.1007/978-1-4419-8462-3_1 · Cited by 312 · see citing works
Graph Evolution: Densification and Shrinking DiametersPreprint
Leskovec, J., Kleinberg, J. M., & Faloutsos, C. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.physics/0603229 · Cited by 346 · see citing works
Self-citationAnalyzing communities and their evolutions in dynamic social networks
Lin, Y., Chi, Y., Shenghuo Zhu, B., Sundaram, H., & Tseng, B. L. (2009) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1514888.1514891 · Cited by 296 · see citing works
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 · see citing works
Graph Summarization Methods and Applications
Liu, Y., Safavi, T., Dighe, A., & Koutra, D. (2018) · ACM Computing Surveys · doi:10.1145/3186727 · Cited by 342 · see citing works
Prediction of emerging technologies based on analysis of the US patent citation network
Érdi, P., Makovi, K., Somogyvári, Z., Strandburg, K. J., Tobochnik, J., Volf, P., & Zalányi, L. (2012) · Scientometrics · doi:10.1007/s11192-012-0796-4 · Cited by 274 · see citing works
Efficient discovery of overlapping communities in massive networks
Gopalan, P., & Blei, D. M. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1221839110 · Cited by 272 · see citing works
Accountable internet protocol (aip)
Andersen, D. G., Balakrishnan, H., Feamster, N., Koponen, T., Moon, D., & Shenker, S. J. (2008) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1402946.1402997 · Cited by 269 · see citing works
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 268 · see citing works
Hierarchy Measure for Complex Networks
Mones, E., Vicsek, L., & Vicsek, T. (2012) · PLoS ONE · doi:10.1371/journal.pone.0033799 · Cited by 259 · see citing works
An Evolutionary Multiobjective Approach for Community Discovery in Dynamic Networks
Folino, F., & Pizzuti, C. (2013) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2013.131 · Cited by 265 · see citing works
A survey of Twitter research: Data model, graph structure, sentiment analysis and attacks
Antonakaki, D., Fragopoulou, P., & Ioannidis, S. (2020) · Expert Systems with Applications · doi:10.1016/j.eswa.2020.114006 · Cited by 279 · see citing works
A framework for analysis of dynamic social networks
Berger-Wolf, T. Y., & Saia, J. (2006) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1150402.1150462 · Cited by 258 · see citing works
Ranking the spreading influence in complex networks
Liu, J.-G., Ren, Z.-M., & Guo, Q. (2013) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2013.04.037 · Cited by 256 · see citing works
Learning Discrete Structures for Graph Neural NetworksPreprint
Franceschi, L., Niepert, M., Pontil, M., & He, X. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1903.11960 · Cited by 264 · see citing works
Toward the dynamic interactome: it's about time
Przytycka, T. M., Singh, M., & Slonim, D. K. (2010) · Briefings in Bioinformatics · doi:10.1093/bib/bbp057 · Cited by 252 · see citing works
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 · see citing works
Clustering attributed graphs: Models, measures and methods
Bothorel, C., Gomez, J. D. C., Magnani, M., & Micenková, B. (2015) · Network Science · doi:10.1017/nws.2015.9 · Cited by 249 · see citing works
Optimizing controllability of complex networks by minimum structural perturbations
Wang, W.-X., Ni, X., Lai, Y., & Grebogi, C. (2012) · Physical Review E · doi:10.1103/physreve.85.026115 · Cited by 248 · see citing works
Community evolution in dynamic multi-mode networks
Tang, L., Liu, H., Zhang, J., & Nazeri, Z. (2008) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1401890.1401972 · Cited by 248 · see citing works
CANE: Context-Aware Network Embedding for Relation Modeling
Tu, C., Liu, H., Liu, Z., & Sun, M. (2017) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.18653/v1/p17-1158 · Cited by 246 · see citing works
On predicting the popularity of newly emerging hashtags in T witter
Ma, Z., Sun, A., & Cong, G. (2013) · Journal of the American Society for Information Science and Technology · doi:10.1002/asi.22844 · Cited by 246 · see citing works
A particle-and-density based evolutionary clustering method for dynamic networks
Kim, M.-S., & Han, J. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687698 · Cited by 244 · see citing works
It's who you know: graph mining using recursive structural features
Henderson, K., Gallagher, B., Li, L., Akoglu, L., Eliassi-Rad, T., Tong, H., & Faloutsos, C. (2011) · Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2020408.2020512 · Cited by 223 · see citing works
Self-citationA Big Data Guide to Understanding Climate Change: The Case for Theory-Guided Data Science
Faghmous, J. H., & Kumar, V. (2014) · Big Data · doi:10.1089/big.2014.0026 · Cited by 223 · see citing works
Lattanzi, S., Moseley, B., Suri, S., & Vassilvitskii, S. (2011) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1989493.1989505 · Cited by 226 · see citing works
The dynamic nature of contact networks in infectious disease epidemiology
Bansal, S., Read, J. M., Pourbohloul, B., & Ancel, L. W. (2010) · Journal of Biological Dynamics · doi:10.1080/17513758.2010.503376 · Cited by 225 · see citing works
The Network Completion Problem: Inferring Missing Nodes and Edges in Networks
Kim, M., & Leskovec, J. (2011) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972818.5 · Cited by 221 · see citing works
Self-citationEmergence of bimodality in controlling complex networks
Jia, T., Liu, Y., Csóka, E., Pósfai, M., Slotine, J.-J. E., & Barabási, A.-Ĺ. (2013) · Nature Communications · doi:10.1038/ncomms3002 · Cited by 216 · see citing works
Crawling Facebook for social network analysis purposes
Catanese, S., Meo, P. D., Ferrara, E., Fiumara, G., & Provetti, A. (2011) · International Conference on Web Intelligence, Mining and Semantics · doi:10.1145/1988688.1988749 · Cited by 219 · see citing works
Prediction and ranking algorithms for event-based network data
O’Madadhain, J., Hutchins, J., & Smyth, P. (2005) · ACM SIGKDD Explorations Newsletter · doi:10.1145/1117454.1117458 · Cited by 218 · see citing works
Scientific workflows for bibliometrics
Güler, A. T., Waaijer, C. J. F., & Palmblad, M. (2016) · Scientometrics · doi:10.1007/s11192-016-1885-6 · Cited by 215 · see citing works
Ranking stability and super-stable nodes in complex networks
Ghoshal, G., & Barabási, A.-Ĺ. (2011) · Nature Communications · doi:10.1038/ncomms1396 · Cited by 196 · see citing works
The bursty dynamics of the Twitter information network
Myers, S. A., & Leskovec, J. (2014) · International World Wide Web Conference (WWW) · doi:10.1145/2566486.2568043 · Cited by 206 · see citing works
Self-citationOn Unbiased Sampling for Unstructured Peer-to-Peer Networks
Stutzbach, D., Rejaie, R., Duffield, N. G., Sen, S. B., & Willinger, W. (2008) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2008.2001730 · Cited by 206 · see citing works
Understanding the influence of all nodes in a network
Lawyer, G. (2015) · Scientific Reports · doi:10.1038/srep08665 · Cited by 201 · see citing works
Structural Information and Dynamical Complexity of Networks
Li, A., & Pan, Y. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2555904 · Cited by 200 · see citing works
CoFIM: A community-based framework for influence maximization on large-scale networks
Shang, J., Zhou, S., Li, X., Liu, L., & Wu, H. (2016) · Knowledge-Based Systems · doi:10.1016/j.knosys.2016.09.029 · Cited by 196 · see citing works
Validity Issues in the Use of Social Network Analysis with Digital Trace Data
University of Texas at Austin, Howison, J., Wiggins, A., Syracuse University, Crowston, K., & Syracuse University (2011) · Journal of the Association for Information Systems · doi:10.17705/1jais.00282 · Cited by 369 · see citing works
Modeling complex systems with adaptive networks
Sayama, H., Pestov, I., Schmidt, J., Bush, B. J., Wong, C., Yamanoi, J., & Groß, T. (2013) · Computers & Mathematics with Applications · doi:10.1016/j.camwa.2012.12.005 · Cited by 187 · see citing works
Measuring the mixing time of social graphs
Mohaisen, A., Yun, A., & Kim, Y. (2010) · ACM Internet Measurement Conference (IMC) · doi:10.1145/1879141.1879191 · Cited by 183 · see citing works
Accountable internet protocol (aip)
Andersen, D. G., Balakrishnan, H., Feamster, N., Koponen, T., Moon, D., & Shenker, S. J. (2008) · ACM SIGCOMM Conference (SIGCOMM) · doi:10.1145/1402958.1402997 · Cited by 191 · see citing works
An overview of social network analysis
Oliveira, M., & da Gama, J. M. P. (2012) · Wiley Interdisciplinary Reviews Data Mining and Knowledge Discovery · doi:10.1002/widm.1048 · Cited by 191 · see citing works
ROLAND: Graph Learning Framework for Dynamic Graphs
You, J., Du, T., & Leskovec, J. (2022) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3534678.3539300 · Cited by 194 · see citing works
Self-citationScalable and parallelizable processing of influence maximization for large-scale social networks?
Kim, J., Kim, S.-K., & Yu, H. (2013) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2013.6544831 · Cited by 188 · see citing works
- Authors
- Leskovec, J., Kleinberg, J., & Faloutsos, C.
- Affiliations
- Carnegie Mellon University (US)
- Cornell University (US)
- Venue
- Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining
- Publisher
- ACM
- Published
- 2005-08-21
- Pages
- 177-187
- OpenAlex
- W2111708605
- Cited by
- 2,281
- References
- 31
- Citations by year
- 2026: 42 · 2025: 88 · 2024: 78 · 2023: 79 · 2022: 85 · 2021: 135 · 2020: 118 · 2019: 128 · 2018: 146 · 2017: 127 · 2016: 157 · 2015: 164 · 2014: 166 · 2013: 168 · 2012: 155
- FWCI
- 77.15
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) (publishedVersion)
- Topics
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Graph Theory and Algorithms
- Physical Sciences › Mathematics › Geometry and Topology › Graph theory and applications
- Keywords
- graph evolution, network densification, superlinear growth, forest fire model, social networks, technological networks, information networks, small-world effect, degree distribution, community structure
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
