Faculty Candidate Seminar

How Accurate are our Maps of the Internet? The Bias of Traceroute Sampling

Assoc. Prof. Cris Moore

Assoc. Prof. Cris Moore is from the University of New Mexico and the Santa Fe Institute
A great deal of effort has been spent measuring the topology of the Internet. However, it was recently argued by Lakhina et al. that sampling based on traceroutes from a small number of sources introduces a fundamental bias in the observed degree distribution. My Ph.D. student Aaron Clauset and I were able to prove this bias analytically: even if a graph is completely random, traceroute sampling gives the illusion of a power-law degree distribution. For graphs whose degree distributions really do have power-law tails P(k) ~ k^{-alpha}, traceroute sampling can significantly underestimate the value of the exponent alpha, unless we use a large number of sources. In joint work with Dimitris Achlioptas and David Kempe, we extended these results to more general graphs by answering the following mathematical question: if I have a random graph with a given degree distribution and I grow a breadth-first spanning tree on it, what is the likely degree distribution of that tree? I will discuss several analytic techniques we found useful, including differential equations for processes on random graphs.

Sponsored by

CSE Division