On Power-Law Relationships of the Internet Topology

Summary

This paper characterizes the structure of the Internet between Nov. 1997 and Dec. 1998. They authors find that power-laws fit the topology really well. The power-laws that they generate could be used to understand more characteristics of the network, such as average neighborhood size, and can be used to help design protocols.

During the time they studied, the internet by 45%. Unless this time was a transition phase for the Internet, the authors believe the power laws they came up with should continue to hold in the future.

Some characteristics of the Internet during the time of their study are:

• Nov. 1997: 3015 nodes, 5156 edges, 3.42 avg. outdegree
• April 1998: 3530 nodes, 6432 edges, 3.65 avg outdegree
• Dec. 1998: 4389 nodes, 8256 edges, 3.76 avg outdegree

They propose 3 power-laws:

• Power-Law 1 (rank exponent): The outdegree, dv, of a node v, is proportional to the rank of the node, rv, to the power of a constant, R.
• Power-Law 2 (outdegree exponent): The frequency, fd, of an outdegree, d, is proportional to the outdegree to the power of a constant, O
• Power-Law 3 (eigen exponent): The eigenvalues, lambda_i, of a graph are proportional to the order, i, to the power of a constant.

Finally, they suggest several practical applications of these power-laws, including assessment of realism of synthetic graphs, analyze worst-case behavior of protocols, and can help answer questions in different scenarios.

Criticisms & Questions

This was an interesting paper, especially since it was one of the first to characterize the topology of the Internet. Seeing as this was a decade ago, I am very curious to find out of these power-laws still hold. Since the way the internet is used has changed in the last 10 years, I would be really surprised if they were still true.

The authors mention several practical applications for the power-laws. I wonder if anyone has used these power-laws to inform any future research.