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

Jure LeskovecJon KleinbergChristos Faloutsos

article2005KDD2,784 citationsSIGKDD Test of Time Award

Demonstrates that real-world networks densify over time and exhibit shrinking effective diameters, overturning long-held assumptions about network growth while proposing the Forest Fire Model to explain these dynamic phenomena.

Listen

The article examines how large real-world networks such as citation graphs, patent records, internet autonomous systems, and author-paper affiliations change as they grow. Conventional models assumed that the average number of connections per node stays roughly constant and that distances between nodes grow slowly, yet these assumptions had rarely been checked against long sequences of network snapshots. The work set out to measure actual growth patterns across multiple domains and to develop simple generative models that reproduce the observed trends.

The authors analyzed nine datasets spanning up to several decades, constructing successive snapshots and tracking the number of nodes and edges at each step. They also computed the effective diameter, defined as the distance within which 90 percent of reachable node pairs lie. Two new probabilistic models were introduced and tested through analysis and simulation: one based on a nested community hierarchy that controls the cost of cross-group links, and a second based on a recursive “forest fire” process in which new nodes attach by burning through existing edges.

The measurements reveal that every network follows a densification power law in which the number of edges grows as a power of the number of nodes, with the exponent lying between 1.08 and 1.68; as a result, average node degree steadily increases. At the same time, effective diameters shrink rather than expand. The Community Guided Attachment model produces the observed densification exponents from a single tunable parameter, while the Forest Fire model reproduces both densification and shrinking diameters together with heavy-tailed degree distributions.

These patterns matter because many practical tasks rely on realistic network models. Graph generators used for simulation and “what-if” planning can now incorporate densification and shrinking distances. Sampling algorithms for very large graphs can be validated against the same laws, and deviations from expected growth can serve as signals for anomalies such as fraud or attacks. Forecasts of future network size and connectivity become better grounded.

The findings support continued development of the Forest Fire model, including variants that allow multiple starting points or isolated nodes, and broader testing on additional network types. Further theoretical analysis is needed to explain why diameters converge and to quantify the range of parameters that produce realistic behavior. The main limitations are the restriction to nine datasets from four domains and the reliance on simulation for the more complex model; results should be treated as robust within the studied settings but require additional confirmation elsewhere.

Carnegie Mellon University Cornell University bipartite graphs degree distributions Densification Power Law Shrinking Diameter Forest Fire Model

snap-stanford/snap Leskovec et al (2005).pdf

Paper: The link prediction problem for social networks, David Liben-Nowell et al. (2003). This paper establishes the topological link prediction framework in evolving co-authorship networks, providing foundational methodology for analyzing dynamic edge formation before the source's densification and shrinking diameter studies.
Paper: Maximizing the spread of influence through a social network, David Kempe et al. (2003). This work introduces algorithmic and submodular frameworks for cascading processes on networks, motivating the recursive and propagation-based dynamics used in the source paper's generative Forest Fire model.
Paper: Mining the network value of customers, Pedro M. Domingos et al. (2001). This study introduces early probabilistic models of network-based propagation and influence dynamics that informed the study of cascading mechanisms in real-world graphs.

Paper: Group formation in large social networks: membership, growth, and evolution, L. Backstrom et al. (2006). This paper extends the empirical study of temporal network evolution by analyzing individual joining behavior and community growth dynamics across large-scale social networks.
Paper: Cost-effective outbreak detection in networks, J. Leskovec et al. (2007). This work applies information cascade and epidemic spreading principles across dynamic network structures to optimize outbreak and cascade detection.
Paper: Temporal Networks, Petter Holme et al. (2011). This review generalizes the study of time-evolving graphs by formalizing temporal networks where edge activation times explicitly govern reachability and dynamical processes.
Paper: Defining and evaluating network communities based on ground-truth, Jaewon Yang et al. (2012). This research builds on empirical network structural properties and community modeling by evaluating topological community definitions against ground-truth datasets.
Paper: Hierarchical structure and the prediction of missing links in networks, Aaron Clauset et al. (2008). This paper advances hierarchical network models like the Community Guided Attachment introduced in the source to infer hierarchical organization and predict missing links.
Paper: Link Prediction in Complex Networks: A Survey, Linyuan Lu et al. (2010). This comprehensive survey categorizes link prediction models and evaluation metrics across evolving and complex network topologies.
Paper: Spatial Networks, Marc Barthelemy (2010). This synthesis evaluates how physical distance and spatial constraints restrict network growth, degree distributions, and topological diameter compared to abstract generative models.
Paper: The structure and dynamics of multilayer networks, S. Boccaletti et al. (2014). This paper broadens single-layer evolving network frameworks by synthesizing generative models and dynamical properties across multilayer and multiplex networks.

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

