SIGKDD Awards

The SIGKDD Test of Time Award recognizes outstanding papers from past KDD Conferences beyond the last decade that have had an important impact on the data mining research community.

Jure Leskovec (Stanford)
Jon Kleinberg (Cornell University)
Christos Faloutsos (Carnegie Mellon University)

Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations, KDD 2005

Significance: The paper makes new discoveries about how real-world graphs and networks grow and evolve over time. These discoveries fundamentally shaped our understanding of the evolution and growth of real-world networks, and the paper spurred a rich line of research on measuring and modeling the structure and evolution of networks across many domains.

The paper studies a number of evolving real-world networks and identifies two laws of network growth: (1) the Densification Power Law, and (2) the Shrinking Diameter Principle. The Densification Power Law captures the fact that the number of edges in a network grows as a power of the number of nodes in the network (for example, double the number of nodes, triple the number of edges).  The Shrinking Diameter Principle captures the fact that the diameter of a network often shrinks as the number of nodes in the network grows. Both of these observations were fundamentally different from what was believed about the evolution of networks at the time they appeared: The conventional wisdom was that the average degree remains constant over time, and that the network diameter slowly grows with the number of nodes.

No existing model of network evolution at the time was able to capture the observed empirical patterns, and so the paper also proposes a set of models of network growth, including the so-called “Forest Fire” model that generates graphs exhibiting densification power laws, shrinking diameters, as well as other basic graph properties including strong clustering and skewed degree distributions.

Original 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 superlinearly 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.