Traceroute sampling makes random graphs appear to have power law degree distributions
arXiv:cond-mat/0312674 · doi:10.1103/PhysRevLett.94.018701
Abstract
The topology of the Internet has typically been measured by sampling traceroutes, which are roughly shortest paths from sources to destinations. The resulting measurements have been used to infer that the Internet's degree distribution is scale-free; however, many of these measurements have relied on sampling traceroutes from a small number of sources. It was recently argued that sampling in this way can introduce a fundamental bias in the degree distribution, for instance, causing random (Erdos-Renyi) graphs to appear to have power law degree distributions. We explain this phenomenon analytically using differential equations to model the growth of a breadth-first tree in a random graph G(n,p=c/n) of average degree c, and show that sampling from a single source gives an apparent power law degree distribution P(k) ~ 1/k for k < c.
References in corpus (2)
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