On Power-Law Relationships of the Internet Topology

This paper describes Internet topology and growth using power laws. The authors find that a surprising number of Internet attributes grow as a power function. They study traces of the Internet over a year in 1998.

The key findings are:

1. The out degree of a node is proportional to the rank of that node to the power of a constant. This means that the out degrees of nodes on the internet follow a "power law" distribution
2. The frequency of an out degree is proportional to the out degree of the power of a constant. The authors find the constant to be negative implying that there are a small number of nodes with a large out degree and a larger number of nodes with a small out degree.
3. The total number of nodes within h hops is proportional to the number of hops to the power of a constant. In other words the number of reachable nodes grows as a power function of the number of hops.
4. The eigenvalues of a graph are proportional to the order to the power of a constant.

Overall the authors explain these surprisingly regular relationships by stating that changes propagate up through the network. In other words adding nodes at the bottom forces additional connectivity at the top.

The authors suggest several applications of this work including tuning protocol performance and extrapolating Internet growth.

It would be interesting to see how well these laws extrapolate; are they still applicable today?