Bayesian Exploration of Complex Networks by Random Walks*

Large-scale networks represent a broad spectrum of systems in nature, science, and technology. In addition to the computer-based networks such as the World Wide Web and the Internet, online social networks such as Twitter and Facebook, and knowledge-sharing online platforms such as Wikipedia and YouTube, exert considerable influence on our everyday activities. Many of these networks are large and constantly evolving, which makes investigation of their statistical properties a challenging task. In particular, estimating the size of the network becomes non-trivial if the network is too large to visit every node. I will describe a novel methodology, based on random walks, for the inference of statistical properties of complex 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. I will show how our formalism can yield high-accuracy estimates of these statistics, and of the network size, after only a small fraction of network nodes has been explored. I will demonstrate our computational framework on several standard examples, including random, scale-free, and small-world networks. I will then discuss how our methods can be used to explore Wikipedia, study propagation of infectious diseases on contact networks, and obtain population data from small samples. \\ {\bf References} 1. Kion-Crosby, W.B. and Morozov, A.V., Phys. Rev. Lett. {\bf 2018} {\it 121}, 038301