# Graph Evolution: Densification and Shrinking Diameters

**Authors:** Jure Leskovec, Jon Kleinberg, Christos Faloutsos  
**arXiv:** [physics/0603229](https://arxiv.org/abs/physics/0603229)  
**Date:** 2006-03-27  
**Summary page:** https://www.summarizepaper.com/en/paper/physics--0603229v3/

## Key points

- Study titled "Graph Evolution: Densification and Shrinking Diameters" by Jure Leskovec, Jon Kleinberg, and Christos Faloutsos
- Focus on growth patterns in social, technological, and information networks
- Most graphs densify over time as the number of edges increases super-linearly in relation to the number of nodes
- Introduction of a new graph generator based on a "forest fire" spreading process
- Graphs generated using this approach exhibit properties observed in prior studies
- Sharp transition in the "forest fire" model between sparse graphs and densifying ones

## Summary

In their study titled "Graph Evolution: Densification and Shrinking Diameters," authors Jure Leskovec, Jon Kleinberg, and Christos Faloutsos explore the evolution of real graphs over time. They focus on growth patterns in social, technological, and information networks to gain a better understanding of how these networks change over extended periods. Previous research has identified static graph properties such as heavy-tailed degree distributions and small-world phenomena. However, there is a lack of information on network evolution. Through an analysis of various real graphs, the authors make several intriguing observations. Firstly, they note that most graphs densify over time as the number of edges increases super-linearly in relation to the number of nodes. This finding challenges conventional wisdom as it suggests that average distances between nodes often decrease over time. This is contrary to expectations that such parameters should increase slowly with the number of nodes. Existing graph generation models do not adequately capture these evolving behaviors. To address this gap, the authors introduce a new graph generator based on a "forest fire" spreading process. This model offers a simple and intuitive explanation for network evolution by requiring minimal parameters like node flammability. Importantly, graphs generated using this approach exhibit a wide range of properties observed in prior studies and the current investigation. Furthermore, the authors highlight a sharp transition in the "forest fire" model between sparse graphs and densifying ones. They find that graphs with decreasing distances between nodes are generated around this transition point. Overall, this study sheds light on how real-world networks evolve over time and provides valuable insights into their changing structures and dynamics.