Accuracy and Scaling Phenomena in Internet Mapping
arXiv:cond-mat/0410059 · doi:10.1103/PhysRevLett.94.018701
Abstract
A great deal of effort has been spent measuring topological features of the Internet. However, it was recently argued that sampling based on taking paths or traceroutes through the network from a small number of sources introduces a fundamental bias in the observed degree distribution. We examine this bias analytically and experimentally. For Erdos-Renyi 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, traceroute sampling from a small number of sources can significantly underestimate the value of αwhen the graph has a large excess (i.e., many more edges than vertices). We find that in order to obtain a good estimate of alpha it is necessary to use a number of sources which grows linearly in the average degree of the underlying graph. Based on these observations we comment on the accuracy of the published values of alpha for the Internet.
arXiv comment4 pages, 3 figures; supercedes cond-mat/0407339 and contains scaling results on the accuracy of multi-source traceroute studies
References in corpus (3)
Cited by in corpus (35)
- Hierarchical structure and the prediction of missing links in networks
- What's in a crowd? Analysis of face-to-face behavioral networks
- New Model of Internet Topology Using k-shell Decomposition
- MEDUSA - New Model of Internet Topology Using k-shell Decomposition
- Statistical properties of sampled networks
- Network structure from rich but noisy data
- Identifying the starting point of a spreading process in complex networks
- Exploring networks with traceroute-like probes: theory and simulations
- Estimating network structure from unreliable measurements
- Statistical properties of sampled networks by random walks
- The structural role of weak and strong links in a financial market network
- Graph Annotations in Modeling Complex Network Topologies
- A critical look at power law modelling of the Internet
- Reliability of rank order in sampled networks
- A statistical approach to the traceroute-like exploration of networks: theory and simulations
- On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs
- Network Inference from TraceRoute Measurements: Internet Topology `Species'
- Spreading paths in partially observed social networks
- On the Tomography of Networks and Multicast Trees
- Using bootstrap for statistical inference on random graphs
- Fast generation of random connected graphs with prescribed degrees
- Shortest path discovery of complex networks
- Emergence of scale-free networks from local connectivity and communication trade-offs
- Sampling networks by nodal attributes
- Graph Theory and Networks in Biology
- Linear regression and its inference on noisy network-linked data
- Pathlength scaling in graphs with incomplete navigational information
- Random graphs with arbitrary i.i.d. degrees
- Implementation and Deployment of a Distributed Network Topology Discovery Algorithm
- Inhomogeneous substructures hidden in random networks
- Condition numbers and scale free graphs
- Bias reduction in traceroute sampling: towards a more accurate map of the Internet
- Dynamic Exploration of Networks: from general principles to the traceroute process
- Bounding the Bias of Tree-Like Sampling in IP Topologies
- Weighted Shortest Path Models: A Revisit to the Simulation of Internet Routing