Jure Leskovec, Jon Kleinberg, and Christos Faloutsos analyze the evolution of real graphs over time, focusing on densification and shrinking diameters. They find that most real graphs densify, with the number of edges growing super-linearly in the number of nodes, and that the average distance between nodes often shrinks over time. Existing graph generation models do not exhibit these behaviors, so they propose a new model based on a "forest fire" spreading process that produces graphs with these properties. They also find that the densification of graphs is fundamentally related to the temporal evolution of the degree distribution. The paper presents empirical findings on several real-world networks, showing that densification and shrinking diameters are common across diverse domains. They propose two probabilistic generative models for graphs that capture these properties, including the Forest Fire model, which exhibits both densification and shrinking diameters. The paper also discusses the implications of these findings for graph generation, sampling, extrapolation, and abnormality detection. The results show that real-world networks exhibit these properties, and the proposed models provide a framework for understanding and generating graphs with these characteristics.Jure Leskovec, Jon Kleinberg, and Christos Faloutsos analyze the evolution of real graphs over time, focusing on densification and shrinking diameters. They find that most real graphs densify, with the number of edges growing super-linearly in the number of nodes, and that the average distance between nodes often shrinks over time. Existing graph generation models do not exhibit these behaviors, so they propose a new model based on a "forest fire" spreading process that produces graphs with these properties. They also find that the densification of graphs is fundamentally related to the temporal evolution of the degree distribution. The paper presents empirical findings on several real-world networks, showing that densification and shrinking diameters are common across diverse domains. They propose two probabilistic generative models for graphs that capture these properties, including the Forest Fire model, which exhibits both densification and shrinking diameters. The paper also discusses the implications of these findings for graph generation, sampling, extrapolation, and abnormality detection. The results show that real-world networks exhibit these properties, and the proposed models provide a framework for understanding and generating graphs with these characteristics.