Network Inference from TraceRoute Measurements: Internet Topology `Species'

Abstract

Internet mapping projects generally consist in sampling the network from a limited set of sources by using traceroute probes. This methodology, akin to the merging of spanning trees from the different sources to a set of destinations, leads necessarily to a partial, incomplete map of the Internet. Accordingly, determination of Internet topology characteristics from such sampled maps is in part a problem of statistical inference. Our contribution begins with the observation that the inference of many of the most basic topological quantities -- including network size and degree characteristics -- from traceroute measurements is in fact a version of the so-called `species problem' in statistics. This observation has important implications, since species problems are often quite challenging. We focus here on the most fundamental example of a traceroute internet species: the number of nodes in a network. Specifically, we characterize the difficulty of estimating this quantity through a set of analytical arguments, we use statistical subsampling principles to derive two proposed estimators, and we illustrate the performance of these estimators on networks with various topological characteristics.

References in corpus (6)

• Statistical properties of sampled networks
• Accuracy and Scaling Phenomena in Internet Mapping
• Exploring networks with traceroute-like probes: theory and simulations
• Exploration of scale-free networks
• Estimation of sums of random variables: Examples and information bounds
• Random Walks on Complex Networks

Cited by in corpus (13)

• Compensating for population sampling in simulations of epidemic spread on temporal contact networks
• The Workshop on Internet Topology (WIT) Report
• Measuring Fundamental Properties of Real-World Complex Networks
• Graph Size Estimation
• Epidemic risk from friendship network data: an equivalence with a non-uniform sampling of contact networks
• K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases
• Shortest path discovery of complex networks
• Impact of spatially constrained sampling of temporal contact networks on the evaluation of the epidemic risk
• Sampling networks by nodal attributes
• What you see is not what you get: how sampling affects macroscopic features of biological networks
• Bias reduction in traceroute sampling: towards a more accurate map of the Internet
• Dynamic Exploration of Networks: from general principles to the traceroute process
• Weighted Shortest Path Models: A Revisit to the Simulation of Internet Routing