Community Detection: Minimaxity and A Computationally Efficient Algorithm

Seminar: 
Combinatorics Seminar
Event time: 
Thursday, February 4, 2016 - 11:00am to 12:00pm
Location: 
215 LOM
Speaker: 
H. Zhou
Speaker affiliation: 
Yale
Event description: 

Recently network analysis has gained more and more attention in statistics, as well as in computer science, probability, and applied mathematics. Community detection for stochastic block model (SBM) is possibly the most studied topic in network analysis. Many methodologies have been proposed. Several beautiful and significant phase transition results are obtained in various settings. In this talk, we provide a general minimax theory for community detection. It gives the minimax rates of mis-match ratio for a wide rage of settings including homogeneous and inhomogeneous SBM, dense and sparse networks, finite and growing number of communities. The result immediately implies threshold phenomenon for consistent community detection, exact recovery as well as a convergence rate sandwiched in-between. The rate is in an exponential form. We obtain the upper bound by a penalized likelihood approach. The lower bound is achieved by novel reduction from a global mis-match ratio to a local clustering problem for one node through the exchangability property. In addition, we present a computationally feasible two-stage method that achieves optimal statistical performance in misclassification proportion for stochastic block model under very weak regularity conditions. Our two-stage procedure consists of a generic refinement step that can take a wide range of weakly consistent community detection procedures as initializer, to which the refinement stage applies and outputs a community assignment achieving optimal misclassification proportion with high probability. If time permits, we will discuss briefly extensions to more general models.