Spring 2016
Seminars are held on Thursdays in Cullimore Hall. For questions about the seminar schedule, please contact Antai Wang.
Date: March 31, 2016
Speaker: Zongming Ma
Department of Statistics,
University of Pennsylvania
Title: "Achieving Optimal Misclassification Proportion in Stochastic Block Model"
Abstract:
Community detection is a fundamental statistical problem in network data analysis. Many algorithms have been proposed to tackle this problem. Most of these algorithms are not guaranteed to achieve the statistical optimality of the problem, while procedures that achieve information theoretic limits for general parameter spaces are not computationally tractable. In this paper, we present a computationally feasible two-stage method that achieves optimal statistical performance in misclassification proportion for stochastic block model under weak regularity conditions. Our two-stage procedure consists of a refinement stage motivated by penalized local maximum likelihood estimation. This stage can take a wide range of weakly consistent community detection procedures as initializer, to which it applies and outputs a community assignment that achieves optimal misclassification proportion with high probability. The practical effectiveness of the new algorithm is demonstrated by competitive numerical results. Time permitting, we will also discuss related results for degree-corrected block model.
This is a joint work with Chao Gao, Anderson Zhang and Harrison Zhou at Yale University.