Some phase transitions in the stochastic block model

Job Candidate Talk
Thursday, January 22, 2015 - 11:05am for 1 hour (actually 50 minutes)
Skiles 006
Joseph Neeman – University of Texas, Austin, TX –
Prasad Tetali
The stochastic block model is a random graph model that was originally introduced 30 years ago to model community structure 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.