M. Faloutsos, P. Faloutsos, C. Faloutsos, “On Power-Law Relationships of the Internet Topology,” ACM SIGCOMM Conference, (September 1999). [PDF]

Summary

This paper explores the underlying regularities of the Internet structure and uses power laws to capture the properties of the AS-graph. The results presented in this paper are based on three AS-level as-complete-as-possible traces of the Internet over a 14 months period from Nov’97 to Dec’98. Within this 14 months, the Internet had a 45% growth. To include the intra-domain characteristics, the authors also used a node-level trace of the whole Internet circa ’95.

The authors observed that the then-existing metrics to capture the characteristics of the Internet were mostly minimum, maximum or average values, which failed to capture the inherent skewness of Internet-related distributions. Based on this observation, they tried and managed to fit the collected trace data to power-law curves with very high accuracy.

This paper proposes three power laws and one approximation (due to lack of data points, they couldn’t strongly suggest it to be a law!), and define four exponents/power-law curves:

1. Rank exponent, R: The out-degree of a node is proportional to its rank to the power of a constant R. From the traces, the authors found that the rank exponent R significantly varies between different types of graphs (e.g., AS-level and node-level) to be able identify them.
2. Out-degree exponent, O: The frequency of an out-degree is proportional to the out-degree to the power of a constant O. This law suggests that there is an underlying out-degree distribution of Internet-like graphs, and the authors propose the use of this metric to rule out synthetic graphs that does not have similar out-degree exponents.
3. Hop-plot exponent, H: The total number of pairs of nodes within a certain number of hops of a node is proportional to the number of hops to the power of H. It can also be used to separate between different types of graphs.
4. Eigen exponent: The eigenvalues of a graph are proportional to the corresponding order to the power of a constant E. The authors found that this exponent remained sort of constant over time to suggest that it is size-invariant; but they found that it can also be used to identify different classes of graphs.

Because the power laws show consistent correlation among traces, they authors propose them to be used to assess the realism of synthetic graphs, to help analyze the average-case behavior of network protocols, and to concisely define Internet-like graphs. The paper also provides several formulas to calculate the number of edges, nodes, density of nodes of such graphs.

Thoughts

The authors have done an excellent job to draw conclusions from a vast amount of data to provide structure to the Internet graph. It was really interesting to see that there is order somewhere under the seemingly chaotic world of computer networks and their interconnections. In fact, as the authors point out, power-laws can be observed in many other types of social, scientific, and biological networks. I wonder why?