%0 Journal Article %1 Achlioptas:2009:BTS:1538902.1538905 %A Achlioptas, Dimitris %A Clauset, Aaron %A Kempe, David %A Moore, Cristopher %C New York, NY, USA %D 2009 %I ACM %J J. ACM %K bias sampling traceroute %N 4 %P 21:1--21:28 %R 10.1145/1538902.1538905 %T On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs %U http://doi.acm.org/10.1145/1538902.1538905 %V 56 %X Understanding the graph structure of the Internet is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining this graph structure can be a surprisingly difficult task, as edges cannot be explicitly queried. For instance, empirical studies of the network of Internet Protocol (IP) addresses typically rely on indirect methods like <i>traceroute</i> to build what are approximately single-source, all-destinations, shortest-path trees. These trees only sample a fraction of the network's edges, and a paper by Lakhina et al. 2003 found empirically that the resulting sample is intrinsically biased. Further, in simulations, they observed that the degree distribution under traceroute sampling exhibits a power law even when the underlying degree distribution is Poisson.</p> <p>In this article, we study the bias of traceroute sampling mathematically and, for a very general class of underlying degree distributions, explicitly calculate the distribution that will be observed. As example applications of our machinery, we prove that 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.

@article{Achlioptas:2009:BTS:1538902.1538905, abstract = {Understanding the graph structure of the Internet is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining this graph structure can be a surprisingly difficult task, as edges cannot be explicitly queried. For instance, empirical studies of the network of Internet Protocol (IP) addresses typically rely on indirect methods like <i>traceroute</i> to build what are approximately single-source, all-destinations, shortest-path trees. These trees only sample a fraction of the network's edges, and a paper by Lakhina et al. [2003] found empirically that the resulting sample is intrinsically biased. Further, in simulations, they observed that the degree distribution under traceroute sampling exhibits a power law even when the underlying degree distribution is Poisson.</p> <p>In this article, we study the bias of traceroute sampling mathematically and, for a very general class of underlying degree distributions, explicitly calculate the distribution that will be observed. As example applications of our machinery, we prove that 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.}, acmid = {1538905}, added-at = {2012-04-04T23:44:05.000+0200}, address = {New York, NY, USA}, articleno = {21}, author = {Achlioptas, Dimitris and Clauset, Aaron and Kempe, David and Moore, Cristopher}, biburl = {https://www.bibsonomy.org/bibtex/23f967f93e365bd65ab97395cb41d5b37/emrahcem}, description = {On the bias of traceroute sampling}, doi = {10.1145/1538902.1538905}, interhash = {1401ca5a7c97271eb4699e0730beb9d7}, intrahash = {3f967f93e365bd65ab97395cb41d5b37}, issn = {0004-5411}, issue_date = {June 2009}, journal = {J. ACM}, keywords = {bias sampling traceroute}, month = jul, number = 4, numpages = {28}, pages = {21:1--21:28}, publisher = {ACM}, timestamp = {2012-04-04T23:44:06.000+0200}, title = {On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs}, url = {http://doi.acm.org/10.1145/1538902.1538905}, volume = 56, year = 2009 }