Accuracy and Scaling Phenomena in Internet Mapping

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 Erdős-Rényi random graphs with mean degree $c$, we show analytically that such sampling gives an observed degree distribution $P(k)\sim k^{-1}$ for $k\lesssim c$, despite the underlying distribution being Poissonian. For graphs whose degree distributions have power-law tails $P(k)\sim 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.