{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T11:02:24Z","timestamp":1782126144974,"version":"3.54.5"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2007,3,1]],"date-time":"2007-03-01T00:00:00Z","timestamp":1172707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2007,3]]},"abstract":"<jats:p>How do real graphs evolve over time? What are normal growth patterns in social, technological, and information networks? Many studies have discovered patterns in<jats:italic>static graphs<\/jats:italic>, 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.<\/jats:p><jats:p>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 superlinearly 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<jats:italic>O<\/jats:italic>(log<jats:italic>n<\/jats:italic>) or<jats:italic>O<\/jats:italic>(log(log<jats:italic>n<\/jats:italic>)).<\/jats:p><jats:p>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.<\/jats:p><jats:p>We also notice that the forest fire model exhibits a sharp transition between sparse graphs and graphs that are densifying. Graphs with decreasing distance between the nodes are generated around this transition point.<\/jats:p><jats:p>Last, we analyze the connection between the temporal evolution of the degree distribution and densification of a graph. We find that the two are fundamentally related. We also observe that real networks exhibit this type of relation between densification and the degree distribution.<\/jats:p>","DOI":"10.1145\/1217299.1217301","type":"journal-article","created":{"date-parts":[[2007,6,8]],"date-time":"2007-06-08T15:00:08Z","timestamp":1181314808000},"page":"2","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2052,"title":["Graph evolution"],"prefix":"10.1145","volume":"1","author":[{"given":"Jure","family":"Leskovec","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jon","family":"Kleinberg","sequence":"additional","affiliation":[{"name":"Cornell University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos","family":"Faloutsos","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2004.03.012"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 6th Annual European Symposium on Algorithms. Springer-Verlag, 332--343","author":"Abello J.","unstructured":"Abello , J. , Buchsbaum , A. L. , and Westbrook , J . 1998. A functional approach to external graph algorithms . In Proceedings of the 6th Annual European Symposium on Algorithms. Springer-Verlag, 332--343 .]] Abello, J., Buchsbaum, A. L., and Westbrook, J. 1998. A functional approach to external graph algorithms. In Proceedings of the 6th Annual European Symposium on Algorithms. Springer-Verlag, 332--343.]]"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Abello J. Pardalos P. M. and Resende M. G. C. 2002. Handbook of Massive Data Sets. Kluwer Academic Publishing.]] Abello J. Pardalos P. M. and Resende M. G. C. 2002. Handbook of Massive Data Sets. Kluwer Academic Publishing.]]","DOI":"10.1007\/978-1-4615-0005-6"},{"key":"e_1_2_1_4_1","unstructured":"Adamic L. A. 2000. Zipf power-law pareto---a ranking tutorial. http:\/\/www.hpl.hp.com\/research\/idl\/papers\/ranking.]] Adamic L. A. 2000. Zipf power-law pareto---a ranking tutorial. http:\/\/www.hpl.hp.com\/research\/idl\/papers\/ranking.]]"},{"key":"e_1_2_1_5_1","volume-title":"-L","author":"Albert R.","year":"1999","unstructured":"Albert , R. and Barabasi , A . -L . 1999 . Emergence of scaling in random networks. Science . 509--512.]] Albert, R. and Barabasi, A.-L. 1999. Emergence of scaling in random networks. Science. 509--512.]]"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/43601"},{"key":"e_1_2_1_7_1","first-page":"4","article-title":"Towards a theory of scale-free graphs: Definition, properties, and implications","volume":"2","author":"Alderson D.","year":"2005","unstructured":"Alderson , D. , Doyle , J. C. , Li , L. , and Willinger , W. 2005 . Towards a theory of scale-free graphs: Definition, properties, and implications . Internet Math. 2 , 4 .]] Alderson, D., Doyle, J. C., Li, L., and Willinger, W. 2005. Towards a theory of scale-free graphs: Definition, properties, and implications. Internet Math. 2, 4.]]","journal-title":"Internet Math."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502521"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0002-2"},{"key":"e_1_2_1_10_1","volume-title":"Computer Networks: The International Journal of Computer and Telecommunications Netowrking","author":"Broder A.","year":"2000","unstructured":"Broder , A. , Kumar , R. , Maghoul , F. , Raghavan , P. , Rajagopalan , S. , Stata , R. , Tomkins , A. , and Wiener , J . 2000 a. Graph structure in the Web. In Proceedings of the 9th International World Wide Web Conference on Computer Networks: The International Journal of Computer and Telecommunications Netowrking . North-Holland Publishing Co., Amsterdam, The Netherlands , 309--320.]] Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., and Wiener, J. 2000a. Graph structure in the Web. In Proceedings of the 9th International World Wide Web Conference on Computer Networks: The International Journal of Computer and Telecommunications Netowrking. North-Holland Publishing Co., Amsterdam, The Netherlands, 309--320.]]"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of World Wide Web Conference.]]","author":"Broder A.","unstructured":"Broder , A. , Kumar , R. , Maghoul , F. , Raghavan , P. , Rajagopalan , S. , Stata , R. , Tomkins , A. , and Wiener , J . 2000b. Graph structure in the web: experiments and models . In Proceedings of World Wide Web Conference.]] Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., and Wiener, J. 2000b. Graph structure in the web: experiments and models. In Proceedings of World Wide Web Conference.]]"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132952.1132954"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the SIAM Conference on Data Mining (SDM).]]","author":"Chakrabarti D.","unstructured":"Chakrabarti , D. , Zhan , Y. , and Faloutsos , C . 2004. R-mat: A recursive model for graph mining . In Proceedings of the SIAM Conference on Data Mining (SDM).]] Chakrabarti, D., Zhan, Y., and Faloutsos, C. 2004. R-mat: A recursive model for graph mining. In Proceedings of the SIAM Conference on Data Mining (SDM).]]"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.252631999"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10084"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.63.025101"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspb.2001.1824"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Dorogovtsev S. and Mendes J. 2002. Accelerated growth of networks. In Handbook of Graphs and Networks: From the Genome to the Internet S. Bornholdt and H.G. Schuster. Eds. Wiley-VCH Berlin Germany.]] Dorogovtsev S. and Mendes J. 2002. Accelerated growth of networks. In Handbook of Graphs and Networks: From the Genome to the Internet S. Bornholdt and H.G. Schuster. Eds. Wiley-VCH Berlin Germany.]]","DOI":"10.1002\/3527602755.ch14"},{"key":"e_1_2_1_19_1","unstructured":"Dorogovtsev S. and Mendes J. 2003. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press Oxford UK.]] Dorogovtsev S. and Mendes J. 2003. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press Oxford UK.]]"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316229"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/980972.980992"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Hall B. H. Jaffe A. B. and Trajtenberg M. 2001. The nber patent citation data file: Lessons insights and methodological tools. NBER Working Papers 8498 National Bureau of Economic Research Inc. (Oct.)]] Hall B. H. Jaffe A. B. and Trajtenberg M. 2001. The nber patent citation data file: Lessons insights and methodological tools. NBER Working Papers 8498 National Bureau of Economic Research Inc. (Oct.)]]","DOI":"10.3386\/w8498"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1038\/43604"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0048-7333(99)00010-4"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1207\/s15366359mea0301_3"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Kleinberg J. M. 2002. Small-world phenomena and the dynamics of information. In Advances in Neural Information Processing Systems 14.]] Kleinberg J. M. 2002. Small-world phenomena and the dynamics of information. In Advances in Neural Information Processing Systems 14.]]","DOI":"10.7551\/mitpress\/1120.003.0060"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the International Conference on Combinatorics and Computing. 1--17","author":"Kleinberg J. M.","unstructured":"Kleinberg , J. M. , Kumar , R. , Raghavan , P. , Rajagopalan , S. , and Tomkins , A . 1999. The Web as a graph: Measurements, models, and methods . In Proceedings of the International Conference on Combinatorics and Computing. 1--17 .]] Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., and Tomkins, A. 1999. The Web as a graph: Measurements, models, and methods. In Proceedings of the International Conference on Combinatorics and Computing. 1--17.]]"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1116869"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.63.066123"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.036118"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796570"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00040-7"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134732"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the European International Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD'05)","author":"Leskovec J.","unstructured":"Leskovec , J. , Chakrabarti , D. , Kleinberg , J. M. , and Faloutsos , C . 2005. Realistic, mathematically tractable graph generation and evolution, using kronecker multiplication . In Proceedings of the European International Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD'05) . 133--145.]] Leskovec, J., Chakrabarti, D., Kleinberg, J. M., and Faloutsos, C. 2005. Realistic, mathematically tractable graph generation and evolution, using kronecker multiplication. In Proceedings of the European International Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD'05). 133--145.]]"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150479"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.212348399"},{"key":"e_1_2_1_38_1","first-page":"60","article-title":"The small-world problem. Psycholo","volume":"2","author":"Milgram S.","year":"1967","unstructured":"Milgram , S. 1967 . The small-world problem. Psycholo . Today 2 , 60 -- 67 .]] Milgram, S. 1967. The small-world problem. Psycholo. Today 2, 60--67.]]","journal-title":"Today"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129088"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1080\/00107510500052444"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988674"},{"key":"e_1_2_1_43_1","unstructured":"Oregon. 1997. University of Oregon route views project. online data and reports. http:\/\/www.routeviews.org.]] Oregon. 1997. University of Oregon route views project. online data and reports. http:\/\/www.routeviews.org.]]"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775059"},{"key":"e_1_2_1_45_1","unstructured":"Redner S. 2004. Citation statistics from more than a century of physical review. Tech. rep. physics\/0407137 arXiv.]] Redner S. 2004. Citation statistics from more than a century of physical review. Tech. rep. physics\/0407137 arXiv.]]"},{"key":"e_1_2_1_46_1","volume-title":"Chaos","author":"Schroeder M.","unstructured":"Schroeder , M. 1991. Fractals , Chaos , Power Laws : Minutes from an Infinite Paradise. W.H. Freeman and Company , New York, NY.]] Schroeder, M. 1991. Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise. W.H. Freeman and Company, New York, NY.]]"},{"key":"e_1_2_1_47_1","unstructured":"Tauro S. L. Palmer C. Siganos G. and Faloutsos M. 2001. A simple conceptual model for the internet topology. In Global Internet. San Antonio TX.]] Tauro S. L. Palmer C. Siganos G. and Faloutsos M. 2001. A simple conceptual model for the internet topology. In Global Internet. San Antonio TX.]]"},{"key":"e_1_2_1_48_1","first-page":"430","article-title":"Disordered networks generated by recursive searches. Europhy","volume":"54","author":"Vazquez A.","year":"2001","unstructured":"Vazquez , A. 2001 . Disordered networks generated by recursive searches. Europhy . Lett. 54 , 4, 430 -- 435 .]] Vazquez, A. 2001. Disordered networks generated by recursive searches. Europhy. Lett. 54, 4, 430--435.]]","journal-title":"Lett."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.67.056104"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1070120"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1217299.1217301","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1217299.1217301","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:29:33Z","timestamp":1750285773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1217299.1217301"}},"subtitle":["Densification and shrinking diameters"],"short-title":[],"issued":{"date-parts":[[2007,3]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,3]]}},"alternative-id":["10.1145\/1217299.1217301"],"URL":"https:\/\/doi.org\/10.1145\/1217299.1217301","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,3]]},"assertion":[{"value":"2007-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}