[Colloq] Talk: Thursday, October 18, David Kempe, USC

[Rachel Kalweit]

College of Computer and Information Science Colloquium

Presents:
David Kempe 
University of Southern California

Who will speak on:
“On the Bias of Traceroute Sampling 
 (or: Power-law Degree Distributions in Regular Graphs)”

Thursday, Oct 18, 2007
4:00 p.m. - 5:00 p.m.,
366 West Village H
Northeastern University

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, calculate the likely observed distributions explicitly. To do this, we use a continuous-time realization of the process of exposing the BFS tree of a random graph with a given degree distribution, calculate the expected degree distribution of the tree, and show that it is sharply concentrated.  As example applications of our machinery, we show how traceroute sampling finds power-law degree distributions in both d-regular and Poisson-distributed random graphs.  Thus, our work puts the observations of Lakhina et al. on a rigorous footing, and extends them to nearly arbitrary degree distributions.
 
(Joint work with Dimitris Achlioptas, Aaron Clauset, and Cristopher Moore.)
 
Bio: 

David Kempe received his Ph.D. from Cornell University in 2003, and has been on the faculty in the computer science department at USC since the Fall of 2004. His primary research interests are in computer science theory and the design and analysis of algorithms, with a particular emphasis on social networks, distributed network algorithms, and game theoretic and pricing questions. He is a recipient of the NSF CAREER award, the VSoE Junior Research Award, and the Robert G. and Mary G. Lane Endowed Early Career Chair.

Host: Rajmohan Rajaraman