The paper "Graph Evolution: Densification and Shrinking Diameters" by Jure Leskovec, Jon Kleinberg, and Christos Faloutsos explores the evolution of real graphs over time, focusing on two key phenomena: densification and shrinking diameters. The authors observe that most real graphs become denser over time, with the number of edges growing super-linearly in the number of nodes, and that the average distance between nodes often shrinks, contrary to the conventional wisdom that such distances should increase slowly. To explain these phenomena, the authors propose a new graph generator based on a "forest fire" spreading process. This model is simple and intuitive, requires few parameters, and produces graphs with the observed properties. The "forest fire" model exhibits a sharp transition between sparse and denser graphs, and graphs with decreasing diameters are generated around this transition point. The paper also analyzes the relationship between the temporal evolution of the degree distribution and graph densification. It finds that these two aspects are fundamentally related and that real networks exhibit this relationship. The authors conclude by discussing the implications of their findings for graph generation, sampling, extrapolations, and anomaly detection in network management.The paper "Graph Evolution: Densification and Shrinking Diameters" by Jure Leskovec, Jon Kleinberg, and Christos Faloutsos explores the evolution of real graphs over time, focusing on two key phenomena: densification and shrinking diameters. The authors observe that most real graphs become denser over time, with the number of edges growing super-linearly in the number of nodes, and that the average distance between nodes often shrinks, contrary to the conventional wisdom that such distances should increase slowly. To explain these phenomena, the authors propose a new graph generator based on a "forest fire" spreading process. This model is simple and intuitive, requires few parameters, and produces graphs with the observed properties. The "forest fire" model exhibits a sharp transition between sparse and denser graphs, and graphs with decreasing diameters are generated around this transition point. The paper also analyzes the relationship between the temporal evolution of the degree distribution and graph densification. It finds that these two aspects are fundamentally related and that real networks exhibit this relationship. The authors conclude by discussing the implications of their findings for graph generation, sampling, extrapolations, and anomaly detection in network management.