Rapid Bayesian Inference of Global Network Statistics Using Random Walks

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.

Figure 1

Epidemic spreading statistics. (a) Pseudotarget RT distribution. Equation (4) parametrized by exact $q_p$ is shown as a cyan solid line. (b) $\mathrm{MLE}\pm 2\sigma$ (red circles with error bars) for the node degree distribution; exact distribution is shown as a blue solid line and its average is shown as a vertical line. (c) $\mathrm{MLE}\pm 2\sigma$ (red circles with error bars) for the fraction of infected nodes $\rho (t)$ computed at unit time intervals, with the exact value shown as a dashed blue line. (d) Histograms of ${\beta }_c$ MLEs obtained using $10^4$ independent runs with $\ell ={10}^2$, $10^3$, $10^4$ steps. Exact value is shown as a vertical dashed line.

Figure 2

Wikipedia network statistics. (a) Pseudotarget RT distribution. Equation (4) parametrized by ${\widehat{q}}_p$ is shown as a cyan solid line. (b) $\mathrm{MLE}\pm 2\sigma$ for $N$ as a function of ${\mathcal{K}}_p$. (c) $\mathrm{MLE}\pm 2\sigma$ for the degree distribution of Wikipedia pages of all types. Power-law fit is shown as a green dashed line. Average degree is shown as a vertical line. (d) $\mathrm{MLE}\pm 2\sigma$ for the distribution of Wikipedia page sizes. Average size is shown as a vertical line.