Abstract

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 super-linearly 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.

Topics

bipartite graphs degree distributions

Keywords

Densification Power Law Shrinking Diameter Forest Fire Model Community Guided Attachment Heavy‑tailed Degree Distribution Effective Diameter Preferential Attachment Autonomous System Citation Graph Affiliation Network

1. INTRODUCTION
2. RELATED WORK
3. OBSERVATIONS
3.1 Densification Laws
3.1.1 ArXiv citation graph
3.1.2 Patents citation graph
3.1.3 Autonomous systems graph
3.1.4 Affiliation graphs
3.2 Shrinking Diameters
3.2.1 Validating the shrinking diameter conclusion
4. PROPOSED MODELS
4.1 Community Guided Attachment
4.1.1 The Basic Version of the Model
4.1.2 Dynamic Community Guided Attachment
4.2 The Forest Fire Model
4.2.1 The Basic Forest Fire Model
4.2.2 Extensions to the Forest Fire Model
4.2.3 Phase plot
5. CONCLUSION
6. REFERENCES

Knowls

Knowl 1 — Densification Power Law for Evolving Graphs
equation
In many evolving real-world networks, the number of edges $e(t)$ at time $t$ grows super-linearly with respect to the number of nodes $n(t)$ at time $t$ according to a power-law relationship:

$e(t) \propto n(t)^a$

where $a$ is the densification exponent, typically satisfying $1 < a \le 2$ .

An exponent of $a = 1$ corresponds to a constant average degree over time (linear edge growth), while $a = 2$ corresponds to an extremely dense graph where every node connects, on average, to a constant fraction of all nodes. When $a > 1$ , the expected average out-degree $\bar{d}(t) = e(t)/n(t)$ increases polynomially with network size:

$\bar{d}(t) \propto n(t)^{a-1}$
Knowl 2 — Shrinking Effective Diameter in Growing Networks
empirical result
Contrary to the conventional assumption that graph diameter expands slowly (e.g., as $O(\log n)$ or $O(\log \log n)$ ) as the number of vertices $n$ grows, large real-world evolving networks frequently exhibit an effective diameter that decreases over time as new nodes and edges are added.

The effective diameter is defined via the smoothed cumulative distribution of shortest path distances: let $g(d)$ denote the fraction of connected node pairs in the undirected graph whose shortest-path distance is at most $d \in \mathbb{N}$ . Linearly interpolating between consecutive integer points $(d, g(d))$ and $(d+1, g(d+1))$ yields a continuous function over $\mathbb{R}^+$ . The effective diameter is the value of $d$ at which this interpolated function equals $0.90$ (representing the 90th percentile distance among connected pairs). In citation networks, this shrinkage is driven by later papers acting as bridges that cite earlier papers from previously disconnected domains.
Knowl 3 — Forest Fire Graph Generation Algorithm
algorithm
The Forest Fire model is a randomized generative model for evolving directed networks that reproduces densification power laws, shrinking effective diameters, communities, and heavy-tailed in- and out-degree distributions without requiring an explicit community hierarchy.

