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

• Publication year

  2016

• Venue

  Annals of Statistics

• Publication date

  2016-07-24

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1214/17-AOS1615arXiv 1607.06993
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Asymptotic statistics

  2018influential reference
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models

  2015cited by this paper
• Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery

  2015cited by this paper
• Achieving Optimal Misclassification Proportion in Stochastic Block Models

  2015influential reference
• Convexified Modularity Maximization for Degree-corrected Stochastic Block Models

  2015influential reference
• An Impossibility Result for Reconstruction in a Degree-Corrected Planted-Partition Model

  2015cited by this paper
• Stochastic Block Model and Community Detection in Sparse Graphs: A spectral algorithm with optimal rate of recovery

  2015influential reference
• Achieving exact cluster recovery threshold via semidefinite programming

  2015cited by this paper
• Minimax Rates of Community Detection in Stochastic Block Models

  2015influential reference
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions

  2015cited by this paper
• Consistency Thresholds for the Planted Bisection Model

  2014cited by this paper
• Exact Recovery in the Stochastic Block Model

  2014cited by this paper
• Consistency Thresholds for Binary Symmetric Block Models

  2014cited by this paper
• Model selection and hypothesis testing for large-scale network models with overlapping groups

  2014cited by this paper
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

  2014cited by this paper
• Community detection thresholds and the weak Ramanujan property

  2013cited by this paper
• A Proof of the Block Model Threshold Conjecture

  2013cited by this paper
• Impact of regularization on spectral clustering

  2013cited by this paper
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

  2013influential reference
• Consistency of spectral clustering in stochastic block models

  2013cited by this paper
• Pseudo-likelihood methods for community detection in large sparse networks

  2012cited by this paper
• Stochastic Block Models and Reconstruction

  2012cited by this paper
• FAST COMMUNITY DETECTION BY SCORE

  2012influential reference
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications

  2011cited by this paper
• Consistency of community detection in networks under degree-corrected stochastic block models

  2011cited by this paper
• Stochastic blockmodels and community structure in networks

  2010cited by this paper
• Spectral clustering and the high-dimensional stochastic blockmodel

  2010cited by this paper
• A nonparametric view of network models and Newman–Girvan and other modularities

  2009cited by this paper
• The political blogosphere and the 2004 U.S. election: divided they blog

  2005cited by this paper
• Spectral analysis of random graphs with skewed degree distributions

  2004cited by this paper
• Stochastic blockmodels: First steps

  1983cited by this paper

• Adjacency Spectral Embeddings of Correlation Networks

  2026cites this paper
• Distributional Limits for Eigenvalues of Graphon Kernel Matrices

  2026cites this paper
• Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Model

  2026cites this paper
• Optimal Graph Clustering without Edge Density Signals

  2025influential citation
• Information Loss and Disparate Effects in Network Embeddings

  2025cites this paper
• Biological Processing Units: Leveraging an Insect Connectome to Pioneer Biofidelic Neural Architectures

  2025cites this paper
• Graph Neural Networks Powered by Encoder Embedding for Improved Node Learning

  2025cites this paper
• Optimal clustering by Lloyd’s algorithm for low-rank mixture model

  2025cites this paper
• Strongly Consistent Community Detection in Popularity Adjusted Block Models

  2025influential citation
• A Bootstrap-based Method for Testing Similarity of Matched Networks

  2025cites this paper
• Understanding asymptotic consistency and its unique advantages in large sample statistical inference

  2025cites this paper
• Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy

  2025cites this paper
• A Goodness-of-Fit Test for Sparse Networks

  2025cites this paper
• Testing common degree-correction parameters of multilayer networks

  2025cites this paper
• Detecting Community Structures in Directed Networks Based on Latent In-Out-Link Patterns

  2025cites this paper
• Community Detection for Contextual-Lsbm: Theoretical Limitations of Misclassification Rate and Efficient Algorithms

  2025cites this paper
• Joint Modeling of Change-Point Identification and Dependent Dynamic Community Detection

  2024cites this paper
• Online Bayesian changepoint detection for network Poisson processes with community structure

  2024cites this paper
• Testing common invariant subspace of multilayer networks

  2024cites this paper
• Degree-Heterogeneous Latent Class Analysis for High-Dimensional Discrete Data

  2024cites this paper
• VEC-SBM: Optimal Community Detection with Vectorial Edges Covariates

  2024cites this paper
• Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models

  2024cites this paper
• Signed Diverse Multiplex Networks: Clustering and Inference

  2024cites this paper
• Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models

  2024cites this paper
• Special invited paper: The SCORE normalization, especially for heterogeneous network and text data

  2023cites this paper
• Optimal recovery by maximum and integrated conditional likelihood in the general Stochastic Block Model

  2023cites this paper
• Dissimilarity-based hypothesis testing for community detection in heterogeneous networks

  2023cites this paper
• Statistical Network Analysis: Past, Present, and Future

  2023cites this paper
• Community Detection Guarantees using Embeddings Learned by Node2Vec

  2023cites this paper
• A Theoretical Analysis of DeepWalk and Node2vec for Exact Recovery of Community Structures in Stochastic Blockmodels

  2023cites this paper
• A social network monitoring procedure based on community statistics

  2023cites this paper
• Efficiently matching random inhomogeneous graphs via degree profiles

  2023cites this paper
• Global Minima, Recoverability Thresholds, and Higher-Order Structure in GNNS

  2023cites this paper
• Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model

  2023cites this paper
