Sampling networks by the union of m shortest path trees

摘要

Many network topology measurements capture or sample only a partial view of the actual network structure, which we call the underlying network. Sampling bias is a critical problem in the field of complex networks ranging from biological networks, social networks and artificial networks like the Internet. This bias phenomenon depends on both the sampling method of the measurements and the features of the underlying networks. In RIPE NCC and the PlanetLab measurement architectures, the Internet is mapped as G_(UmSpt), the union of shortest paths between each pair of a set .M of m testboxes, or equivalently, m shortest path trees. In this paper, we investigate this sampling method on a wide class of real-world complex networks as well as on the weighted Erd6s-Renyi random graphs. This general framework examines the effect of the set of testboxes on G_(UmSpt). We establish the correlation between the subgraph G_M of the underlying network, i.e. the set ,M and the direct links between nodes of set M, and the sampled network G_(UmSpt),. Furthermore, we illustrate that in order to obtain an increasingly accurate view of a given network, a higher than linear detection/measuring effort (the relative size m/N of set M) is needed, where N is the size of the underlying network. Finally, when the relative size m/N of set .M is small, we characterize the kind of networks possessing small sampling bias, which provides insights on how to place the testboxes for good network topology measurement.