Random evolution in massive graphs

William Aiello, Fan Chung, and Linyuan Lu

Many massive graphs (such as WWW graphs and Call graphs) share certain
universal characteristics which can be described by the so-called the
"power law".  In this paper, we first briefly survey the history and
previous work on power law graphs.  Then we give  four evolution models
for generating power law graphs by adding one node/edge at a time. We show
that for any given edge density and desired distributions for in-degrees
and out-degrees (not necessarily the same, but adhered to certain general
conditions), the resulting graph almost surely satisfy the power law and
the in/out-degree conditions.  We show that our most general directed and
undirected  models include nearly  all known models as special cases.
In addition, we consider another crucial aspect of massive graphs that
is called "scale-free" in the sense that the frequency of sampling
(w.r.t. the growth rate) is independent of the parameter of the resulting
power law graphs.  We show that our evolution models  generate scale-free
power law graphs.

Keywords: Massive graphs, Power laws, Scale invariance, Random evolution.