Pseudo-likelihood methods for community detection in large sparse networks

DOI10.1214/13-AOS1138zbMATH Open1277.62166arXiv1207.2340OpenAlexW3101919829WikidataQ105584325 ScholiaQ105584325MaRDI QIDQ90059FDOQ90059

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)

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.

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

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

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)

Cites Work

• 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
• Pseudo-likelihood methods for community detection in large sparse networks
• On the convergence properties of the EM algorithm
• Title not available (Why is that?)
• On the distribution of the number of successes in independent trials
• Estimation and prediction for stochastic blockmodels for graphs with latent block structure
• Consistency of community detection in networks under degree-corrected stochastic block models
• Consistency of maximum-likelihood and variational estimators in the stochastic block model
• Classification and estimation in the stochastic blockmodel based on the empirical degrees
• Mixed membership stochastic blockmodels
• On the Distribution of the Number of Successes in Independent Trials
• Mixture models and exploratory analysis in networks
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• An Exponential Family of Probability Distributions for Directed Graphs
• Title not available (Why is that?)
• Community structure in social and biological networks
• Stochastic Blockmodels for Directed Graphs
• Title not available (Why is that?)
• 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)

• Fast Network Community Detection With Profile-Pseudo Likelihood Methods
• Consistent nonparametric estimation for heavy-tailed sparse graphs
• Optimization via low-rank approximation for community detection in networks
• Community detection via an efficient nonconvex optimization approach based on modularity
• Large-scale estimation of random graph models with local dependence
• Identifying Community Structures from Network Data via Maximum Likelihood Methods
• Network cross-validation for determining the number of communities in network data
• Optimal bipartite network clustering
• Corrected Bayesian information criterion for stochastic block models
• A review on spectral clustering and stochastic block models
• Spectral based hypothesis testing for community detection in complex networks
• Multiresolution Network Models
• A likelihood-ratio type test for stochastic block models with bounded degrees
• A review of dynamic network models with latent variables
• Fusing data depth with complex networks: community detection with prior information
• Testing community structure for hypergraphs
• Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
• On semidefinite relaxations for the block model
• Review on statistical methods for gene network reconstruction using expression data
• Community detection in degree-corrected block models
• Network quantile autoregression
• Consistency of spectral clustering in stochastic block models
• Matrix estimation by universal singular value thresholding
• Covariate regularized community detection in sparse graphs
• Detecting overlapping communities in networks using spectral methods
• Convexified modularity maximization for degree-corrected stochastic block models
• Additive and multiplicative effects network models
• Efficient discovery of overlapping communities in massive networks
• Network vector autoregression with individual effects
• A semiparametric Bayesian approach to epidemics, with application to the spread of the coronavirus MERS in South Korea in 2015
• The geometry of continuous latent space models for network data
• Community detection by \(L_{0}\)-penalized graph Laplacian
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Stochastic block models are a discrete surface tension
• Impact of regularization on spectral clustering
• Bayesian estimation of the latent dimension and communities in stochastic blockmodels
• Nonreconstruction of high-dimensional stochastic block model with bounded degree
• Consistent structure estimation of exponential-family random graph models with block structure
• Profile likelihood biclustering
• Maximum likelihood estimation of sparse networks with missing observations
• Network inference from temporally dependent grouped observations
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Core-periphery structure in networks: a statistical exposition
• Testing for association in multiview network data
• The geometry of kernelized spectral clustering
• Likelihood Inference for Large Scale Stochastic Blockmodels With Covariates Based on a Divide-and-Conquer Parallelizable Algorithm With Communication
• A divisive spectral method for network community detection
• Model-based clustering of multiple networks with a hierarchical algorithm
• Pseudo-likelihood methods for community detection in large sparse networks
• A testing based extraction algorithm for identifying significant communities in networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Submatrix localization via message passing
• nett
• Estimating the number of communities by spectral methods
• Rate-optimal graphon estimation
• Probabilistic Community Detection With Unknown Number of Communities
• Role of normalization in spectral clustering for stochastic blockmodels
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• Hierarchical Community Detection by Recursive Partitioning
• Inferring gene-gene interactions and functional modules using sparse canonical correlation analysis
• Fast community detection by SCORE
• Improvements on SCORE, especially for weak signals
• Extended stochastic block models with application to criminal networks
• Title not available (Why is that?)
• randnet
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Community detection in sparse networks via Grothendieck's inequality
• Fused community detection
• Estimating a network from multiple noisy realizations
• Model-based clustering of time-evolving networks through temporal exponential-family random graph models
• Two-sample test of stochastic block models
• Title not available (Why is that?)
• A Time-Varying Network for Cryptocurrencies
• 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
• Title not available (Why is that?)
• On the Rényi index of random graphs
• Estimating mixed-memberships using the symmetric Laplacian inverse matrix
• Hypothesis testing in sparse weighted stochastic block model
• Posterior contraction rates for stochastic block models
• A practical two-sample test for weighted random graphs
• Smoothing graphons for modelling exchangeable relational data
• Learning sparse graphons and the generalized Kesten-Stigum threshold
• Asymptotic uncertainty quantification for communities in sparse planted bi-section models
• 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
• Test on stochastic block model: local smoothing and extreme value theory
• An interactive graphical method for community detection in network data
• Consistent Estimation of the Number of Communities via Regularized Network Embedding
• High-dimensional Gaussian graphical models on network-linked data
• Discussion to: ``Bayesian graphical models for modern biological applications by Y. Ni, V. Baladandayuthapani, M. Vannucci and F. C. Stingo
• An extension of the angular synchronization problem to the heterogeneous setting
• Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
• 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
• Adjacency matrix comparison for stochastic block models
• A distributed community detection algorithm for large scale networks under stochastic block models
• A multivariate to multivariate approach for voxel-wise genome-wide association analysis
• Online estimation and community detection of network point processes for event streams

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)