Accuracy and scaling phenomena in Internet mapping

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 Erdos-Renyi random graphs with mean degree c, we show analytically that such sampling gives an observed degree distribution P(k)similar tok(-1) for kless than or similar toc, despite the underlying distribution being Poissonian. For graphs whose degree distributions have power-law tails P(k)similar tok(-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.