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)∼k−1 for k≲c, despite the underlying distribution being Poissonian. For graphs whose degree distributions have power-law tails P(k)∼k−α, sampling can significantly underestimate α when the graph has a large excess (i.e., many more edges than vertices). We find that in order to accurately estimate α, 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 α for the Internet.

This publication has 8 references indexed in Scilit: