On power-law relationships of the internet topology

In this paper, the authors describe several power law relationships of quantities of interest in studying Internet topology, based on analysis of collected Internet data. If there are indeed such power laws, it would be useful in verifying or deciding between graph models used in simulations, in studying the theoretical performance of Internet protocols, or in modeling the evolution of the Internet. The power laws described in this paper are:

• Node out-degree and its rank (in order of decreasing out-degree)
• Out-degree frequency and out-degree
• Number of pairs of nodes within h hops and h
• Eigenvalue of connectivity graph and its order (in order of decreasing eigenvalue)

From these power laws, other relationships can also be elucidated, such as between edges and rank exponent and between average size of neighborhood within h hops and hop exponent.

It is interesting that such relationships exist, at least in the data that the authors examine. My biggest question would be how applicable are these laws over the years since this study was carried out. Related to this would be how time-invariant the exponents really are. My guess would be that the power laws would have exponents that are fairly constant over time, since they have to do with how hosts are connected to the internet through router, and the choices that are made are constrained by cost-effectiveness and hardware. Of course, if there was a major shift in technology or cost structure, this should also show up in the evolution of the exponents. The key point is that these laws should hold with just plain scaling.

I think that Section 5.1 would have been interesting to expand on. Namely, I would like to know if some of these power laws can be derived from first principles. As the authors pointed out, cost-effectiveness in designing networks can drive a common solution in network topology, hence leading to some of the power laws described in this paper.