Speaker: David Kempe, Univ. of Southern California Title: On the
Bias of Traceroute Sampling (or: Power-law Degree Distributions
in Regular Graphs) Abstract: Understanding the structure of the
Internet graph is a crucial step for building accurate network
models and designing efficient algorithms for Internet
applications. Yet, obtaining its graph structure is a
surprisingly difficult task, as edges cannot be explicitly
queried. Instead, empirical studies rely on traceroutes to build
what are essentially single-source, all-destinations, shortest-
path trees. These trees only sample a fraction of the network's
edges, and a recent paper by Lakhina et al. found empirically
that the resuting sample is intrinsically biased. For instance,
the observed degree distribution under traceroute sampling
exhibits a power law even when the underlying degree
distribution is Poisson. In this talk, we study the bias of
traceroute sampling systematically, and, for a very general
class of underlying degree distributions, calculat