Featured Speaker :  Allen Liu (MIT EECS)

Title :  Robust Community Detection

Abstract :  Understanding community structure in networks and graphs is a fundamental question with wide-ranging applications.  The canonical model for studying community detection is the stochastic block model (SBM) which generates a random graph where different groups of vertices are connected with different probabilities.  There has been extensive work on community detection in the stochastic block model and sharp characterizations of many recovery thresholds are known.  However, these thresholds are often very brittle and break down when the graph is perturbed, even in a seemingly helpful way.  In this talk, we study the problem of community detection through the lens of robustness, where much less is known.  We will survey both impossibility results and new algorithms that achieve strong robustness guarantees while nearly matching some thresholds from the non-robust setting.