[Nrg-l] FW: [Colloq] Talk: Thursday, October 18, David Kempe, USC

Abraham Matta matta at cs.bu.edu
Thu Oct 11 16:45:50 EDT 2007

 This talk should be of interest...

-----Original Message-----
From: Rajmohan Rajaraman [mailto:rraj at ccs.neu.edu] 
Sent: Thursday, October 11, 2007 3:14 PM
To: John Byers; Abraham Matta; Shang-Hua Teng
Subject: Fwd: [Colloq] Talk: Thursday, October 18, David Kempe, USC

This talk may be of interest to you folks.   

Ibrahim/John -- could you also please forward the announcement to your
NRG list?  Thanks!


----- Forwarded Message -----
From: "Rachel Kalweit" <rachelb at ccs.neu.edu>
To: "colloq" <colloq at lists.ccs.neu.edu>
Sent: Thursday, October 11, 2007 2:52:42 PM (GMT-0500) America/New_York
Subject: [Colloq] Talk: Thursday, October 18, David Kempe, USC

College of Computer and Information Science Colloquium

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


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

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 

Colloq mailing list
Colloq at lists.ccs.neu.edu

More information about the Nrg-l mailing list