Achieving Optimal Misclassification Proportion in Stochastic Block Model

• Activity Number: 331
• Type: Invited
• Date/Time: Tuesday, August 11, 2015 : 10:30 AM to 12:20 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Chao Gao and Harrison Zhou* and Zongming Ma and Anderson Ye Zhang
• Companies: Yale University and Yale University and University of Pennsylvania and Yale University
• Keywords: network ; community detection ; stochastic block model ; two-stage procedure ; minimax rate ; computation

Abstract

Community detection is a fundamental statistical problem in network data analysis. Many algorithms have been proposed to tackle this problem. Typically 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 talk, 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. The practical effectiveness of the new algorithm is demonstrated by competitive numerical results.