Probability Seminar

Joe NeemanUniversity of Texas at Austin
Some phase transitions in the stochastic block model

Friday, December 5, 2014 - 2:30pm
Malott 206

The stochastic block model is a random graph model that was originally proposed 30 years ago to study community detection in networks. To generate a random graph from this model, begin with two classes of vertices and then connect each pair of vertices independently at random, with probability p if they are in the same class and probability q otherwise. Some questions come to mind: can we reconstruct the classes if we only observe the graph? What if we only want to partially reconstruct the classes? How different is this model from an Erdos-Renyi graph anyway? The answers to these questions depend on p and q, and we will say exactly how.