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 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.

Figure 1

Sampled degree distributions from breadth-first, depth-first, and random-first spanning trees on a random graph of size $n={10}^5$ and average degree $c=100$, and our analytic results (black dots). For comparison, the black line shows the Poisson degree distribution of the underlying graph. Note the power-law behavior of the apparent degree distribution $P(k)\sim k^{-1}$, which extends up to a cutoff at $k\sim c$.

Figure 2

Single-source traceroute sampling for preferential attachment networks with $n=5\times {10}^5$ and varying values of the minimum degree $m$. The extent to which traceroute sampling underestimates $\alpha$ increases with $m$.

Figure 3

Performance of multisource traceroute sampling in preferential attachment networks as a function of the number of sources divided by $m$. On the left, the convergence of ${\alpha }_{\mathrm{o}\mathrm{b}\mathrm{s}}$ to the correct value $\alpha =3$; on the right, the fraction of edges observed at least once. Both curves collapse, showing that the number of sources necessary to counter the sampling bias grows linearly with the average degree.