Bayesian Inference of Global Statistics on Complex Networks using Random Walks

The study of complex networks is ubiquitous across physics, biology, and computer science, as well as many other disciplines. Examples include protein-protein interaction networks, the Worldwide Web, etc. Complete querying of these enormous systems is often impractical or impossible. We have developed a theoretical methodology for rapid Bayesian inference of the statistical properties of these complex networks based on the sampling method of random walks for networks with weighted or unweighted edges. The statistics of interest include, but are not limited to, the node degree distribution, the average degree of nearest-neighbor nodes, and the node clustering coefficient. Surprisingly, our formalism yields high-accuracy estimates of these statistics, and of the network size, after only a small fraction of network nodes have been explored. The Bayesian nature of our approach provides rigorous estimates of all parameter uncertainties. We have demonstrated our framework on several standard examples, including random, scale-free, and small-world networks, and have applied it to the network formed by the links between Wikipedia pages.