• CataBEEM: Integrating Latent Interaction Categories in Node-wise Community Detection Models for Network Data

  2023cites this paper
• Graph Encoder Ensemble for Simultaneous Vertex Embedding and Community Detection

  2023cites this paper
• Combinatorial-Probabilistic Trade-Off: P-Values of Community Property Test in the Stochastic Block Models

  2023cites this paper
• Of Spiky SVDs and Music Recommendation

  2023cites this paper
• A Survey of Graph Neural Networks on Synthetic Data

  2023cites this paper
• Adversarially Robust Clustering With Optimality Guarantees

  2023cites this paper
• Semi-supervised Community Detection via Structural Similarity Metrics

  2023influential citation
• Fundamental Limits of Spectral Clustering in Stochastic Block Models

  2023cites this paper
• SCOREH+: A High-Order Node Proximity Spectral Clustering on Ratios-of-Eigenvectors Algorithm for Community Detection

  2023cites this paper
• Community Detection and Classification Guarantees Using Embeddings Learned by Node2Vec

  2023cites this paper
• Subsampling-based modified Bayesian information criterion for large-scale stochastic block models

  2023cites this paper
• rMultiNet: An R Package For Multilayer Networks Analysis

  2023cites this paper
• for weak signals

  2022cites this paper
• Multiway Spherical Clustering Via Degree-Corrected Tensor Block Models

  2022influential citation
• Community detection for multilayer weighted networks

  2022cites this paper
• Testing community structure for hypergraphs

  2022cites this paper
• The SCORE normalization, especially for highly heterogeneous network and text data

  2022cites this paper
• Optimal Network Membership Estimation under Severe Degree Heterogeneity

  2022cites this paper
• The Multivariate Community Hawkes Model for Dependent Relational Events in Continuous-time Networks

  2022cites this paper
• Minimax optimal clustering of bipartite graphs with a generalized power method

  2022influential citation
• Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model

  2022influential citation
• Higher-order accurate two-sample network inference and network hashing

  2022cites this paper
• Node-Level Community Detection within Edge Exchangeable Models for Interaction Processes

  2022cites this paper
• Adaptive Weights Community Detection

  2022cites this paper
• Selecting a significance level in sequential testing procedures for community detection

  2022cites this paper
• Community detection for directed weighted networks

  2022cites this paper
• Community detection algorithms for recommendation systems: techniques and metrics

  2022cites this paper
• Joint Spectral Clustering in Multilayer Degree-Corrected Stochastic Blockmodels

  2022cites this paper
• Community detection for weighted bipartite networks

  2021influential citation
• Exact Recovery of Community Structures Using DeepWalk and Node2vec

  2021cites this paper
• Degree-corrected distribution-free model for community detection in weighted networks

  2021cites this paper
• An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees

  2021influential citation
• Consistency of random-walk based network embedding algorithms

  2021influential citation
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian

  2021cites this paper
• Dynamic community discovery via common subspace projection

  2021cites this paper
• Estimation and clustering in popularity adjusted block model

  2021cites this paper
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons

  2021cites this paper
• Efficient hypothesis testing for community detection in heterogeneous networks by graph dissimilarity

  2021cites this paper
• Block dense weighted networks with augmented degree correction

  2021cites this paper
• Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method

  2021cites this paper
• Consistent Nonparametric Methods for Network Assisted Covariate Estimation

  2021influential citation
• Community detection in complex networks: From statistical foundations to data science applications

  2021cites this paper
• Rate-Optimal Subspace Estimation on Random Graphs

  2021cites this paper
• Consistency of spectral clustering for directed network community detection

  2021cites this paper
• Clustering of Diverse Multiplex Networks

  2021cites this paper
• Network structure optimization for social networks by minimizing the average path length

  2021cites this paper
• Gravity algorithm for the community detection of large-scale network

  2021cites this paper
• Undirected and Directed Network Analysis of the Chinese Stock Market

  2021cites this paper
• Subsampling spectral clustering for stochastic block models in large-scale networks

  2021cites this paper
• Community detection in censored hypergraph

  2021cites this paper
• The Hierarchy of Block Models

  2020cites this paper
• Statistical Inference in Heterogeneous Block Model

  2020cites this paper
• Universal Latent Space Model Fitting for Large Networks with Edge Covariates

  2020cites this paper
• Rate optimal Chernoff bound and application to community detection in the stochastic block models

  2020cites this paper
• General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers

  2020cites this paper
• Identification of the effects of the existing network properties on the performance of current community detection methods

  2020cites this paper
• Interpretable Stochastic Block Influence Model: Measuring Social Influence Among Homophilous Communities

  2020cites this paper
• Linear regression and its inference on noisy network‐linked data

  2020cites this paper
• Topical Community Detection: an Embedding User and Content Similarity Method (short paper)

  2020cites this paper
• Community detection in sparse latent space models

  2020influential citation
• Estimating the number of communities by Stepwise Goodness-of-fit

  2020cites this paper
• Bayesian Testing for Exogenous Partition Structures in Stochastic Block Models

  2020cites this paper
• Combinatorial-Probabilistic Trade-Off: Community Properties Test in the Stochastic Block Models

  2020cites this paper
• Fast Network Community Detection With Profile-Pseudo Likelihood Methods

  2020cites this paper
• A Community Detection Algorithm for Heterogeneous Information Networks

  2020cites this paper
• Robustness of Community Detection to Random Geometric Perturbations

  2020cites this paper