Jure Leskovec
Lars Backstrom
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.
Supplemental Material
- R. Albert and A.-L. Barabasi. Emergence of scaling in random networks. Science, 286:509--512, 1999.Google Scholar
Cross Ref
- R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Reviews of Modern Physics, 74, 47, 2002.Google ScholarCross Ref
- L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan. Group formation in large social networks: Membership, growth, and evolution. In 12th KDD, pages 44--54, 2006. Google ScholarDigital Library
- I. Bezáková, A. Kalai, and R. Santhanam. Graph model selection using maximum likelihood. In 23rd ICML, pages 105--112, 2006. Google ScholarDigital Library
- A. Blum, H. Chan, and M. Rwebangira. A random-surfer web-graph model. In ANALCO, 2006.Google ScholarCross Ref
- 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.Google Scholar
- A. Broder, S. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. L. Wiener. Graph structure in the web. Computer Networks/WWW, 33(1-6):309--320, 2000. Google ScholarDigital Library
- S. Dorogovtsev and J. Mendes. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford Univ. Press, 2003. Google ScholarDigital Library
- P. Erdõs and A. Rényi. On the evolution of random graphs. Mathematical Institute of the Hungarian Academy of Science, 1960.Google Scholar
- M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. In SIGCOMM, pages 251--262, 1999. Google ScholarDigital Library
- D. Fetterly, M. Manasse, M. Najork, and J. Wiener. A large-scale study of the evolution of web pages. Software Practice and Experience, 34(2):213--237, 2004. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- R. Kumar, J. Novak, and A. Tomkins. Structure and evolution of online social networks. In 12th KDD, pages 611--617, 2006. Google ScholarDigital Library
- R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic models for the web graph. In 41st FOCS, pages 57--65, 2000. Google ScholarDigital Library
- J. Leskovec and C. Faloutsos. Scalable modeling of real graphs using Kronecker multiplication. In 24th ICML, pages 497--504, 2007. Google ScholarDigital Library
- J. Leskovec, J. M. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. ACM TKDD, 1(1):2, 2007. Google ScholarDigital Library
- D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In 12th CIKM, pages 556--559, 2003. Google ScholarDigital Library
- M. Newman. The structure and function of complex networks. SIAM Review, 45, 2:167--256, 2003.Google ScholarDigital Library
- A. Ntoulas, J. Cho, and C. Olston. What's new on the web? The evolution of the web from a search engine perspective. In 13th WWW, pages 1--12, 2004. Google ScholarDigital Library
- X. Shi, L. A. Adamic, and M. J. Strauss. Networks of strong ties. Physica A, 378(1):3347, 2007.Google ScholarCross Ref
- S. Strogatz. Exploring complex networks. Nature, 410, 2001.Google Scholar
- S. Wasserman and P. Pattison. Logit models and logistic regressions for social networks. Psychometrika, 60:401--425, 1996.Google ScholarCross Ref
- C. Wiuf, M. Brameier, O. Hagberg, and M. P. Stumpf. A likelihood approach to analysis of network data. PNAS, 103(20), 2006.Google Scholar
Index Terms
- Microscopic evolution of social networks
Recommendations
A Motif-Based Framework for Characterizing the Evolution of Social Networks
MINES '12: Proceedings of the 2012 Fourth International Conference on Multimedia Information Networking and SecuritySocial network computing has become popular in recent years. The study of evolving patterns of networks is facing a challenge: how to find the evolving features so as to extract significant evolving patterns. In this work, a novel framework based on ...
Quantifying triadic closure in multi-edge social networks
ASONAM '19: Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and MiningIn social networks, edges often form closed triangles or triads. Standard approaches to measuring triadic closure, however, fail for multi-edge networks, because they do not consider that triads can be formed by edges of different multiplicity. We ...
Search engine drives the evolution of social networks
ACM TURC '17: Proceedings of the ACM Turing 50th Celebration Conference - ChinaThe search engine is tightly coupled with social networks and is primarily designed for users to acquire interested information. Specifically, the search engine assists the information dissemination for social networks, i.e., enabling users to access ...
Comments