 |
Center for Nonlinear Studies |
A central problem in analyzing networks is partitioning them into modules or communities, clusters with a statistically homogeneous pattern of links to each other or to the rest of the network. A principled approach to address this problem is to fit the network on a stochastic block model, this task is, however, intractable exactly. In this talk we discuss application of belief propagation algorithm to module detection. In the first part we present an asymptotically exact analysis of the stochastic block model. We quantify properties of the detectability/undetectability phase transition and the easy/hard phase transition for the module detection problem. In a second part of the talk we discuss applications of the algorithm to real large scale data, and related issues such as parameter learning, selection among different stochastic block models, and comparison to existing approaches.
Host: Garrett Kenyon, gkenyon@lanl.gov, 7-1900, IS & T