Accuracy and Scaling Phenomena in Internet Mapping

It is found that in order to accurately estimate alpha, one must use a number of sources which grows linearly in the mean degree of the underlying graph, and comment on the accuracy of the published values of alpha for the Internet.

Abstract

It was recently argued that sampling a network by traversing it with paths from a small number of sources, as with traceroutes on the Internet, creates a fundamental bias in observed topological features like the degree distribution. We examine this bias analytically and experimentally. For Erdo s-Re nyi random graphs with mean degree c, we show analytically that such sampling gives an observed degree distribution P(k) approximately k(-1) for k less, similarc, despite the underlying distribution being Poissonian. For graphs whose degree distributions have power-law tails P(k) approximately k(-alpha), sampling can significantly underestimate alpha when the graph has a large excess (i.e., many more edges than vertices). We find that in order to accurately estimate alpha, one must use a number of sources which grows linearly in the mean degree of the underlying graph. Finally, we comment on the accuracy of the published values of alpha for the Internet.