The model is parameterized by a forward burning probability $p \in [0, 1]$ and a backward burning ratio $r \in [0, 1]$ (or backward burning probability $p_b = r \cdot p$ ). The graph begins at time $t=1$ with a single node $G_1$ . When a new node $v$ joins the network at time $t > 1$ to form $G_t$ from $G_{t-1}$ :
Input: Existing graph $G_{t-1}$ , new node $v$ , forward probability $p$ , backward ratio $r$
Output: Graph $G_t$ with node $v$ and its newly formed out-links
$w \leftarrow$ uniformly random node chosen from $G_{t-1}$
Add directed edge $(v, w)$ to $G_t$
$\text{visited} \leftarrow \{w, v\}$
$\text{queue} \leftarrow [w]$
while $\text{queue}$ is not empty:
     $u \leftarrow \text{dequeue}(\text{queue})$
     $x \leftarrow$ random integer sampled from $\text{Binomial}$ with mean $(1 - p)^{-1}$
    Select up to $x$ unvisited neighbor links incident to $u$ , where in-links are selected with probability $r$ times less than out-links
    for each selected edge endpoint $w'$ :
        if $w' \notin \text{visited}$ :
            Add directed edge $(v, w')$ to $G_t$
             $\text{visited} \leftarrow \text{visited} \cup \{w'\}$
             $\text{queue} \leftarrow \text{enqueue}(\text{queue}, w')$
return $G_t$
By recursively spreading link formation along existing paths, the process occasionally triggers large cascades ("conflagrations"), generating high out-degree nodes that act as bridges across disparate regions and reduce the graph's effective diameter.
Knowl 4 — Community Guided Attachment Model
model/method
The Community Guided Attachment (CGA) model is a hierarchical generative model based on self-similarity that accounts for graph densification without centralized coordination.

Nodes are organized as the leaves of a balanced $b$ -ary tree $\Gamma$ of height $H$ , where the $n = b^H$ leaves represent the set of vertices $V$ of the graph. For any pair of leaf nodes $v, w \in V$ , their tree distance is defined by $h(v, w)$ , the height of their least common ancestor in $\Gamma$ .

The probability that an edge forms between $v$ and $w$ is determined by a scale-free difficulty function $f(h(v, w))$ :

$f(h) = c^{-h}$

where $c \ge 1$ is the difficulty constant parameterizing the resistance to forming cross-community links. Scale-invariance ensures that the relative difficulty ratio $f(h)/f(h-1) = c^{-1}$ is constant across all hierarchical levels.
Knowl 5 — Expected Degree and Densification Exponent in Static CGA
theoretical result
In the static Community Guided Attachment model with branching factor $b \ge 2$ , difficulty constant $c \ge 1$ , and $n$ leaf nodes, the expected average out-degree $\bar{d}$ of a node satisfies:

$\bar{d} = \begin{cases} \Theta\left(n^{1 - \log_b(c)}\right) & \text{if } 1 \le c < b \\ \Theta(\log_b n) & \text{if } c = b \\ \Theta(1) & \text{if } c > b \end{cases}$

When $1 < c < b$ , the total number of edges grows as $e(n) \propto n^a$ with a densification power law exponent:

$a = 2 - \log_b(c)$

As the difficulty constant $c$ varies continuously across the interval $[1, b)$ , the densification exponent $a$ spans the entire range $(1, 2]$ .
Knowl 6 — Phase Regimes and Degree Distributions in Dynamic CGA
theoretical result
The Dynamic Community Guided Attachment model extends CGA to a growing network. At each time step $t$ , the tree $\Gamma$ deepens by adding $b$ children to each current leaf, and graph nodes reside at both internal nodes and leaves. A newly arriving node $v$ connects independently to each existing node $w$ with probability $c^{-d(v,w)/2}$ , where $d(v,w)$ is the shortest tree path length between $v$ and $w$ in $\Gamma$ .

As the difficulty constant $c$ varies relative to the branching factor $b$ , the resulting graph displays three distinct structural regimes:
1. Densifying regime ( $c < b$ ): The average node degree is $\bar{d} = \Theta(n^{1 - \log_b c})$ , total edges obey $e(t) \propto n(t)^{2 - \log_b c}$ , and the in-degrees follow a Zipf distribution with exponent $\gamma = \frac{1}{2}\log_b c$ .
2. Constant degree with heavy tails ( $b < c < b^2$ ): The average node degree is constant ( $\bar{d} = \Theta(1)$ ), and the in-degrees follow a Zipf distribution with exponent $\gamma = 1 - \frac{1}{2}\log_b c$ .
3. Constant degree with light tails ( $c > b^2$ ): The average node degree is constant ( $\bar{d} = \Theta(1)$ ), and the probability of a node exceeding in-degree $k$ decays exponentially in $k$ .
The Zipf exponent is maximized at the onset of densification ( $c = b$ ).
Knowl 7 — Empirical Densification Exponents in Real-World Networks
empirical result
Across multiple real-world evolving networks from four distinct sources, the densification power law $e(t) \propto n(t)^a$ holds with consistently high goodness-of-fit and exponents $a > 1$ :
- arXiv HEP-TH Citation Graph ( $n = 29{,}555$ papers, $e = 352{,}807$ citations, Jan 1993 – Apr 2003): Densification exponent $a = 1.68$ ( $R^2 = 1.0$ ), with average out-degree growing over time from below 5 to ~15.
- arXiv HEP-PH Citation Graph: Densification exponent $a = 1.56$ .
- U.S. Patents Citation Graph ( $n = 3{,}923{,}922$ patents, $e = 16{,}522{,}438$ citations, 1975 – 1999): Densification exponent $a = 1.66$ ( $R^2 = 0.99$ ), with average patent out-degree growing from ~4 to ~10.
- Autonomous Systems BGP Graph (735 daily snapshots over 785 days, Nov 1997 – Jan 2000): Densification exponent $a = 1.18$ ( $R^2 = 1.00$ ), demonstrating super-linear edge growth despite active edge deletions and router disruptions.
- arXiv Affiliation Graphs (bipartite author-paper networks, Apr 1992 – Mar 2002): ASTRO-PH ( $n = 57{,}381$ , $e = 133{,}170$ ) yields $a = 1.15$ ( $R^2 = 1.0$ ); other categories (HEP-TH, HEP-PH, COND-MAT, GR-QC) exhibit exponents strictly between $1.08$ and $1.15$ .
Knowl 8 — Phase Space and Regimes of the Forest Fire Model
empirical result
By varying the forward burning probability $p$ and backward burning ratio $r$ (or $p_b = r \cdot p$ ), the Forest Fire model produces qualitatively different graph growth dynamics:
- Sparse graph with increasing diameter (e.g., $p = 0.35, p_b = 0.20$ ): Densification exponent $a = 1.01 \approx 1$ (near-linear edge growth) and effective diameter increasing logarithmically with $n$ .
- Densifying graph with decreasing diameter (e.g., $p = 0.37, p_b = 0.32$ ): Densification exponent $a = 1.21 < 2$ , heavy-tailed in- and out-degree distributions, and effective diameter decreasing from $\approx 6.5$ to $\approx 5.5$ .
- Dense graph with decreasing diameter (e.g., $p = 0.38, p_b = 0.35$ ): Densification exponent $a = 1.88 \approx 2$ (approaching quadratic edge growth) and effective diameter dropping rapidly from $\approx 7$ to under $3$ .
Fitting a logarithmic function $\text{diameter} = \alpha \log t + \beta$ to the second half of the network growth trace reveals that the parameter boundary where the diameter shrinks ( $\alpha < 0$ ) is shifted relative to the densification boundary ( $a > 1$ ). Consequently, the basic Forest Fire model can generate sparse graphs ( $a \approx 1$ ) that still exhibit shrinking effective diameters.
Knowl 9 — Forest Fire Model Extensions: Orphans and Multiple Ambassadors
model/method
Two natural extensions enhance the Forest Fire model to match domain-specific properties of real citation and communication graphs:
1. Orphans: Real citation networks contain isolated nodes (documents with zero citations to prior corpus entries). Orphans are introduced either by initializing the network with $n_0 > 1$ disconnected nodes at $t = 1$ , or by giving each newly arriving node a probability $q > 0$ of forming no out-links (forming no edge even to its ambassador). As subsequent nodes arrive and link across formerly separate orphan clusters, the decrease in effective diameter becomes more pronounced.
2. Multiple Ambassadors: Instead of attaching to a single entry point, a newly arriving node selects $k \ge 2$ initial ambassadors with positive probability and initiates recursive link-burning from each. Linking to multiple ambassadors bridges previously distant network regions, further accelerating the reduction of effective diameter over time.
Knowl 10 — Robustness Validation of the Shrinking Diameter Phenomenon
experimental setup
To verify that shrinking effective diameters are an intrinsic property of evolving networks rather than artifacts of data truncation or computation methods, four validation tests were performed:
1. Distance Estimation Accuracy: Effective diameters computed using the Approximate Neighborhood Function (ANF) and exhaustive breadth-first search on random vertex samples yielded nearly identical results.
2. Component Connectivity: Computing effective diameters on the entire graph versus only within the giant connected component produced equivalent shrinking trajectories.
3. Missing Past (Truncation Effects): To test whether unobserved pre-baseline citations artificially lower earlier diameters, comparisons were made across three graphs: the full graph, a post- $t_0$ subgraph retaining pre- $t_0$ links, and a post- $t_0$ subgraph with pre- $t_0$ links deleted ( $t_0 = 1995$ for arXiv; $t_0 = 1985$ for Patents). While curves deviate immediately at $t_0$ , they rapidly converge and consistently decline toward the present.
4. Giant Component Emergence: Unlike Erdős–Rényi graphs where diameter shrinks temporarily as isolated components coalesce into a giant component, real networks exhibit a continuous decrease in effective diameter long after the giant component has stabilized to contain over 90% of all nodes.

Coverage note — None. The 10 knowls fully cover the paper's core contributions, including the empirical discovery of densification and shrinking diameter, validation checks, static/dynamic CGA models with their analytical theorems, the Forest Fire model, its algorithm, phase space, and extensions.

References

1.J. Abello, A. L. Buchsbaum, and J. Westbrook. A functional approach to external graph algorithms. In Proceedings of the 6th Annual European Symposium on Algorithms, pages 332–343. Springer-Verlag, 1998.
2.J. Abello, P. M. Pardalos, and M. G. C. Resende. Handbook of massive data sets. Kluwer, 2002.
3.R. Albert and A.-L. Barabasi. Emergence of scaling in random networks. Science, pages 509–512, 1999.
4.R. Albert, H. Jeong, and A.-L. Barabasi. Diameter of the world-wide web. Nature, 401:130–131, September 1999.
5.Z. Bi, C. Faloutsos, and F. Korn. The dgx distribution for mining massive, skewed data. In KDD, pages 17–26, 2001.
6.B. Bollobas and O. Riordan. The diameter of a scale-free random graph. Combinatorica, 24(1):5–34, 2004.
7.A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the web: experiments and models. In Proceedings of World Wide Web Conference, 2000.
8.D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-mat: A recursive model for graph mining. In SDM, 2004.
9.F. Chung and L. Lu. The average distances in random graphs with given expected degrees. Proceedings of the National Academy of Sciences, 99(25):15879–15882, 2002.
10.C. Cooper and A. Frieze. A general model of web graphs. Random Struct. Algorithms, 22(3):311–335, 2003.
11.M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. In SIGCOMM, pages 251–262, 1999.
12.J. Gehrke, P. Ginsparg, and J. M. Kleinberg. Overview of the 2003 kdd cup. SIGKDD Explorations, 5(2):149–151, 2003.
13.B. H. Hall, A. B. Jaffe, and M. Trajtenberg. The nber patent citation data file: Lessons, insights and methodological tools. NBER Working Papers 8498, National Bureau of Economic Research, Inc, Oct. 2001.
14.B. A. Huberman and L. A. Adamic. Growth dynamics of the world-wide web. Nature, 399:131, 1999.
15.J. S. Katz. The self-similar science system. Research Policy, 28:501–517, 1999.
16.J. S. Katz. Scale independent bibliometric indicators. Measurement: Interdisciplinary Research and Perspectives, 3:24–28, 2005.
17.J. M. Kleinberg. Small-world phenomena and the dynamics of information. In Advances in Neural Information Processing Systems 14, 2002.
18.J. M. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. The web as a graph: Measurements, models, and methods. In Proc. International Conference on Combinatorics and Computing, pages 1–17, 1999.
19.R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic models for the web graph. In Proc. 41st IEEE Symp. on Foundations of Computer Science, 2000.
20.R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Trawling the web for emerging cyber-communities. In Proceedings of 8th International World Wide Web Conference, 1999.
21.F. Menczer. Growing and navigating the small world web by local content. Proceedings of the National Academy of Sciences, 99(22):14014–14019, 2002.
22.S. Milgram. The small-world problem. Psychology Today, 2:60–67, 1967.
23.M. Mitzenmacher. A brief history of generative models for power law and lognormal distributions, 2004.
24.M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167–256, 2003.
25.A. Ntoulas, J. Cho, and C. Olston. What’s new on the web? the evolution of the web from a search engine perspective. In WWW Conference, pages 1–12, New York, New York, May 2004.
26.U. of Oregon Route Views Project. Online data and reports. http://www.routeviews.org.
27.C. R. Palmer, P. B. Gibbons, and C. Faloutsos. Anf: A fast and scalable tool for data mining in massive graphs. In SIGKDD, Edmonton, AB, Canada, 2002.
28.S. Redner. Citation statistics from more than a century of physical review. Technical Report physics/0407137, arXiv, 2004.
29.M. Schroeder. Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise. W.H. Freeman and Company, New York, 1991.
30.D. J. Watts, P. S. Dodds, and M. E. J. Newman. Collective dynamics of ’small-world’ networks. Nature, 393:440–442, 1998.
31.D. J. Watts, P. S. Dodds, and M. E. J. Newman. Identity and search in social networks. Science, 296:1302–1305, 2002.

Citation

MLA

Leskovec, J., et al. “Graphs over Time”. Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, 2005, pp. 177–87, https://doi.org/10.1145/1081870.1081893.

APA

Leskovec, J., Kleinberg, J., & Faloutsos, C. (2005). Graphs over time. Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, 177–187. https://doi.org/10.1145/1081870.1081893

Chicago

Leskovec, J., J. Kleinberg, and C. Faloutsos. 2005. “Graphs over Time”. Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, 177–87. https://doi.org/10.1145/1081870.1081893.

Harvard

Leskovec, J., Kleinberg, J. and Faloutsos, C. (2005) “Graphs over time”, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. ACM, pp. 177–187. Available at: https://doi.org/10.1145/1081870.1081893.

Vancouver

1. Leskovec J, Kleinberg J, Faloutsos C (2005) Graphs over time. In: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. ACM, pp 177–187

BibTeX

@inproceedings{Leskovec_2005, series={KDD05}, title={Graphs over time: densification laws, shrinking diameters and possible explanations}, url={http://dx.doi.org/10.1145/1081870.1081893}, DOI={10.1145/1081870.1081893}, booktitle={Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining}, publisher={ACM}, author={Leskovec, Jure and Kleinberg, Jon and Faloutsos, Christos}, year={2005}, month=Aug, pages={177–187}, collection={KDD05} }

Metadata:Crossref

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

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

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Densification Power Law for Evolving Graphs

Knowl 2 — Shrinking Effective Diameter in Growing Networks

Knowl 3 — Forest Fire Graph Generation Algorithm

Knowl 4 — Community Guided Attachment Model

Knowl 5 — Expected Degree and Densification Exponent in Static CGA

Knowl 6 — Phase Regimes and Degree Distributions in Dynamic CGA

Knowl 7 — Empirical Densification Exponents in Real-World Networks

Knowl 8 — Phase Space and Regimes of the Forest Fire Model

Knowl 9 — Forest Fire Model Extensions: Orphans and Multiple Ambassadors

Knowl 10 — Robustness Validation of the Shrinking Diameter Phenomenon

References

Citation

BibTeX

Source Code

Access the Paper