Graph evolution: Densification and shrinking diameters
By Jure Leskovec, Jon M. Kleinberg, Christos Faloutsos. 2006
2,913 citations recorded by the source corpus.
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.
Subfields: Sociology and Political Science, Statistical and Nonlinear Physics, Network Science & Complex Systems
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Sociology and Political Science
- Jure Leskovec
- Jon M. Kleinberg
- Charu C. Aggarwal
- Shibamouli Lahiri
- Remco van der Hofstad
- Jian Pei
- Peng Cui
- Wenwu Zhu
In Statistical and Nonlinear Physics
- Jure Leskovec
- William L. Hamilton
- Jon M. Kleinberg
- Charu C. Aggarwal
- Christos Faloutsos
- Michael W. Mahoney
- Remco van der Hofstad
- Linyuan Lu
In Network Science & Complex Systems
- Jure Leskovec
- Charu C. Aggarwal
- Shibamouli Lahiri
- Peng Cui
- Wenwu Zhu
- Christos Faloutsos
- Michael W. Mahoney
- Deepayan Chakrabarti
Citations in the corpus
- Position-aware Graph Neural Networks (2019, background): “7 real-world email communication graphs from SNAP (Leskovec et al., 2007) with no node features.”
- GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models (2018, background): “, Barabási-Albert model, Kronecker graphs, exponential random graphs, and stochastic block models) (Erdős & Rényi, 1959; Leskovec et al., 2010; Albert & Barabási, 2002; Airoldi et al., 2008; Leskovec et al., 2007; Robins et al., 2007) are hand-engineered to model a particular family of graphs, and t”
- Graph Embedding Techniques, Applications, and Performance: A Survey (2017, background): “Modeling the interactions between entities as graphs has enabled researchers to understand the various network systems in a systematic manner [4].”
- Combining Label Propagation and Simple Models Out-performs Graph Neural Networks (2020, methodology): “Finally, we use an email dataset of a European research institute, where classes are department membership and there are no features (Leskovec et al., 2007; Yin et al., 2017).”
- Identifying influential spreaders in complex networks based on gravity formula (2015, methodology): “work of University at Rovira i Virgili, URV) [28], TAP(yeast protein-protein binding network generated by tandem affinity purification experiments) [17], Y2H (yeast protein-protein binding network generated using yeast two hybridization) [29], Blogs (the communication relationships between owners of”
- A new space for comparing graphs (2014, methodology): “We used 3 public collaboration network datasets [18]: 1) High energy physics collaboration network3, 2) Condensed matter physics collaboration network4, 3) Astro physics collaboration network.”
- Listing All Maximal Cliques in Large Sparse Real-World Graphs (2011, positive): “03 email-EuAll [31] 265,214 364,481 37 265,214 * 4.”
- Asymptotic behavior and distributional limits of preferential attachment graphs (2014, background): “In order to demonstrate this, we also give a few applications of the 1Note, however, that we do not cover models exhibiting densification in the sense of Leskovec, Kleinberg and Faloutsos [19]; see [18] for a mathematical model exhibiting this phenomenon.”
- PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs (2012, neutral): “While there has been substantial work (see [27]) in more sophisticated natural graph models, the techniques in this paper focus only on the degree distribution and do not require any other modeling assumptions.”
- Scalable Inference of Overlapping Communities (2012, neutral): “[23] HEP-TH 9.”
- Random Dot Product Graph Models for Social Networks (2007, background): “5 explicit formulas for the degree sequence leading to a super-linear number of edges, which is consistent with recent results of Leskovec, Kleinberg and Faloutsos [14].”