2021/07/30 by Huan Qing, Qing, Huan, Jingli Wang +1
Computer Science · Engineering · #62H30 #91C20 #Advanced Clustering Algorithms Research #FOS: Computer and information sciences #Face and Expression Recognition #Methodology (stat.ME) #Remote-Sensing Image Classification
paper · pdf · doi:10.48550/arxiv.2107.14705
openalex publication_date 2021/07/30 · openalex created_date 2021/08/16 · openalex updated_date 2026/07/28
Mixed membership community detection is a challenge problem in network analysis. To estimate the memberships and study the impact of regularized spectral clustering under the mixed membership stochastic block (MMSB) model, this article proposes two efficient spectral clustering approaches based on regularized Laplacian matrix, Simplex Regularized Spectral Clustering (SRSC) and Cone Regularized Spectral Clustering (CRSC). SRSC and CRSC methods are designed based on the ideal simplex structure and the ideal cone structure in the variants of the eigen-decomposition of the population regularized Laplacian matrix. We show that these two approaches SRSC and CRSC are asymptotically consistent under mild conditions by providing error bounds for the inferred membership vector of each node under MMSB. Through the theoretical analysis, we give the upper and lower bound for the regularizer τ. By introducing a parametric convergence probability, we can directly see that when τ is large these two methods may still have low error rates but with a smaller probability. Thus we give an empirical optimal choice of τ is O(log(n)) with n the number of nodes to detect sparse networks. The proposed two approaches are successfully applied to synthetic and empirical networks with encouraging results compared with some benchmark methods.