Achieving Optimal Misclassification Proportion in Stochastic Block Model
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionmodelStochastic Block ModelSimilar Papers 제목 키워드 기반
Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information
We study the misclassification error for community detection in general heterogeneous stochastic block models (SBM) with noisy or partial label information. We establish a connection between the misclassification rate an…
Community DetectionCommunity Detection in Degree-Corrected Block Models
Community detection is a central problem of network data analysis. Given a network, the goal of community detection is to partition the network nodes into a small number of clusters, which could often help reveal interes…
Community DetectionAchieving Exact Cluster Recovery Threshold via Semidefinite Programming
The binary symmetric stochastic block model deals with a random graph of $n$ vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability $p$ within clus…
Stochastic Block ModelCommunity Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithms
The integration of network information and node attribute information has recently gained significant attention in the community detection literature. In this work, we consider community detection in the Contextual Label…
AttributeCommunity DetectionStochastic Block ModelAchieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
Resolving a conjecture of Abbe, Bandeira and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recoverin…
Community DetectionStochastic Block Model