achieving optimal misclassification proportion in stochastic block models

• DOI: 10.5555/3122009.3153016
• Publication Date: 2015-01-01
• Authors: Chao Gao; Anderson Y. Zhang; Zongming Ma; Harrison H. Zhou
• Keywords: Social and Information Networks (cs.SI); FOS: Computer and information sciences; Mathematics - Statistics Theory; Computer Science - Social and Information Networks; Machine Learning (stat.ML); Statistics Theory (math.ST); 01 natural sciences; Methodology (stat.ME); Statistics - Machine Learning; FOS: Mathematics; 0101 mathematics; Statistics - Methodology

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 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.