Pseudo-likelihood methods for community detection in large sparse networks

Abstract

Many algorithms have been proposed for fitting network models with communities, but most of them do not scale well to large networks, and often fail on sparse networks. Here we propose a new fast pseudo-likelihood method for fitting the stochastic block model for networks, as well as a variant that allows for an arbitrary degree distribution by conditioning on degrees. We show that the algorithms perform well under a range of settings, including on very sparse networks, and illustrate on the example of a network of political blogs. We also propose spectral clustering with perturbations, a method of independent interest, which works well on sparse networks where regular spectral clustering fails, and use it to provide an initial value for pseudo-likelihood. We prove that pseudo-likelihood provides consistent estimates of the communities under a mild condition on the starting value, for the case of a block model with two communities.

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

References in corpus (9)

• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Stochastic blockmodels and community structure in networks
• Mixture models and exploratory analysis in networks
• Matrix estimation by Universal Singular Value Thresholding
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Uncovering latent structure in valued graphs: A variational approach
• Modeling homophily and stochastic equivalence in symmetric relational data
• The method of moments and degree distributions for network models

Cited by in corpus (36)

• Spectral redemption: clustering sparse networks
• Matrix estimation by Universal Singular Value Thresholding
• A Comprehensive Survey on Community Detection with Deep Learning
• Fast community detection by SCORE
• Localization and centrality in networks
• Rate-optimal graphon estimation
• Coauthorship and Citation Networks for Statisticians
• Covariate-assisted spectral clustering
• 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
• Role of normalization in spectral clustering for stochastic blockmodels
• The geometry of kernelized spectral clustering
• A Survey on Theoretical Advances of Community Detection in Networks
• A testing based extraction algorithm for identifying significant communities in networks
• Inferring gene-gene interactions and functional modules using sparse canonical correlation analysis
• Consistency Thresholds for the Planted Bisection Model
• A divisive spectral method for network community detection
• Generative model for reciprocity and community detection in networks
• Large-scale estimation of random graph models with local dependence
• Consistent structure estimation of exponential-family random graph models with block structure
• Laplacian Eigenmaps from Sparse, Noisy Similarity Measurements
• Bayesian estimation of the latent dimension and communities in stochastic blockmodels
• Online Bayesian changepoint detection for network Poisson processes with community structure
• Pairwise Covariates-adjusted Block Model for Community Detection
• Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel
• Profile Likelihood Biclustering
• Estimating the number of communities in weighted networks
• Group fairness without demographics using social networks
• Stochastic Block Models are a Discrete Surface Tension
• Detecting User Community in Sparse Domain via Cross-Graph Pairwise Learning
• Consistency between ordering and clustering methods for graphs
• Distributed Pseudo-Likelihood Method for Community Detection in Large-Scale Networks
• On role extraction for digraphs via neighbourhood pattern similarity
• A Unified Framework for Community Detection and Model Selection in Blockmodels
• Human-Centric Community Detection in Hybrid Metaverse Networks with Integrated AI Entities
• Consistent model selection for the Degree Corrected Stochastic Blockmodel