| Title | How Accurate are our Maps of the Internet? |
| Speaker | Prof. Cristopher Moore, University of New Mexico |
| Web page | http://www.santafe.edu/~moore/ |
| Time | Monday, October 18, 11:00am |
| Location | GFS 104 |
A great deal of effort has been spent measuring topological features of the Internet. However, it was recently argued that sampling based on taking traceroutes through the network from a small number of sources introduces a fundamental bias in the observed degree distribution. We examine this bias analytically and experimentally. For random graphs with mean degree c, we show analytically that traceroute sampling gives an observed degree distribution P(k) ∼ 1/k for k ≤ c, even though the underlying degree distribution is Poisson. For graphs whose degree distributions have power-law tails P(k) ∼ k^-α, traceroute sampling from a small number of sources can significantly underestimate the value of α. We find that in order to obtain a good estimate of α, it is necessary to use a number of sources which grows linearly in the average degree of the underlying graph. Based on these observations we comment on the accuracy of the published values of α for the Internet.