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.