On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs

Details On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs

2005-03-04

arxiv.org/abs/cond-mat/0503087v3

Proc. 37th ACM Symposium on Theory of Computing (STOC) 2005

Physics

Condensed Matter

Disordered Systems and Neural Networks

Long-format version (19 pages); includes small correction to section 6.1

Scientific paper

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 paper, 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 delta-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.

Affiliated with

Also associated with

No associations

Rating

On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-200692