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 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.

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

References in corpus (3)

• Accuracy and Scaling Phenomena in Internet Mapping
• Traceroute sampling makes random graphs appear to have power law degree distributions
• Describing and Simulating Internet Routes

Cited by in corpus (13)

• Data-Driven Control of Complex Networks
• Compensating for population sampling in simulations of epidemic spread on temporal contact networks
• Epidemic risk from friendship network data: an equivalence with a non-uniform sampling of contact networks
• Benefits of Bias: Towards Better Characterization of Network Sampling
• Impact of spatially constrained sampling of temporal contact networks on the evaluation of the epidemic risk
• Sampling Content Distributed Over Graphs
• Near-optimal adjacency labeling scheme for power-law graphs
• Rules of Thumb for Information Acquisition from Large and Redundant Data
• Sampling Online Social Networks via Heterogeneous Statistics
• An $O(\log n)$-approximation for the Set Cover Problem with Set Ownership
• A Peep on the Interplays between Online Video Websites and Online Social Networks
• Impact of Random Failures and Attacks on Poisson and Power-Law Random Networks
• Potential Networks, Contagious Communities, and Understanding Social Network Structure