Abstract
The general methodology used to construct Internet maps consists in merging all the discovered paths obtained by sending data packets from a set of active computers to a set of destination hosts, obtaining a graphlike representation of the network. This technique, sometimes referred to as Internet tomography, spurs the issue concerning the statistical reliability of such empirical maps. We tackle this problem by modeling the network sampling process on synthetic graphs and by using a mean-field approximation to obtain expressions for the probability of edge and vertex detection in the sampled graph. This allows a general understanding of the origin of possible sampling biases. In particular, we find a direct dependence of the map statistical accuracy upon the topological properties (in particular, the betweenness centrality property) of the underlying network. In this framework, it appears that statistically heterogeneous network topologies are captured better than the homogeneous ones during the mapping process. Finally, the analytical discussion is complemented with a thorough numerical investigation of simulated mapping strategies in network models with varying topological properties.
Keywords
Internet maps, networks, statistical theory, Internet tomography
Subject Categories
Internet, Topology
Disciplines
Physics
Publisher
American Physical Society
Publication Date
3-1-2005
Rights Information
©2005 American Physical Society
Rights Holder
American Physical Society
Permanent URL
Recommended Citation
Dall'Asta, L; Alvarez-Hamelin, I; Barrat, A; Vazquez, A; and Vespignani, A, "Statistical theory of Internet exploration" (2005). Physics Faculty Publications. Paper 186. http://hdl.handle.net/2047/d20002146
Click button above to open, or right-click to save.
Notes
Originally published in Physical Review E, v.71 no.3 (2005), 36135. DOI:10.1103/PhysRevE.71.036135. Dr. Vespignani is affiliated with Northeastern University as of the time of deposit.