Model-based and model-free community recovery in graphs
Advisor: Marina Meila
There have been many recent theoretical advances in the model-based community recovery for network data. In the center of it are the Stochastic Block Model and its extension, Degree Corrected Stochastic Block Model. Under assumptions on the balance and separation of clusters, theoretical guarantees have been provided to ensure the recovery of the true clusters with high probability. In the first part of this talk, we introduce a wider class of network models called Preference Frame Model. We show that under weaker assumptions, the communities or clusters can be recovered by spectral clustering algorithm with essentially the same guarantees.
The model-based results, despite their importance, are limited by a strong and difficult-to-verify assumption that the observed data are generated from the model. In the second part of the talk, we present the model-free community recovery, where we do not make assumptions about the data generating process and provide theoretical guarantees for the performance of the model based clustering algorithms in this framework.