On Power-Law Relationships of the Internet Topology

This paper was pretty interesting because it looked at mathematical properties seemingly obeyed by the Internet graph based on snapshots at different times. Several "laws" that produced good fits were identified. All were power laws, implying heavy-tailed distributions. Such distributions are very common in systems used by people (e.g. content popularity on the Internet) as well as natural systems. The laws identified involved distribution of ranks vs degrees, degree frequency vs degree, hop count vs number of nodes, and eigenvalues. I thought that the hop count one was particularly interesting because it is a measure of the "connectedness" of a graph. The degree found was about 2.8 for the router graph, implying that the Internet is "more connected" than a 2D grid but "less connected" than a 3D grid. This seems to be expected on a two-dimensional planet.

The main question with this paper is how to use this work. The most reasonable proposal is to validate Internet topology generators used in simulations. Still, the laws don't tell us how bad a graph that doesn't meet them is at approximating the Internet - in fact it might be a "harder" graph to route through / make reliable / whatever the algorithm is doing, in which case it's okay to test on it. The laws also might not be sufficient conditions for a realistic graph, so still the best way to do a simulation is with real topology data. Finally, the authors do use the power laws to try to predict Internet growth; I'm curious how well that works if extrapolated to today.

Another question is how many of these laws will arise naturally in a randomly generated graph [if generated according to some sensible model]. Certainly the hop-count one for example seems reasonable for planar graphs. The eigenvalue one also seems like something that could happen in random graphs no matter how we generated them, especially because it has little physical interpretation. The other laws may work in the same way. If this is the case, do the laws really imply something fundamental about the Internet?