On Power-Law Relationships of the Internet Topology

Summary:

This paper introduces an interesting approach in characterizing the internet topologies by power-laws. The authors argue and demonstrate that simple averaging of parameters of interest does not correctly capture the underlying skewed distributions.

To this end they experimentally identify 3 power-laws (y prop x^a) and show that they hold over the three instances of Internet inter-domain topologies taken during 1998 and a single instance of intera-domain topology from year 1995. The lines predicted by the identified power-laws have above 96% coefficient correlation with actual data points. The identified power-laws are as following:

1. Power-Law 1 (rank exponent): The outdegree of a node is proportional to the rank of the node to a power of a constant R. The rank of a node will be determined by ordering the nodes in their decreasing outdegree order and finding the index. The constant R is called the "rank exponent" of the network topology and its value can be measure from the slop of the log-log plot of corresponding parameters. The rank exponent of three inter-domain instances are quite close (~-0.80) and different from the intra-domain instance (~-048) suggesting that it is a good metric in distinguishing the differences among network topologies.
   
2. Power-Law 2 (outdegree exponent): The frequency of an outdgree is proportional to the outdegree to the power of a constant O. This constant is called the outdegree exponent of the network topology. The value of O is quite close for all of the 4 instances (still slightly different for the intera-domain instance) suggesting that PL2 is a fundamental property of any such network. good for ckeckign the realisticness of a network
   
3. Power-Law 3 (eigen exponent): The eigenvalues of a graph are proportional to the order i, to the power of a constant E. i is the order of eigenvalues in a decreasing sequence fashion. E is called the eigen exponent of the network toplogy which again significantly differs in between the inter-domain instances (~-0.48) and intera-domain (-0.177) suggesting it is a good metric for distinguishing the differences among networks.

In addition to above three power-laws the authors identify another power-law but reserve to call it a law because of lack of sample points:

• Approximation 1 (hop-plot exponent): The total number of pairs of nodes, P(h), within h hops is proportional to the number of hops to the power of a constant H. The hop-plot exponent H can again be measured from the slop of the log-log plots when h is much less than the diameter of the network.
  

The hop-plot exponent is especially interesting since it gives better tools in estimating the number of average neighborhood size versus the traditional approach based on average node degree. The advantage comes from the fact that averaging assumes uniform outdegree while the hop-plot exponent based estimation better captures the underlying skewed distribution.

The identified power-laws can be used to verify the validity of a simulation model, improve the protocol analysis and interpolate/estimate the topological parameters of interest.

Critique:

The paper gives some insight into the underlying effect which causes the validity of identified power-laws which are quite interesting. It seems like after the first significant step the authors had taken in identifying these power-laws, a more detailed study of the underlying effects will be the next natural candidate.

This improved understanding of power-laws will also require to have access to many more sample points (even though it is a tedious process) and network instances. I'm very curious to know what have been the result of studying these power-laws over a richer set of network instances. I believe this is a great paper to be kept in the syllabus.