Bias reduction in traceroute sampling - towards a more accurate map of the internet
A. Flaxman, and J. Vera. Proceedings of the 5th international conference on Algorithms and models for the web-graph, page 1--15. Berlin, Heidelberg, Springer-Verlag, (2007)
Abstract
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 Erdös-Rényi 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.
Description
Bias reduction in traceroute sampling - towards a more accurate map of the internet
%0 Conference Paper
%1 Flaxman:2007:BRT:1777879.1777880
%A Flaxman, Abraham D.
%A Vera, Juan
%B Proceedings of the 5th international conference on Algorithms and models for the web-graph
%C Berlin, Heidelberg
%D 2007
%I Springer-Verlag
%K bias reduction sampling traceroute
%P 1--15
%T Bias reduction in traceroute sampling - towards a more accurate map of the internet
%U http://dl.acm.org/citation.cfm?id=1777879.1777880
%X 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 Erdös-Rényi 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.
%@ 3-540-77003-8, 978-3-540-77003-9
@inproceedings{Flaxman:2007:BRT:1777879.1777880,
abstract = {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 Erdös-Rényi 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.},
acmid = {1777880},
added-at = {2012-04-04T23:46:28.000+0200},
address = {Berlin, Heidelberg},
author = {Flaxman, Abraham D. and Vera, Juan},
biburl = {https://www.bibsonomy.org/bibtex/2dec475eb0574c8dbb67827c9072ab12d/emrahcem},
booktitle = {Proceedings of the 5th international conference on Algorithms and models for the web-graph},
description = {Bias reduction in traceroute sampling - towards a more accurate map of the internet},
interhash = {9b38a24a4d4094ce1ad07a804932c129},
intrahash = {dec475eb0574c8dbb67827c9072ab12d},
isbn = {3-540-77003-8, 978-3-540-77003-9},
keywords = {bias reduction sampling traceroute},
location = {San Diego, CA, USA},
numpages = {15},
pages = {1--15},
publisher = {Springer-Verlag},
series = {WAW'07},
timestamp = {2012-04-04T23:46:28.000+0200},
title = {Bias reduction in traceroute sampling - towards a more accurate map of the internet},
url = {http://dl.acm.org/citation.cfm?id=1777879.1777880},
year = 2007
}