Scalable uniform graph sampling by local computation. (English) Zbl 1227.60095
The author addresses the problem of sampling a unidirectional, unweighted graph such that its vertices are sampled uniformly by local computations only. The sampling algorithm makes use of the representation of a graph as a discrete Markov chain and of a random walk sampler such that the invariant distribution is uniform. The author presents a new method that combines a random walk that converges fast but does not reach the uniform distribution with a second method that converges slowly to the correct invariant distribution. This combined algorithm converges faster to the correct invariant distribution than the standard uniform random walk. Moreover, samples can be obtained using only local information of the individual vertices and the knowledge of the complete graph is not incorporated into the sampling method. Background, previous results and the implementation of the method are thoroughly discussed and the applicability of the method is illustrated on numerical examples.
Reviewer: Martin Riedler (Linz)
MSC:
60J22 | Computational methods in Markov chains |
60J20 | Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) |
65C40 | Numerical analysis or methods applied to Markov chains |
62D05 | Sampling theory, sample surveys |