Some phase transitions in the stochastic block model

Series: 
Job Candidate Talk
Thursday, January 22, 2015 - 11:05
1 hour (actually 50 minutes)
Location: 
Skiles 006
,  
University of Texas, Austin, TX
,  
Organizer: 
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.