Pseudo-likelihood methods for community detection in large sparse networks

DOI10.1214/13-AOS1138MaRDI QIDQ90059zbMATH OpenOpenAlexWikidataFDO

Authors Elizaveta Levina, Arash A. Amini, Aiyou Chen, P. J. Bickel

Publication date 1 August 2013

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

Full work available at URL https://arxiv.org/abs/1207.2340, https://projecteuclid.org/euclid.aos/1382547514

zbMATH Keywords

pseudo-likelihoodcommunity detectionnetworks

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Asymptotic properties of nonparametric inference (62G20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Multivariate analysis (62H99)

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.

Recommendations

• A spectral method for community detection in moderately sparse degree-corrected stochastic block models
• Spectral clustering and the high-dimensional stochastic blockmodel
• Consistency of spectral clustering in stochastic block models
• Stochastic blockmodels with a growing number of classes
• Fused community detection

Cites work

• scientific article; zbMATH DE number 3513115 (Why is no real title available?)
• scientific article; zbMATH DE number 3626409 (Why is no real title available?)
• scientific article; zbMATH DE number 2100602 (Why is no real title available?)
• A nonparametric view of network models and Newman–Girvan and other modularities
• An Exponential Family of Probability Distributions for Directed Graphs
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Classification and estimation in the stochastic blockmodel based on the empirical degrees
• Community structure in social and biological networks
• Consistency of community detection in networks under degree-corrected stochastic block models
• Consistency of maximum-likelihood and variational estimators in the stochastic block model
• Estimation and Prediction for Stochastic Blockstructures
• Estimation and prediction for stochastic blockmodels for graphs with latent block structure
• Mixed membership stochastic blockmodels
• Mixture models and exploratory analysis in networks
• On the Distribution of the Number of Successes in Independent Trials
• On the convergence properties of the EM algorithm
• On the distribution of the number of successes in independent trials
• Pseudo-likelihood methods for community detection in large sparse networks
• Spectral clustering and the high-dimensional stochastic blockmodel
• Stochastic Blockmodels for Directed Graphs
• The method of moments and degree distributions for network models
• Uncovering latent structure in valued graphs: a variational approach

Cited in

(only showing first 100 items - show all)

• Model-based clustering of multiple networks with a hierarchical algorithm
• Community detection by \(L_{0}\)-penalized graph Laplacian
• Convexified modularity maximization for degree-corrected stochastic block models
• Multiresolution Network Models
• Model-based clustering of time-evolving networks through temporal exponential-family random graph models
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• Pseudo-likelihood methods for community detection in large sparse networks
• Fusing data depth with complex networks: community detection with prior information
• Community detection via an efficient nonconvex optimization approach based on modularity
• Large-scale estimation of random graph models with local dependence
• scientific article; zbMATH DE number 7370586 (Why is no real title available?)
• scientific article; zbMATH DE number 7626732 (Why is no real title available?)
• Testing community structure for hypergraphs
• Network quantile autoregression
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Testing for association in multiview network data
• Fast Network Community Detection With Profile-Pseudo Likelihood Methods
• Fast community detection by SCORE
• Improvements on SCORE, especially for weak signals
• Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
• Identifying Community Structures from Network Data via Maximum Likelihood Methods
• Consistency of spectral clustering in stochastic block models
• Matrix estimation by universal singular value thresholding
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Extended stochastic block models with application to criminal networks
• Consistent structure estimation of exponential-family random graph models with block structure
• Profile likelihood biclustering
• On semidefinite relaxations for the block model
• Submatrix localization via message passing
• Optimization via low-rank approximation for community detection in networks
• Stochastic block models are a discrete surface tension
• Estimating the number of communities by spectral methods
• A likelihood-ratio type test for stochastic block models with bounded degrees
• Network inference from temporally dependent grouped observations
• Maximum likelihood estimation of sparse networks with missing observations
• The geometry of kernelized spectral clustering
• Rate-optimal graphon estimation
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Additive and multiplicative effects network models
• Network cross-validation for determining the number of communities in network data
• Likelihood Inference for Large Scale Stochastic Blockmodels With Covariates Based on a Divide-and-Conquer Parallelizable Algorithm With Communication
• Impact of regularization on spectral clustering
• A semiparametric Bayesian approach to epidemics, with application to the spread of the coronavirus MERS in South Korea in 2015
• Review on statistical methods for gene network reconstruction using expression data
• Bayesian estimation of the latent dimension and communities in stochastic blockmodels
• nett
• Consistent nonparametric estimation for heavy-tailed sparse graphs
• Probabilistic Community Detection With Unknown Number of Communities
• Efficient discovery of overlapping communities in massive networks
• Nonreconstruction of high-dimensional stochastic block model with bounded degree
• Network vector autoregression with individual effects
• A review of dynamic network models with latent variables
• A testing based extraction algorithm for identifying significant communities in networks
• The geometry of continuous latent space models for network data
• Core-periphery structure in networks: a statistical exposition
• Role of normalization in spectral clustering for stochastic blockmodels
• Covariate regularized community detection in sparse graphs
• Community detection in degree-corrected block models
• Community detection in sparse networks via Grothendieck's inequality
• scientific article; zbMATH DE number 7307464 (Why is no real title available?)
• randnet
• Optimal bipartite network clustering
• Detecting overlapping communities in networks using spectral methods
• A review on spectral clustering and stochastic block models
• Corrected Bayesian information criterion for stochastic block models
• Hierarchical Community Detection by Recursive Partitioning
• Estimating a network from multiple noisy realizations
• A divisive spectral method for network community detection
• Fused community detection
• Spectral based hypothesis testing for community detection in complex networks
• Inferring gene-gene interactions and functional modules using sparse canonical correlation analysis
• Community Detection in Partial Correlation Network Models
• Consistent Estimation of the Number of Communities via Regularized Network Embedding
• A survey on theoretical advances of community detection in networks
• Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
• Two-sample test of stochastic block models
• Discussion of “A Tale of Two Datasets: Representativeness and Generalisability of Inference for Samples of Networks” by Pavel N. Krivitsky, Pietro Coletti, and Niel Hens
• Community detection with nodal information: likelihood and its variational approximation
• Fallacy of data-selective inference in modelling networks
• Adjacency matrix comparison for stochastic block models
• Profile-pseudo likelihood methods for community detection of multilayer stochastic block models
• Special invited paper: the SCORE normalization, especially for heterogeneous network and text data
• On the Rényi index of random graphs
• Community detection in complex networks: from statistical foundations to data science applications
• Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM)
• Rate optimal Chernoff bound and application to community detection in the stochastic block models
• Matched bipartite block model with covariates
• Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
• Large volatility matrix analysis using global and national factor models
• A distributed community detection algorithm for large scale networks under stochastic block models
• Test on stochastic block model: local smoothing and extreme value theory
• Estimating mixed-memberships using the symmetric Laplacian inverse matrix
• A multivariate to multivariate approach for voxel-wise genome-wide association analysis
• scientific article; zbMATH DE number 7626779 (Why is no real title available?)
• Hypothesis testing in sparse weighted stochastic block model
• Using Maximum Entry-Wise Deviation to Test the Goodness of Fit for Stochastic Block Models
• Group Network Hawkes Process
• Learning sparse graphons and the generalized Kesten-Stigum threshold
• A fast algorithm for integrative community detection of multi-layer networks
• Efficient split likelihood-based method for community detection of large-scale networks

This page was built for publication: Pseudo-likelihood methods for community detection in large sparse networks

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