The IPB colloquium will be held on Wednesday, 20 June 2018 at 13:30 in the “Zvonko Marić” lecture hall of the Institute of Physics Belgrade. The talk entitled

"Rapid exploration of complex networks by random walks"

will be given by Prof. Dr. Alexandre Morozov (Department of Physics, Rutgers University, USA).

Abstract of the talk:

Humanity has become increasingly dependent on large-scale networks. In addition to the original computer-based networks, such as the World Wide Web and the Internet, several online social networks have emerged, notably Twitter and Facebook. Our daily professional and personal lives are influenced by knowledge-sharing online services, such as Wikipedia and YouTube. More generally, complex networks describe a broad spectrum of systems in nature, science, technology, and society. Many of these networks are large and evolving, making investigation of their statistical properties a challenging task. In particular, estimating the network size becomes non-trivial if the network is too large to visit every node. In this talk we 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. We 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. We will first demonstrate our computational framework on several standard examples, including random, scale-free, and small-world networks. Next, we will discuss how our method can be used to explore Wikipedia, study propagation of infectious diseases on contact networks, and obtain census-type population data from small samples.