Traceroute sampling is an important technique in exploring the internet router graph and the autonomous system graph. Although it is one of the primary techniques used in calculating statistics about the internet, it can introduce bias that corrupts these estimates. This paper reports on a theoretical and experimental investigation of a new technique to reduce the bias of traceroute sampling when estimating the degree distribution. We develop a new estimator for the degree of a node in a traceroute-sampled graph; validate the estimator theoretically in Erdos-Renyi graphs and, through computer experiments, for a wider range of graphs; and apply it to produce a new picture of the degree distribution of the autonomous system graph.
Internet mapping by traceroute sampling was pioneered by Pansiot and Grad in @cite_10 , and the scale-free nature of the degree distribution was observed by Faloutsos, Faloutsos, and Faloutsos in @cite_21 . Since 1998, the Cooperative Association for Internet Data Analysis (CAIDA) project has archived traceroute data that is collected daily @cite_17 . The bias introduced by traceroute sampling was identified in computer experiments by Lakhina, Byers, Crovella, and Xie in @cite_4 and Petermann and De Los Rios @cite_16 , and formally proven to hold in a model of one-monitor, all-target traceroute sample by Clauset and Moore @cite_2 and, in further generality, by Achlioptas, Clauset, Kempe, and Moore @cite_1 . Computer experiments by to Guillaume, Latapy, and Magoni @cite_14 and an analysis using the mean field approximation of statistical physics due to Dall'Asta, Alvarez-Hamelin, Barrat, V ' a zquez, and Vespignani @cite_11 argue that, despite the bias introduced by traceroute sampling, some sort of scale-free behavior can be inferred from the union of traceroute-sampled paths.
@cite_14 @cite_4 @cite_11 @cite_21 @cite_1 @cite_2 @cite_16 @cite_10 @cite_17
1519020025 1540064387 1693225151 2120511087
Department of Physics and Astronomy,University of New Mexico, Albuquerque NM 87131(aaron,moore)@cs.unm.edu(Dated: February 2, 2008)A great deal of eﬀort has been spent measuring topological features of the Internet. However, itwas recently argued that sampling based on taking paths or traceroutes through the network froma small number of sources introduces a fundamental bias in the observed degree distribution. Weexamine this bias analytically and experimentally. For Erd˝os-R´enyirandom graphs with mean degreec, we show analytically that traceroute sampling gives an observed degree distribution P(k) ∼ k Mapping the Internet generally consists in sampling the network from a limited set of sources by using "traceroute"-like probes. This methodology, akin to the merging of different spanning trees to a set of destinations, has been argued to introduce uncontrolled sampling biases that might produce statistical properties of the sampled graph which sharply differ from the original ones. Here we explore these biases and provide a statistical analysis of their origin. We derive a mean-field analytical approximation for the probability of edge and vertex detection that exploits the role of the number of sources and targets and allows us to relate the global topological properties of the underlying network with the statistical accuracy of the sampled graph. In particular we find that the edge and vertex detection probability is depending on the betweenness centrality of each element. This allows us to show that shortest path routed sampling provides a better characterization of underlying graphs with scale-free topology. We complement the analytical discussion with a throughout numerical investigation of simulated mapping strategies in different network models. We show that sampled graphs provide a fair qualitative characterization of the statistical properties of the original networks in a fair range of different strategies and exploration parameters. The numerical study also allows the identification of intervals of the exploration parameters that optimize the fraction of nodes and edges discovered in the sampled graph. This finding might hint the steps toward more efficient mapping strategies. Despite great effort spent measuring topological features of large networks like the Internet, it was recently argued that sampling based on taking paths through the network (e.g., traceroutes) introduces a fundamental bias in the observed degree distribution. We examine this bias analytically and experimentally. For classic random graphs with mean degree c, we show analytically that traceroute sampling gives an observed degree distribution P(k) 1 k for k < c, even though the underlying degree distribution is Poisson. For graphs whose degree distributions have power-law tails P(k) k^-alpha, the accuracy of traceroute sampling is highly sensitive to the population of low-degree vertices. In particular, when the graph has a large excess (i.e., many more edges than vertices), traceroute sampling can significantly misestimate alpha. 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 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 δ-regular and Poisson-distributed random graphs. Thus, our work puts the observations of on a rigorous footing, and extends them to nearly arbitrary degree distributions.