{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T17:08:05Z","timestamp":1774631285747,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,6,1]],"date-time":"2009-06-01T00:00:00Z","timestamp":1243814400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ITR-0324845PHY-0200909CCF-0524613CCR-0220070EIA-0218563ITR-0324845"],"award-info":[{"award-number":["ITR-0324845PHY-0200909CCF-0524613CCR-0220070EIA-0218563ITR-0324845"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0546900"],"award-info":[{"award-number":["CCF-0546900"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["ITR-0324845PHY-0200909CCF-0524613CCR-0220070EIA-0218563ITR-0324845"],"award-info":[{"award-number":["ITR-0324845PHY-0200909CCF-0524613CCR-0220070EIA-0218563ITR-0324845"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["210743"],"award-info":[{"award-number":["210743"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000166","name":"Division of Physics","doi-asserted-by":"publisher","award":["ITR-0324845PHY-0200909CCF-0524613CCR-0220070EIA-0218563ITR-0324845"],"award-info":[{"award-number":["ITR-0324845PHY-0200909CCF-0524613CCR-0220070EIA-0218563ITR-0324845"]}],"id":[{"id":"10.13039\/100000166","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:p>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<jats:italic>traceroute<\/jats:italic>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.<\/jats:p><jats: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 \u03b4-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.<\/jats:p>","DOI":"10.1145\/1538902.1538905","type":"journal-article","created":{"date-parts":[[2009,6,30]],"date-time":"2009-06-30T13:10:17Z","timestamp":1246367417000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":54,"title":["On the bias of traceroute sampling"],"prefix":"10.1145","volume":"56","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[{"name":"University of California, Santa Cruz, CA"}]},{"given":"Aaron","family":"Clauset","sequence":"additional","affiliation":[{"name":"University of New Mexico, Albuquerque, and the Santa Fe Institute, New Mexico"}]},{"given":"David","family":"Kempe","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, CA"}]},{"given":"Cristopher","family":"Moore","sequence":"additional","affiliation":[{"name":"University of New Mexico, Albuquerque, and the Santa Fe Institute, New Mexico"}]}],"member":"320","published-online":{"date-parts":[[2009,7,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2005.861250"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Amini L. Shaikh A. and Schulzrinne H. 2002. Issues with inferring Internet topological attributes. In SPIE IT-Com. Amini L. Shaikh A. and Schulzrinne H. 2002. Issues with inferring Internet topological attributes. In SPIE IT-Com.","DOI":"10.1117\/12.473379"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/505202.505204"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.066101"},{"key":"e_1_2_1_5_1","volume-title":"Random Graphs","author":"Bollob\u00e1s B.","unstructured":"Bollob\u00e1s , B. 2001. Random Graphs , 2 nd ed. Cambridge University Press , Cambridge . Bollob\u00e1s, B. 2001. Random Graphs, 2nd ed. Cambridge University Press, Cambridge.","edition":"2"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0401033"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 21st ACM SIGCOMM Conference. ACM","author":"Chen Q.","unstructured":"Chen , Q. , Chang , H. , Govindan , R. , Jamin , S. , Shenker , S. , and Willinger , W . 2002. The origin of power laws in Internet topologies revisited . In Proceedings of the 21st ACM SIGCOMM Conference. ACM , New York. Chen, Q., Chang, H., Govindan, R., Jamin, S., Shenker, S., and Willinger, W. 2002. The origin of power laws in Internet topologies revisited. In Proceedings of the 21st ACM SIGCOMM Conference. ACM, New York."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.94.018701"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the European Conference on Complex Systems (ECCS).","author":"Cohen R.","unstructured":"Cohen , R. , Gonen , M. , and Wool , A . 2007. Bounding the bias of tree-like sampling in ip topologies . In Proceedings of the European Conference on Complex Systems (ECCS). Cohen, R., Gonen, M., and Wool, A. 2007. Bounding the bias of tree-like sampling in ip topologies. In Proceedings of the European Conference on Complex Systems (ECCS)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2007-00326-9"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.12.009"},{"key":"e_1_2_1_12_1","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s P.","year":"1960","unstructured":"Erd\u0151s , P. , and R\u00e9nyi , A. 1960 . On the evolution of random graphs . Publ. Math. Inst. Hung. Acad. Sci. 5 , 17 -- 61 . Erd\u0151s, P., and R\u00e9nyi, A. 1960. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17--61.","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 29th International Colloguium on Automata, Languages and Programming. 110--122","author":"Fabrikant A.","unstructured":"Fabrikant , A. , Koutsoupias , E. , and Papadimitriou , C . 2002. Heuristically optimized trade-offs: A new paradigm for power laws in the internet . In Proceedings of the 29th International Colloguium on Automata, Languages and Programming. 110--122 . Fabrikant, A., Koutsoupias, E., and Papadimitriou, C. 2002. Heuristically optimized trade-offs: A new paradigm for power laws in the internet. In Proceedings of the 29th International Colloguium on Automata, Languages and Programming. 110--122."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316229"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 5th Workshop on Algorithms and Models for the Web-Graph (WAW2007)","author":"Flaxman A.","unstructured":"Flaxman , A. , and Vera , J . 2007. Bias reduction in traceroute sampling: Towards a more accurate map of the internet . In Proceedings of the 5th Workshop on Algorithms and Models for the Web-Graph (WAW2007) . Flaxman, A., and Vera, J. 2007. Bias reduction in traceroute sampling: Towards a more accurate map of the internet. In Proceedings of the 5th Workshop on Algorithms and Models for the Web-Graph (WAW2007)."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 19th ACM SIGCOMM Conference. ACM","author":"Govindan R.","unstructured":"Govindan , R. , and Tangmunarunkit , H . 2000. Heuristics for Internet map discovery . In Proceedings of the 19th ACM SIGCOMM Conference. ACM , New York. Govindan, R., and Tangmunarunkit, H. 2000. Heuristics for Internet map discovery. In Proceedings of the 19th ACM SIGCOMM Conference. ACM, New York."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2005.12.010"},{"key":"e_1_2_1_18_1","first-page":"13","article-title":"Probability inequalities for sums of bounded random variables","volume":"58","author":"Hoeffding W.","year":"1963","unstructured":"Hoeffding , W. 1963 . Probability inequalities for sums of bounded random variables . J. ASA 58 , 13 -- 30 . Hoeffding, W. 1963. Probability inequalities for sums of bounded random variables. J. ASA 58, 13--30.","journal-title":"J. ASA"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Kim J. H. 2006. Poisson cloning model for random graphs. Preprint. Kim J. H. 2006. Poisson cloning model for random graphs. Preprint.","DOI":"10.4171\/022-3\/43"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International Conference on Combinatorics and Computing.","author":"Kleinberg J.","unstructured":"Kleinberg , J. , Kumar , R. , Raghavan , P. , Rajagopalan , S. , and Tomkins , A . 1999. The web as a graph: Measurements, models and methods . In Proceedings of the International Conference on Combinatorics and Computing. Kleinberg, J., Kumar, R., Raghavan, P., Rajagopalan, S., and Tomkins, A. 1999. The web as a graph: Measurements, models and methods. In Proceedings of the International Conference on Combinatorics and Computing."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 22nd IEEE INFOCOM Conference. IEEE Computer Society Press, Los Alamitos.","author":"Lakhina A.","unstructured":"Lakhina , A. , Byers , J. , Crovella , M. , and Xie , P . 2003. Sampling biases in IP topology measurements . In Proceedings of the 22nd IEEE INFOCOM Conference. IEEE Computer Society Press, Los Alamitos. Lakhina, A., Byers, J., Crovella, M., and Xie, P. 2003. Sampling biases in IP topology measurements. In Proceedings of the 22nd IEEE INFOCOM Conference. IEEE Computer Society Press, Los Alamitos."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2006.10.008"},{"key":"e_1_2_1_23_1","volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","author":"McDiarmid C.","unstructured":"McDiarmid , C. 1998. Concentration . In Probabilistic Methods for Algorithmic Discrete Mathematics , M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, Eds. Springer-Verlag , Berlin, Germany , 195--247. McDiarmid, C. 1998. Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, Eds. Springer-Verlag, Berlin, Germany, 195--247."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 35th ACM Symposium on Theory of Computing. ACM","author":"Mihail M.","unstructured":"Mihail , M. , Papadimitriou , C. , and Saberi , A . 2003. On certain connectivity properties of the Internet topology . In Proceedings of the 35th ACM Symposium on Theory of Computing. ACM , New York. Mihail, M., Papadimitriou, C., and Saberi, A. 2003. On certain connectivity properties of the Internet topology. In Proceedings of the 35th ACM Symposium on Theory of Computing. ACM, New York."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/259573.259582"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003526"},{"key":"e_1_2_1_27_1","unstructured":"Motwani R. and Raghavan P. 1990. Randomized Algorithms. Cambridge University Press. Cambridge. Motwani R. and Raghavan P. 1990. Randomized Algorithms. Cambridge University Press. Cambridge."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/280549.280555"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2004-00021-5"},{"key":"e_1_2_1_30_1","volume-title":"Hypergeometric Functions and Their Applications","author":"Seaborn J.","unstructured":"Seaborn , J. 1991. Hypergeometric Functions and Their Applications . Springer-Verlag , Berlin, Germany . Seaborn, J. 1991. Hypergeometric Functions and Their Applications. Springer-Verlag, Berlin, Germany."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1096536.1096546"},{"key":"e_1_2_1_32_1","first-page":"351","article-title":"The exponential integral ei(x) and related functions. In An Atlas of Functions. Hemisphere","volume":"37","author":"Spanier J.","year":"1987","unstructured":"Spanier , J. , and Oldham , K. 1987 . The exponential integral ei(x) and related functions. In An Atlas of Functions. Hemisphere , Chapter 37 , 351 -- 360 . Spanier, J., and Oldham, K. 1987. The exponential integral ei(x) and related functions. In An Atlas of Functions. Hemisphere, Chapter 37, 351--360.","journal-title":"Chapter"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2003.822655"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 20th IEEE INFOCOM Conference. IEEE Computer Society Press, Los Alamitos.","author":"Tangmunarunkit H.","unstructured":"Tangmunarunkit , H. , Govindan , R. , Shenker , S. , and Estrin , D . 2001. The impact of policy on Internet paths . In Proceedings of the 20th IEEE INFOCOM Conference. IEEE Computer Society Press, Los Alamitos. Tangmunarunkit, H., Govindan, R., Shenker, S., and Estrin, D. 2001. The impact of policy on Internet paths. In Proceedings of the 20th IEEE INFOCOM Conference. IEEE Computer Society Press, Los Alamitos."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 6th Internet Measurement Conference (IMC'06)","author":"Viger F.","unstructured":"Viger , F. , Augustin , B. , Cuvellier , X. , Magnien , C. , Latapy , M. , Friedman , T. , and Teixeira , R . 2006. Detection, understanding, and prevention of traceroute measurement artifacts . In Proceedings of the 6th Internet Measurement Conference (IMC'06) . Viger, F., Augustin, B., Cuvellier, X., Magnien, C., Latapy, M., Friedman, T., and Teixeira, R. 2006. Detection, understanding, and prevention of traceroute measurement artifacts. In Proceedings of the 6th Internet Measurement Conference (IMC'06)."},{"key":"e_1_2_1_36_1","unstructured":"Wilf H. 1994. Generatingfunctionology. Academic Press Orlando FL. Wilf H. 1994. Generatingfunctionology. Academic Press Orlando FL."},{"key":"e_1_2_1_37_1","volume-title":"Vol. 276","author":"Wormald N.","unstructured":"Wormald , N. 1999. Models of random regular graphs . In London Math. Soc. Lecture Note Series, J. Lamb and D. Preece, Eds. Vol. 276 . Cambridge University Press , Cambridge . 239--298. Wormald, N. 1999. Models of random regular graphs. In London Math. Soc. Lecture Note Series, J. Lamb and D. Preece, Eds. Vol. 276. Cambridge University Press, Cambridge. 239--298."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1538902.1538905","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1538902.1538905","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:53Z","timestamp":1750278413000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1538902.1538905"}},"subtitle":["Or, power-law degree distributions in regular graphs"],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["10.1145\/1538902.1538905"],"URL":"https:\/\/doi.org\/10.1145\/1538902.1538905","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6]]},"assertion":[{"value":"2007-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}