title: 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 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.
authors.affiliation: Computer Science Department, University of New Mexico, Albuquerque, NM 87131, USA. aaron@cs.unm.edu
authors.forename: Aaron
authors.initials: A
authors.lastname: Clauset
authors.forename: Cristopher
authors.initials: C
authors.lastname: Moore