Name
Title | ||
|---|---|---|
A statistical approach to the traceroute-like exploration of networks: theory and simulations |
Abstract | ||
|---|---|---|
Mapping the Internet generally consists in sampling the network from a limited set of sources by us- ing traceroute-like probes. This methodology, akin to the merging of different spanning trees to a set of destina- tions, has been argued to introduce uncontrolled sampling biases that might produce statistical properties of the sam- pled graph which sharply differ from the original ones (7-9). Here we explore these biases and provide a statistical analy- sis of their origin. We derive a mean-field analytical approx - imation 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 sam- pled graph. In particular we find that the edge and vertex detection probability is depending on the betweenness cen- trality of each element. This allows us to show that short- est path routed sampling provides a better characterization of underlying graphs with scale-free topology. We comple- ment the analytical discussion with a throughout numeri- cal investigation of simulated mapping strategies in different network models. We show that sampled graphs provide a fair qualitative characterization of the statistical prop erties of the original networks in a fair range of different strate- gies and exploration parameters. The numerical study also allows the identification of intervals of the exploration pa - rameters that optimize the fraction of nodes and edges dis- covered in the sampled graph. This finding might hint the steps toward more efficient mapping strategies. |
Year | Venue | Keywords |
|---|---|---|
2004 | Clinical Orthopaedics and Related Research | internet exploration,topology in- ference.,—traceroute,limit set,mean field,network model,spanning tree,network theory,scale free |
Field | DocType | Volume |
Mathematical optimization,Vertex (geometry),Shortest path problem,Quantum mechanics,traceroute,Algorithm,Betweenness centrality,Spanning tree,Sampling (statistics),Network model,Mathematics,The Internet | Journal | cond-mat/0 |
ISSN | Citations | PageRank |
CAAN 2004, LNCS 3405, p. 140 (2005) . | 20 | 1.16 |
References | Authors | |
4 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luca Dall'Asta | 1 | 493 | 39.53 |
| J. Ignacio Alvarez-hamelin | 2 | 143 | 13.31 |
| Alain Barrat | 3 | 1401 | 87.12 |
| Alexei Vázquez | 4 | 95 | 7.85 |
| Alessandro Vespignani | 5 | 1647 | 109.55 |