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.

• Publication year

  2017

• Venue

  Physical Review Letters

• Publication date

  2017-12-03

• Fields of study

  Mathematics, Physics, Computer Science, Medicine

• Identifiers
  DOI 10.1103/PhysRevLett.121.038301arXiv 1712.00804PMID 30085804
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Eight challenges for network epidemic models.

  2015cited by this paper
• Estimating network degree distributions under sampling: An inverse problem, with applications to monitoring social media networks

  2013cited by this paper
• Estimating Omissions From Searches

  2012cited by this paper
• Estimating network parameters using random walks

  2012cited by this paper
• Topologically biased random walk and community finding in networks.

  2010cited by this paper
• Quantifying network heterogeneity.

  2010cited by this paper
• A Kinetic View of Statistical Physics

  2010cited by this paper
• Walking in Facebook: A Case Study of Unbiased Sampling of OSNs

  2010cited by this paper
• Networks: An Introduction

  2010cited by this paper
• Traffic-driven epidemic spreading in finite-size scale-free networks

  2009cited by this paper
• Self-similarity of complex networks and hidden metric spaces

  2007cited by this paper
• First-passage times in complex scale-invariant media

  2007cited by this paper
• Navigability of Complex Networks

  2007cited by this paper
• Statistical properties of sampled networks by random walks.

  2006cited by this paper
• Random walks and Brownian motion: a method of computation for first-passage times and related quantities in confined geometries.

  2006cited by this paper
• Statistical properties of sampled networks.

  2005cited by this paper
• What is special about diffusion on scale-free nets?

  2004cited by this paper
• Random walks on complex networks.

  2003cited by this paper
• Mixing patterns in networks.

  2002cited by this paper
• Statistical mechanics of complex networks

  2001influential reference
• Mean-field solution of the small-world network model.

  1999cited by this paper
• On power-law relationships of the Internet topology

  1999cited by this paper
• Collective dynamics of ‘small-world’ networks

  1998cited by this paper
• Stochastic Processes in Physics and Chemistry

  1995cited by this paper
• On the evolution of random graphs

  1984cited by this paper
• UVM ScholarWorks UVM ScholarWorks

  year unknowncited by this paper

• EVOLUTION AND STOCHASTIC DYNAMICS IN COMPLEX SYSTEMS

  2022cites this paper