Network Inference from TraceRoute Measurements: Internet Topology `Species'
<|reference_start|>Network Inference from TraceRoute Measurements: Internet Topology `Species': 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.<|reference_end|>
@article{viger2005network,
    title={Network Inference from TraceRoute Measurements: Internet Topology
  `Species'},
    author={Fabien Viger, Alain Barrat, Luca Dall'Asta, Cun-Hui Zhang, and Eric D.
  Kolaczyk},
    journal={Phys. Rev. E 75 (2007) 056111},
    year={2005},
    doi={10.1103/PhysRevE.75.056111},
    archivePrefix={arXiv},
    eprint={cs/0510007},
    primaryClass={cs.NI cond-mat.stat-mech math.ST physics.soc-ph stat.TH}
}