## DCI'00

**William Aiello**

*AT&T Lab - Research*

*Power Law Graphs*

Joint work with Fan Chung and Lincoln Lu.

There are now several real world examples of very massive graphs, for
example, the World Wide Web graph or the Internet Router Graph. These
graphs are too large and dynamic to answer even simple structural
questions exactly. Recently, however, an interesting property of these
graphs has come to light. The distribution of the degrees follows a
power law. That is, if y is the number of nodes of degree d, then y as
a function of d is proportional to 1/d^p for some constant power p > 0.
We describe how to model graphs with a power law degree distribution and
show how to answer some simple structural questions using the model.