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; these include heavy tails for in and
outdegree distributions, communities, smallworld 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. We studied a wide range of real graphs,
and we observed 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)).
What underlying process causes a graph to systematically densify, and to
experience a decrease in effective diameter even as its size increases?
The existing graph generation models do not exhibit these types of
behavior, even at a qualitative level. In most cases they are also very
complicated to analyze mathematically.
So we propose a graph generator that is mathematically tractable and
matches this collection of properties. The main idea is to use a
nonstandard matrix operation, the Kronecker product, to generate graphs
that we refer to as "Kronecker graphs". We show that Kronecker graphs
naturally obey all the properties; in fact, we can rigorously prove that
they do so. We also provide empirical evidence showing that they can
mimic very well several real graphs.

Pradeep Ravikumar Last modified: Thu Oct 13 11:41:53 EDT 2005