Rapid Bayesian Inference of Global Network Statistics Using Random Walks

Abstract

We propose a novel Bayesian methodology which uses random walks for rapid inference of statistical properties of undirected networks with weighted or unweighted edges. Our formalism yields high-accuracy estimates of the probability distribution of any network node-based property, and of the network size, after only a small fraction of network nodes has been explored. The Bayesian nature of our approach provides rigorous estimates of all parameter uncertainties. We demonstrate our framework on several standard examples, including random, scale-free, and small-world networks, and apply it to study epidemic spreading on a scale-free network. We also infer properties of the large-scale network formed by hyperlinks between Wikipedia pages.

References in corpus (15)

• Statistical mechanics of complex networks
• Mixing patterns in networks
• First-passage times in complex scale-invariant media
• Navigability of Complex Networks
• Statistical properties of sampled networks
• Mean-field solution of the small-world network model
• Self-similarity of complex networks and hidden metric spaces
• Traffic-driven Epidemic Spreading in Finite-size Scale-Free Networks
• Occupation times of random walks in confined geometries: From random trap model to diffusion limited reactions
• Statistical properties of sampled networks by random walks
• Topologically biased random walk with application for community finding in networks
• Estimating network degree distributions under sampling: An inverse problem, with applications to monitoring social media networks
• Estimation of global network statistics from incomplete data
• Estimating Omissions from Searches
• Random Walks on Complex Networks