On the Quality of Sampling from Geographic Networks

摘要

We consider the problem of randomly sampling information from a network embedded in two-dimensional space, as characteristic of a physical network. We ask in particular what factor most affects the sampling quality: The distribution of the nodes in the space or the connectivity structure of the links? We hypothesize that, although node distribution is also effective in sampling quality, the link connectivity dominates the sampling quality. Our hypotheses are confirmed via extensive simulations as well as theoretical background on the relationship between eigenvalues of the matrix representing the network and the link connectivity properties. This work has relevance to both the analysis of information dissemination in various networks as well as the engineering of networks to be more efficient and resilient for such.