Consistency of community detection in networks under degree-corrected stochastic block models

Abstract

Community detection is a fundamental problem in network analysis, with applications in many diverse areas. The stochastic block model is a common tool for model-based community detection, and asymptotic tools for checking consistency of community detection under the block model have been recently developed. However, the block model is limited by its assumption that all nodes within a community are stochastically equivalent, and provides a poor fit to networks with hubs or highly varying node degrees within communities, which are common in practice. The degree-corrected stochastic block model was proposed to address this shortcoming and allows variation in node degrees within a community while preserving the overall block community structure. In this paper we establish general theory for checking consistency of community detection under the degree-corrected stochastic block model and compare several community detection criteria under both the standard and the degree-corrected models. We show which criteria are consistent under which models and constraints, as well as compare their relative performance in practice. We find that methods based on the degree-corrected block model, which includes the standard block model as a special case, are consistent under a wider class of models and that modularity-type methods require parameter constraints for consistency, whereas likelihood-based methods do not. On the other hand, in practice, the degree correction involves estimating many more parameters, and empirically we find it is only worth doing if the node degrees within communities are indeed highly variable. We illustrate the methods on simulated networks and on a network of political blogs.

Published in at http://dx.doi.org/10.1214/12-AOS1036 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org). With Corrections

References in corpus (6)

• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Stochastic blockmodels and community structure in networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Mixture models and exploratory analysis in networks
• Modeling homophily and stochastic equivalence in symmetric relational data

Cited by in corpus (53)

• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Consistency of spectral clustering in stochastic block models
• Pseudo-likelihood methods for community detection in large sparse networks
• Dynamic stochastic blockmodels for time-evolving social networks
• Parsimonious module inference in large networks
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Rate-optimal graphon estimation
• Coauthorship and Citation Networks for Statisticians
• Network histograms and universality of blockmodel approximation
• A goodness-of-fit test for stochastic block models
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• Community detection in multi-relational data with restricted multi-layer stochastic blockmodel
• Asymptotics in directed exponential random graph models with an increasing bi-degree sequence
• A Survey on Theoretical Advances of Community Detection in Networks
• Co-clustering separately exchangeable network data
• One-Hot Graph Encoder Embedding
• Community detection in networks using graph embeddings
• Dynamic stochastic blockmodels: Statistical models for time-evolving networks
• Detecting Dynamic Community Structure in Functional Brain Networks Across Individuals: A Multilayer Approach
• A testing based extraction algorithm for identifying significant communities in networks
• Asymptotic normality in the maximum entropy models on graphs with an increasing number of parameters
• Controlling epidemics through optimal allocation of test kits and vaccine doses across networks
• Cross-validation estimate of the number of clusters in a network
• Estimating Causal Peer Influence in Homophilous Social Networks by Inferring Latent Locations
• Universal Phase Transition in Community Detectability under a Stochastic Block Model
• Demarcating Geographic Regions using Community Detection in Commuting Networks with Significant Self-Loops
• Adapting Stochastic Block Models to Power-Law Degree Distributions
• Social Network Mediation Analysis: a Latent Space Approach
• Improvements on SCORE, Especially for Weak Signals
• Consistent structure estimation of exponential-family random graph models with block structure
• Hierarchical clustering with discrete latent variable models and the integrated classification likelihood
• Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities
• Discovering Communication Pattern Shifts in Large-Scale Labeled Networks using Encoder Embedding and Vertex Dynamics
• Graph Encoder Ensemble for Simultaneous Vertex Embedding and Community Detection
• Pairwise Covariates-adjusted Block Model for Community Detection
• Inference of Edge Correlations in Multilayer Networks
• A Simple Spectral Failure Mode for Graph Convolutional Networks
• Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel
• Profile Likelihood Biclustering
• Synergistic Graph Fusion via Encoder Embedding
• A useful criterion on studying consistent estimation in community detection
• Non Parametric Statistics of Dynamic Networks with distinguishable nodes
• Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model
• Evading Community Detection via Counterfactual Neighborhood Search
• Encoder Embedding for General Graph and Node Classification
• A network community detection method with integration of data from multiple layers and node attributes
• Refined Graph Encoder Embedding via Self-Training and Latent Community Recovery
• Community detection robustness of graph neural networks
• Distributed Pseudo-Likelihood Method for Community Detection in Large-Scale Networks
• A Unified Framework for Community Detection and Model Selection in Blockmodels
• Consistent model selection for the Degree Corrected Stochastic Blockmodel
• Modeling Node Exposure for Community Detection in Networks