A Survey on Theoretical Advances of Community Detection in Networks

Abstract

Real-world networks usually have community structure, that is, nodes are grouped into densely connected communities. Community detection is one of the most popular and best-studied research topics in network science and has attracted attention in many different fields, including computer science, statistics, social sciences, among others. Numerous approaches for community detection have been proposed in literature, from ad-hoc algorithms to systematic model-based approaches. The large number of available methods leads to a fundamental question: whether a certain method can provide consistent estimates of community labels. The stochastic blockmodel (SBM) and its variants provide a convenient framework for the study of such problems. This article is a survey on the recent theoretical advances of community detection. The authors review a number of community detection methods and their theoretical properties, including graph cut methods, profile likelihoods, the pseudo-likelihood method, the variational method, belief propagation, spectral clustering, and semidefinite relaxations of the SBM. The authors also briefly discuss other research topics in community detection such as robust community detection, community detection with nodal covariates and model selection, as well as suggest a few possible directions for future research.

arXiv commentWire Computational Statistics, 2017

References in corpus (38)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• Finding local community structure in networks
• Mixed membership stochastic blockmodels
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• Spectral clustering and the high-dimensional stochastic blockmodel
• Structure and inference in annotated networks
• Consistency of spectral clustering in stochastic block models
• Fast community detection by SCORE
• Consistency of community detection in networks under degree-corrected stochastic block models
• Pseudo-likelihood methods for community detection in large sparse networks
• Stochastic blockmodels with growing number of classes
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Community Detection as an Inference Problem
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Community extraction for social networks
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Covariate-assisted spectral clustering
• A goodness-of-fit test for stochastic block models
• Spectra of random graphs with arbitrary expected degrees
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Role of normalization in spectral clustering for stochastic blockmodels
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Spectra of random graphs with community structure and arbitrary degrees
• Estimating the number of communities in networks by spectral methods
• Local Network Community Detection with Continuous Optimization of Conductance and Weighted Kernel K-Means
• Density Evolution in the Degree-correlated Stochastic Block Model
• Impact of regularization on Spectral Clustering
• Community Detection in Degree-Corrected Block Models
• Covariate Regularized Community Detection in Sparse Graphs
• Corrected Bayesian information criterion for stochastic block models

Cited by in corpus (8)

• Graph Generators: State of the Art and Open Challenges
• Profile Likelihood Biclustering
• Spectral clustering via adaptive layer aggregation for multi-layer networks
• Consistent polynomial-time unseeded graph matching for Lipschitz graphons
• Fast Network Community Detection with Profile-Pseudo Likelihood Methods
• Identifiability and consistency of network inference using the hub model and variants
• Neural Stochastic Block Model & Scalable Community-Based Graph Learning
• CALF-SBM: A Covariate-Assisted Latent Factor Stochastic Block Model