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

DOI10.1214/12-AOS1036zbMATH Open1257.62095arXiv1110.3854OpenAlexW3103168877MaRDI QIDQ1940773FDOQ1940773

Yunpeng Zhao, Elizaveta Levina, Ji Zhu

Publication date: 7 March 2013

Published in: The Annals of Statistics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1110.3854

Mathematics Subject Classification ID

Asymptotic properties of nonparametric inference (62G20) Neural nets and related approaches to inference from stochastic processes (62M45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A nonparametric view of network models and Newman–Girvan and other modularities
• Estimation and Prediction for Stochastic Blockstructures
• Spectral clustering and the high-dimensional stochastic blockmodel
• A Survey of Statistical Network Models
• Estimation and prediction for stochastic blockmodels for graphs with latent block structure
• Consistency of community detection in networks under degree-corrected stochastic block models
• Mixed membership stochastic blockmodels
• Mixture models and exploratory analysis in networks
• Community structure in social and biological networks
• Stochastic Blockmodels for Directed Graphs
• Generalized, linear, and mixed models
• Stochastic blockmodels with a growing number of classes
• Networks
• Finding Planted Partitions in Random Graphs with General Degree Distributions

Cited In (only showing first 100 items - show all)

• Fast Network Community Detection With Profile-Pseudo Likelihood Methods
• Directed Community Detection With Network Embedding
• Optimization via low-rank approximation for community detection in networks
• Detecting structural changes in longitudinal network data
• Consistency of community detection in networks under degree-corrected stochastic block models
• Co-clustering separately exchangeable network data
• A likelihood-ratio type test for stochastic block models with bounded degrees
• A review of dynamic network models with latent variables
• Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
• On semidefinite relaxations for the block model
• Community detection in degree-corrected block models
• Consistency of spectral clustering in stochastic block models
• Consistency of modularity clustering on random geometric graphs
• Network linear discriminant analysis
• Convexified modularity maximization for degree-corrected stochastic block models
• Bayesian community detection
• Hierarchical clustering with discrete latent variable models and the integrated classification likelihood
• Additive and multiplicative effects network models
• Network vector autoregression with individual effects
• Statistical inference for continuous‐time Markov processes with block structure based on discrete‐time network data
• Testing degree corrections in stochastic block models
• Community detection by \(L_{0}\)-penalized graph Laplacian
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Dynamics of an SIS network model with a periodic infection rate
• Consistent structure estimation of exponential-family random graph models with block structure
• Profile likelihood biclustering
• Dynamic stochastic block models: parameter estimation and detection of changes in community structure
• Bayesian degree-corrected stochastic blockmodels for community detection
• Correction to the proof of consistency of community detection
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Title not available (Why is that?)
• Core-periphery structure in networks: a statistical exposition
• Identifiability and parameter estimation of the overlapped stochastic co-block model
• Mixed membership stochastic blockmodels for heterogeneous networks
• Network representation using graph root distributions
• Asymptotic in undirected random graph models with a noisy degree sequence
• Nonparametric statistics of dynamic networks with distinguishable nodes
• Directed weighted random graphs with an increasing bi-degree sequence
• A spectral algorithm with additive clustering for the recovery of overlapping communities in networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotic normality in the maximum entropy models on graphs with an increasing number of parameters
• Community detection with dependent connectivity
• Pseudo-likelihood methods for community detection in large sparse networks
• A testing based extraction algorithm for identifying significant communities in networks
• Optimal Bipartite Network Clustering
• Asymptotics in directed exponential random graph models with an increasing bi-degree sequence
• Grouped Network Vector Autoregression
• Title not available (Why is that?)
• Corrected Bayesian Information Criterion for Stochastic Block Models
• Factor Models for High-Dimensional Tensor Time Series
• Network Cross-Validation for Determining the Number of Communities in Network Data
• Rate-optimal graphon estimation
• Probabilistic Community Detection With Unknown Number of Communities
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Optimal Estimation of the Number of Network Communities
• Detecting Overlapping Communities in Networks Using Spectral Methods
• Sparse Graphs Using Exchangeable Random Measures
• Spectral clustering in the dynamic stochastic block model
• Hierarchical Community Detection by Recursive Partitioning
• Fast community detection by SCORE
• Improvements on SCORE, Especially for Weak Signals
• A goodness-of-fit test for stochastic block models
• Title not available (Why is that?)
• Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models
• A note on asymptotic distributions in maximum entropy models for networks
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Asymptotic distribution in directed finite weighted random graphs with an increasing bi-degree sequence
• Social network mediation analysis: a latent space approach
• Oriented and degree-generated block models: generating and inferring communities with inhomogeneous degree distributions
• A Time-Varying Network for Cryptocurrencies
• Universal rank inference via residual subsampling with application to large networks
• Consistent model selection for the degree corrected stochastic blockmodel
• A spectral based goodness-of-fit test for stochastic block models
• A survey on theoretical advances of community detection in networks
• Synergistic graph fusion via encoder embedding
• Stock co-jump networks
• Testing community structure for hypergraphs
• Title not available (Why is that?)
• Asymptotic in the ordered networks with a noisy degree sequence
• Null models and community detection in multi-layer networks
• Scalable estimation of epidemic thresholds via node sampling
• Affiliation weighted networks with a differentially private degree sequence
• Estimating mixed-memberships using the symmetric Laplacian inverse matrix
• Hypothesis testing in sparse weighted stochastic block model
• Posterior contraction rates for stochastic block models
• Smoothing graphons for modelling exchangeable relational data
• Edgeworth expansions for network moments
• Bootstrap inference for network vector autoregression in large-scale social network
• A Block Model for Node Popularity in Networks with Community Structure
• A Bayesian State-Space Approach to Mapping Directional Brain Networks
• Estimating Causal Peer Influence in Homophilous Social Networks by Inferring Latent Locations
• Learning sparse graphons and the generalized Kesten-Stigum threshold
• Community detection in complex networks: from statistical foundations to data science applications
• Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
• A new method for quantifying network cyclic structure to improve community detection
• Extracting brain disease‐related connectome subgraphs by adaptive dense subgraph discovery
• Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
• Title not available (Why is that?)

Uses Software

• igraph
• Tabu search

This page was built for publication: Consistency of community detection in networks under degree-corrected stochastic block models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1940773)