Graph evolution: Densification and shrinking diameters

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 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 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.

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.

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.

REFERENCES

• 1: Abello, J. 2004. Hierarchical graph maps. Comput. Graph. 28, 3, 345--359.
• 2: James Abello , Adam L. Buchsbaum , Jeffery Westbrook, A Functional Approach to External Graph Algorithms, Proceedings of the 6th Annual European Symposium on Algorithms, p.332-343, August 24-26, 1998
• 3: James Abello , Panos M. Pardalos , Mauricio G. C. Resende, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
• 4: Adamic, L. A. 2000. Zipf, power-law, pareto---a ranking tutorial. http://www.hpl.hp.com/research/idl/papers/ranking.
• 5: Albert, R. and Barabasi, A.-L. 1999. Emergence of scaling in random networks. Science. 509--512.
• 6: Albert, R., Jeong, H., and Barabasi, A.-L. 1999. Diameter of the World-Wide Web. Nature 401, 130--131.
• 7: 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.
• 8: Zhiqiang Bi , Christos Faloutsos , Flip Korn, The "DGX" distribution for mining massive, skewed data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.17-26, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502521]
• 9: Bélaa Bollobás , Oliver Riordan, The Diameter of a Scale-Free Random Graph, Combinatorica, v.24 n.1, p.5-34, January 2004 [doi>10.1007/s00493-004-0002-2]
• 10: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
• 11: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
• 12: Deepayan Chakrabarti , Christos Faloutsos, Graph mining: Laws, generators, and algorithms, ACM Computing Surveys (CSUR), v.38 n.1, p.2-es, 2006 [doi>http://doi.acm.org/10.1145/1132952.1132954]
• 13: 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).
• 14: Chung, F. and Lu, L. 2002. The average distances in random graphs with given expected degrees. Proceedings of the National Academy of Sciences 99, 25, 15879--15882.
• 15: Colin Cooper , Alan Frieze, A general model of web graphs, Random Structures & Algorithms, v.22 n.3, p.311-335, May 2003 [doi>10.1002/rsa.10084]
• 16: Dorogovtsev, S. and Mendes, J. 2001a. Effect of the accelerated growth of communications networks on their structure. Phys. Rev. E 63, 025101.
• 17: Dorogovtsev, S. and Mendes, J. 2001b. Language as an evolving word web. Proceedings of the Royal Society of London B 268, 2603.
• 18: 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.
• 19: S. N. Dorogovtsev , J. F. F. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW (Physics), Oxford University Press, Inc., New York, NY, 2003
• 20: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 21: Johannes Gehrke , Paul Ginsparg , Jon Kleinberg, Overview of the 2003 KDD Cup, ACM SIGKDD Explorations Newsletter, v.5 n.2, December 2003 [doi>10.1145/980972.980992]
• 22: 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.)
• 23: Huberman, B. A. and Adamic, L. A. 1999. Growth dynamics of the world-wide web. Nature 399, 131.
• 24: Katz, J. S. 1999. The self-similar science system. Resear. Policy 28, 501--517.
• 25: Katz, J. S. 2005. Scale independent bibliometric indicators. Measure.: Interdisciplin. Resea. Perspect. 3, 24--28.
• 26: Kleinberg, J. M. 2002. Small-world phenomena and the dynamics of information. In Advances in Neural Information Processing Systems 14.
• 27: 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.
• 28: Kossinets, G. and Watts, D. J. 2006. Empirical analysis of an evolving social network. Science 311, 88--90.
• 29: Krapivsky, P. L. and Redner, S. 2001. Organization of growing random networks. Phys. Rev. E 63, 066123.
• 30: Krapivsky, P. L. and Redner, S. 2005. Network growth by copying. Phys. Rev. E 71, 036118.
• 31: R. Kumar , P. Raghavan , S. Rajagopalan , D. Sivakumar , A. Tomkins , E. Upfal, Stochastic models for the Web graph, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.57, November 12-14, 2000
• 32: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Proceeding of the eighth international conference on World Wide Web, p.1481-1493, May 1999, Toronto, Canada
• 33: Jure Leskovec , Lada A. Adamic , Bernardo A. Huberman, The dynamics of viral marketing, Proceedings of the 7th ACM conference on Electronic commerce, p.228-237, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134732]
• 34: 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.
• 35: Jure Leskovec , Christos Faloutsos, Sampling from large graphs, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150479]
• 36: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 37: Menczer, F. 2002. Growing and navigating the small world web by local content. Proceedings of the National Academy of Sciences 99, 22, 14014--14019.
• 38: Milgram, S. 1967. The small-world problem. Psycholo. Today 2, 60--67.
• 39: Mitzenmacher, M. 2004. A brief history of generative models for power law and lognormal distributions. Internet Math. 1, 2, 226--251.
• 40: Newman, M. E. J. 2003. The structure and function of complex networks. SIAM Review 45, 167--256.
• 41: Newman, M. E. J. 2005. Power laws, pareto distributions and zipf's law. Contemp. Phys. 46, 323--351.
• 42: Alexandros Ntoulas , Junghoo Cho , Christopher Olston, What's new on the web?: the evolution of the web from a search engine perspective, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988674]
• 43: Oregon. 1997. University of Oregon route views project. online data and reports. http://www.routeviews.org.
• 44: Christopher R. Palmer , Phillip B. Gibbons , Christos Faloutsos, ANF: a fast and scalable tool for data mining in massive graphs, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775059]
• 45: Redner, S. 2004. Citation statistics from more than a century of physical review. Tech. rep. physics/0407137, arXiv.
• 46: Schroeder, M. 1991. Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise. W.H. Freeman and Company, New York, NY.
• 47: 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.
• 48: Vazquez, A. 2001. Disordered networks generated by recursive searches. Europhy. Lett. 54, 4, 430--435.
• 49: Vazquez, A. 2003. Growing networks with local rules: Preferential attachment, clustering hierarchy and degree correlations. Physical Review E 67, 056104.
• 50: Watts, D. J., Dodds, P. S., and Newman, M. E. J. 1998. Collective dynamics of ‘small-world’ networks. Nature 393, 440--442.
• 51: Watts, D. J., Dodds, P. S., and Newman, M. E. J. 2002. Identity and search in social networks. Science 296, 1302--1305.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Measurement, Theory

Keywords:
Densification power laws, graph generators, graph mining, heavy-tailed distributions, small-world phenomena