Graphs over time: densification laws, shrinking diameters and possible explanations

By Jure Leskovec, Jon M. Kleinberg, Christos Faloutsos. 2005

2,772 citations recorded by the source corpus.

Subfields: Sociology and Political Science, Statistical and Nonlinear Physics, Graph Learning, 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

In Statistical and Nonlinear Physics

In Graph Learning

In Network Science & Complex Systems

Citations in the corpus

Averaging Gone Wrong: Using Time-Aware Analyses to Better Understand Behavior (2016, background): “This can be a natural response to limitations in the amount of available data: datasets may capture a small part of the community’s history [3]; timestamps may not be available [52,53]; snapshots may provide limited views of the community [11]; or the community itself may be small [39].”
Predict then Propagate: Graph Neural Networks meet Personalized PageRank (2018, background): “larger diameter (Leskovec et al., 2005), note that these graphs indeed have average shortest path lengths between 5 and 10 and therefore a regular two-layer GCN cannot cover the entire graph.”
Inferring networks of diffusion and influence (2010, methodology): “We consider two models of directed realworld networks, namely, the Forest Fire model [20] and the Kr onecker Graphs model [19] to generate G.”
Community detection in graphs (2009, background): “Recently, several data sets have become available, enabling to monitor the evolution in time of real systems (Kumar et al., 2003, 2006; Leskovec et al., 2008, 2005).”
Supervised random walks: predicting and recommending links in social networks (2010, background): “Large real-world networks exhibit a range of interesting properties and patterns [7, 20].”
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters (2008, methodology): “Graphs generated by this principle have both power-law degree distributions and they also obey the Densification Power Law [112, 113].”
Foundations and Modeling of Dynamic Networks Using Dynamic Graph Neural Networks: A Survey (2020, methodology): “Many models deﬁne rules for how links are established [41], [42].”
It's who you know: graph mining using recursive structural features (2011, background): “For example, at global scale, graph diameter has been observed to be small [2] and to shrink over time [20].”
Accountable internet protocol (aip) (2008, background): “[24], the AS-diameter of the Internet has been shrinking.”
Evolution of social-attribute networks: measurements, modeling, and implications using google+ (2012, background): “Measuring social-attribute networks can simultaneously inform us the properties of social network structure, attribute structure, and how such attributes impact social network structure.”
Information Contagion: An Empirical Study of the Spread of News on Digg and Twitter Social Networks (2010, neutral): “With time, we expect the Twitter network to grow denser (Leskovec, Kleinberg, and Faloutsos 2005) and become as tightly knit as Digg.”
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training (2020, background): “ow that several types of networks, e.g., World Wide Web, social, and biological networks, have the scale-free property, i.e., all of their degree distributions follow a power law [1]. Leskovec et al. [28] discover that a wide range of real graphs satisfy the densification and shrinking laws. Other c”
Diffusion Improves Graph Learning (2019, background): “Graphs become denser with size [39] and in practice we expect GDC to typically reduce the average degree at constant accuracy.”
On the Embeddability of Random Walk Distances (2013, methodology): “The next 7 graphs are from various networks, including a collaboration network graph from arXiv [24], an Internet autonomous systems (AS) graph from CAIDA [23], a citation graph from arXiv [23], a snapshot of the Gnutella peer-to-peer file sharing network [23], a measured Email network graph of a la”
Community Discovery in Dynamic Networks (2017, neutral): “…random graphs (R´enyi and Erdos, 1959), Watts and Strogatz small-world networks (Watts and Strogatz, 1998), Barab´asi and Al-bert Preferencial attachment model (Barab´asi and Al-bert, 1999), Leskovec’s Forest Fire (Leskovec et al. , 2005) or Community-Aﬃliation Graph (Yang and Leskovec, 2014).”