Microscopic evolution of social networks

ABSTRACT

We present a detailed study of network evolution by analyzing four large online social networks with full temporal information about node and edge arrivals. For the first time at such a large scale, we study individual node arrival and edge creation processes that collectively lead to macroscopic properties of networks. Using a methodology based on the maximum-likelihood principle, we investigate a wide variety of network formation strategies, and show that edge locality plays a critical role in evolution of networks. Our findings supplement earlier network models based on the inherently non-local preferential attachment.

Based on our observations, we develop a complete model of network evolution, where nodes arrive at a prespecified rate and select their lifetimes. Each node then independently initiates edges according to a "gap" process, selecting a destination for each edge according to a simple triangle-closing model free of any parameters. We show analytically that the combination of the gap distribution with the node lifetime leads to a power law out-degree distribution that accurately reflects the true network in all four cases. Finally, we give model parameter settings that allow automatic evolution and generation of realistic synthetic networks of arbitrary scale.

REFERENCES

• 1: R. Albert and A.-L. Barabasi. Emergence of scaling in random networks. Science, 286:509--512, 1999.
• 2: R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Reviews of Modern Physics, 74, 47, 2002.
• 3: Lars Backstrom , Dan Huttenlocher , Jon Kleinberg , Xiangyang Lan, Group formation in large social networks: membership, growth, and evolution, 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.1150412]
• 4: Ivona Bezáková , Adam Kalai , Rahul Santhanam, Graph model selection using maximum likelihood, Proceedings of the 23rd international conference on Machine learning, p.105-112, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143858]
• 5: A. Blum, H. Chan, and M. Rwebangira. A random-surfer web-graph model. In ANALCO, 2006.
• 6: B. Bollobas and O. Riordan. Mathematical results on scale-free random graphs. In S. Bornholdt and H. Schuster, editors, Handbook of Graphs and Networks, pages 1--37. Wiley-WCH, 2002.
• 7: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.309-320, June 2000
• 8: 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
• 9: P. Erdõs and A. Rényi. On the evolution of random graphs. Mathematical Institute of the Hungarian Academy of Science, 1960.
• 10: 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
• 11: Dennis Fetterly , Mark Manasse , Marc Najork , Janet L. Wiener, A large-scale study of the evolution of web pages, Software—Practice & Experience, v.34 n.2, p.213-237, February 2004 [doi>10.1002/spe.577]
• 12: D. Krackhardt and M. Handcock. Heider vs. Simmel: Emergent features in dynamic structure. In Statistical Network Analysis: Models, Issues, and New Directions, pages 14--27, 2007.
• 13: Ravi Kumar , Jasmine Novak , Andrew Tomkins, Structure and evolution of online social networks, 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.1150476]
• 14: 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
• 15: Jure Leskovec , Christos Faloutsos, Scalable modeling of real graphs using Kronecker multiplication, Proceedings of the 24th international conference on Machine learning, p.497-504, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273559]
• 16: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graph evolution: Densification and shrinking diameters, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.2-es, March 2007 [doi>10.1145/1217299.1217301]
• 17: David Liben-Nowell , Jon Kleinberg, The link prediction problem for social networks, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956972]
• 18: M. Newman. The structure and function of complex networks. SIAM Review, 45, 2:167--256, 2003.
• 19: 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]
• 20: X. Shi, L. A. Adamic, and M. J. Strauss. Networks of strong ties. Physica A, 378(1):3347, 2007.
• 21: S. Strogatz. Exploring complex networks. Nature, 410, 2001.
• 22: S. Wasserman and P. Pattison. Logit models and logistic regressions for social networks. Psychometrika, 60:401--425, 1996.
• 23: C. Wiuf, M. Brameier, O. Hagberg, and M. P. Stumpf. A likelihood approach to analysis of network data. PNAS, 103(20), 2006.

INDEX TERMS

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

General Terms:
Experimentation, Measurement

Keywords:
graph generators, maximum likelihood, network evolution, social networks, transitivity, triadic closure