Community Detection in Degree-Corrected Block Models

Abstract

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 interesting structures. The present paper studies community detection in Degree-Corrected Block Models (DCBMs). We first derive asymptotic minimax risks of the problem for a misclassification proportion loss under appropriate conditions. The minimax risks are shown to depend on degree-correction parameters, community sizes, and average within and between community connectivities in an intuitive and interpretable way. In addition, we propose a polynomial time algorithm to adaptively perform consistent and even asymptotically optimal community detection in DCBMs.

References in corpus (8)

• Stochastic blockmodels and community structure in networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Fast community detection by SCORE
• Stochastic Block Models and Reconstruction
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Impact of regularization on Spectral Clustering

Cited by in corpus (9)

• A Survey on Theoretical Advances of Community Detection in Networks
• Testing for Global Network Structure Using Small Subgraph Statistics
• Optimal hypothesis testing for stochastic block models with growing degrees
• A Sharp Lower Bound for Mixed-membership Estimation
• Testing Community Structures for Hypergraphs
• Optimal Bipartite Network Clustering
• Optimal Rates for Community Estimation in the Weighted Stochastic Block Model
• Revisiting Spectral Graph Clustering with Generative Community Models
• Exponential error rates of SDP for block models: Beyond Grothendieck's inequality