Exploring networks with traceroute-like probes: theory and simulations

Abstract

Mapping the Internet generally consists in sampling the network from a limited set of sources by using traceroute-like probes. This methodology, akin to the merging of different spanning trees to a set of destination, has been argued to introduce uncontrolled sampling biases that might produce statistical properties of the sampled graph which sharply differ from the original ones. In this paper we explore these biases and provide a statistical analysis of their origin. We derive an analytical approximation for the probability of edge and vertex detection that exploits the role of the number of sources and targets and allows us to relate the global topological properties of the underlying network with the statistical accuracy of the sampled graph. In particular, we find that the edge and vertex detection probability depends on the betweenness centrality of each element. This allows us to show that shortest path routed sampling provides a better characterization of underlying graphs with broad distributions of connectivity. We complement the analytical discussion with a throughout numerical investigation of simulated mapping strategies in network models with different topologies. We show that sampled graphs provide a fair qualitative characterization of the statistical properties of the original networks in a fair range of different strategies and exploration parameters. Moreover, we characterize the level of redundancy and completeness of the exploration process as a function of the topological properties of the network. Finally, we study numerically how the fraction of vertices and edges discovered in the sampled graph depends on the particular deployements of probing sources. The results might hint the steps toward more efficient mapping strategies.

This paper is related to cond-mat/0406404, with explorations of different networks and complementary discussions

References in corpus (3)

• Accuracy and Scaling Phenomena in Internet Mapping
• Exploration of scale-free networks
• Why Mapping the Internet is Hard

Cited by in corpus (23)

• The Internet AS-Level Topology: Three Data Sources and One Definitive Metric
• AS Relationships: Inference and Validation
• Exploring Complex Networks through Random Walks
• Lessons from Three Views of the Internet Topology
• Graph Annotations in Modeling Complex Network Topologies
• The Workshop on Internet Topology (WIT) Report
• A critical look at power law modelling of the Internet
• Monitoring the edges of a graph using distances
• Network Inference from TraceRoute Measurements: Internet Topology `Species'
• A Radar for the Internet
• A New Computationally Efficient Measure of Topological Redundancy of Biological and Social Networks
• K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases
• Algorithmic Perspectives of Network Transitive Reduction Problems and their Applications to Synthesis and Analysis of Biological Networks
• Bounds and extremal graphs for monitoring edge-geodetic sets in graphs
• Damage detection via shortest path network sampling
• Sampling networks by nodal attributes
• Understanding edge-connectivity in the Internet through core-decomposition
• A new intrinsic way to measure IXP performance: an experience in Bolivia
• Router-level community structure of the Internet Autonomous Systems
• Near-Linear Query Complexity for Graph Inference
• Impact of Random Failures and Attacks on Poisson and Power-Law Random Networks
• Weighted Shortest Path Models: A Revisit to the Simulation of Internet Routing
• Spatial Neural Networks and their Functional Samples: Similarities and Differences