Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In the last decade, structural properties of several naturally arising networks (the Internet, social networks, the web graph, etc.) have been studied intensively with a view to understanding their evolution.

In recent empirical work, Leskovec, Kleinberg, and Faloutsos identify two new and surprising properties of the evolution of many real-world networks: densification (the ratio of edges to vertices grows over time), and shrinking diameter (the diameter reduces over time to a constant). These properties run counter to conventional wisdom, and are certainly inconsistent with graph models prior to their work.

In this paper, we present the first model that provides a simple, realistic, and mathematically tractable generative model that intrinsically explains all the well-known properties of the social networks, as well as densification and shrinking diameter.

Our model is based on ideas studied empirically in the social sciences, primarily on the groundbreaking work of Breiger (1973) on bipartite models of social networks that capture the affiliation of agents to societies.

We also present algorithms that harness the structural consequences of our model. Specifically, we show how to overcome the bottleneck of densification in computing shortest paths between vertices by producing sparse subgraphs that preserve or approximate shortest distances to all or a distinguished subset of vertices. This is a rare example of an algorithmic benefit derived from a realistic graph model.

Finally, our work also presents a modular approach to connecting random graph paradigms (preferential attachment, edge-copying, etc.) to structural consequences (heavy-tailed degree distributions, shrinking diameter, etc.).

REFERENCES

• 1: W. Aiello , F. Chung, Random Evolution in Massive Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.510, October 14-17, 2001
• 2: R. Albert and A.-L. Barabasi. "Emergence of scaling in random networks." Science, pages 509-512, 1999.
• 3: N.Alon, S. Hoory and N. Linial. "The moore bound for irregular graphs." in Graphs and Combinatorics 18 (2002), pages 53--57.
• 4: Ingo Althöfer , Gautam Das , David Dobkin , Deborah Joseph , José Soares, On sparse spanners of weighted graphs, Discrete & Computational Geometry, v.9 n.1, p.81-100, 1993 [doi>10.1007/BF02189308]
• 5: S.Baswana, S. Sen, "A simple linear time algorithm for computing sparse spanners in weighted graphs." in 30th International Colloquium on Automata, Languages and Programming(ICALP), pages 384--396, 2003.
• 6: Béla Bollobás , Oliver Riordan , Joel Spencer , Gábor Tusnády, The degree sequence of a scale-free random graph process, Random Structures & Algorithms, v.18 n.3, p.279-290, May 2001 [doi>10.1002/rsa.1009]
• 7: 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]
• 8: B. Bollobas, "The Diameter of Random Graphs." IEEE Trans. Inform.Theory 36 (1990), no. 2, 285--288.
• 9: R. L. Breiger "The Duality of Persons and Groups." Social Forces, University of North Carolina Press, 1974.
• 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: F. Chierichetti, S. Lattanzi and A. Panconesi, "Gossiping in Social Networks." to be submitted.
• 12: 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]
• 13: M. Dodds and Watts. "An experimental study of search in global social networks." Science, 301(5634):827--829, 2003.
• 14: D. Dubhashi, "Talagrand's inequality in hereditary settings." in Technical report, Dept. CS, Indian Istitute of Technology, 1998.
• 15: Alex Fabrikant , Elias Koutsoupias , Christos H. Papadimitriou, Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.110-122, July 08-13, 2002
• 16: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.251-262, Oct. 1999
• 17: J. Kleinberg. "Navigation in a small world." Nature, 06:845, 2000.
• 18: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 19: 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
• 20: Jure Leskovec , Lars Backstrom , Ravi Kumar , Andrew Tomkins, Microscopic evolution of social networks, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401948]
• 21: J. Leskovec, D. Chakrabarti, J.M. Kleinberg, C. Faloutsos, "Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication." PKDD 2005: 133--145.
• 22: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings 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]
• 23: M. Mahdian, Y. Xu, "Stochastic Kronecker Graphs." WAW 2007: 179--186.
• 24: B. Mandelbrot. "An informational theory of the statistical structure of languages." In W. Jackson, editor, Communication Theory, pages 486--502. Butterworth, 1953.
• 25: C.J.H. McDiarmid "On the method of bounded differences." In J. Siemons editor, Surveys in Combinatorics: Invited Papers at the 12th British Combinatorial Conference, number 141 in London Mathematical Society Lecture Notes Series, pages 148--188. Cambridge University Press, 1989.
• 26: M. Mitzenmacher. "A brief history of generative models for power law and lognormal distributions." Internet Mathematics, 1(2), 2003.
• 27: M. Mitzenmacher. "Editorial: The Future of Power Law Research." Internet Mathematics, vol. 2. no. 4, pp. 525--534, 2006.
• 28: D. L Nowell, J. Novak, R. Kumar, P. Raghavan, A. Tomkins "Geographic Routing in Social Networks." Proceedings of the National Academy of Sciences, Vol. 102, No. 33. (August 2005), pp. 11623--11628.
• 29: David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
• 30: H. Simon. "On a class of skew distribution functions." Biometrika, 42:425--440, 1955.
• 31: J. Travers and S. Milgram. "An experimental study of the small world problem." Sociometry, 32(4):425--443, 1969.
• 32: D. Watts and S. Strogatz. "Collective dynamics of small-world networks." Nature, 393(6684):409--410, 1998.
• 33: G. K. Zipf. "Human Behavior and the Principle of Least Effort." Addison-Wesley, 1949.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

General Terms:
Algorithms, Theory

Keywords:
densification, diameter, social networks, sparsification.