Bias Reduction in Traceroute Sampling – Towards a More Accurate Map of the Internet
From MaRDI portal
Publication:5458296
DOI10.1007/978-3-540-77004-6_1zbMATH Open1136.68325arXiv0705.3243OpenAlexW3106411499MaRDI QIDQ5458296FDOQ5458296
Authors: Abraham D. Flaxman, Juan Vera 
Publication date: 11 April 2008
Published in: Algorithms and Models for the Web-Graph (Search for Journal in Brave)
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 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.
Full work available at URL: https://arxiv.org/abs/0705.3243
Recommendations
Random graphs (graph-theoretic aspects) (05C80) Network design and communication in computer systems (68M10)
Cited In (7)
- A Fast Algorithm to Find All High-Degree Vertices in Graphs with a Power-Law Degree Sequence
- Detection, understanding, and prevention of traceroute measurement artifacts
- Relevance of massively distributed explorations of the internet topology: qualitative results
- On the bias of traceroute sampling
- On the bias of traceroute sampling
- Bounding the bias of tree-like sampling in IP topologies
- Exploring networks with traceroute-like probes: Theory and simulations
This page was built for publication: Bias Reduction in Traceroute Sampling – Towards a More Accurate Map of the Internet
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458296)
