Stochastic block models are a popular model of social and biological networks. In addition to the standard notion of communities as clumps of nodes that are densely connected to each other, they also allow for "functional" communities, where nodes are similar because the connect to the rest of the network in similar ways. Given the topology of a real network, one can simultaneously infer the types of the nodes, and the probabilities with which these types connect, using an Expectation-Maximization algorithm. The Expectation step can be carried out with Monte Carlo sampling, but a much faster approach is to use a Belief Propagation. Using the cavity method of statistical physics, we can then study phase transitions in the identifiability of these communities in various ensembles of random graphs. I will present empirical results on synthetic and real-world networks showing how well these algorithms work in practice, and discuss the challenges of making our analysis rigorous. (This is joint work with Lenka Zdeborova, Florent Krzakala, and Aurelien Decelle.) If time permits, I will also present some new results on the k-colorability threshold in random graphs.
Copyright. All Rights Reserved.