Computational and statistical thresholds in multi-layer stochastic block models

DOI10.1214/24-aos2441MaRDI QIDQ6656627

Anru R. Zhang, Jing Lei, Zihan Zhu

Publication date: 3 January 2025

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

zbMATH Keywords

multilayer networkcommunity detection and recoverycomputational barrierlow-degree polynomial hardness

Mathematics Subject Classification ID

Multivariate analysis (62H99) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Unnamed Item
• Unnamed Item
• Minimax rates of community detection in stochastic block models
• Optimal detection of sparse principal components in high dimension
• Statistical analysis of network data. Methods and models
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Global and individualized community detection in inhomogeneous multilayer networks
• Tensor clustering with planted structures: statistical optimality and computational limits
• Computational barriers to estimation from low-degree polynomials
• Spectral and matrix factorization methods for consistent community detection in multi-layer networks
• A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging
• Dynamic network models and graphon estimation
• Consistency of spectral clustering in stochastic block models
• Computational barriers in minimax submatrix detection
• Exact Recovery in the Stochastic Block Model
• Community Detection and Stochastic Block Models
• Tensor SVD: Statistical and Computational Limits
• Clustering With Multi-Layer Graphs: A Spectral Perspective
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• Global spectral clustering in dynamic networks
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property
• Network Models for Data Science
• HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
• A Survey of Statistical Network Models
• Consistent community detection in multi-layer network data
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Statistical Clustering of Temporal Networks Through a Dynamic Stochastic Block Model
• Computationally efficient sparse clustering
• Introduction to nonparametric estimation
• Networks
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Optimal estimation and computational limit of low-rank Gaussian mixtures
• Subexponential-time algorithms for sparse PCA

This page was built for publication: Computational and statistical thresholds in multi-layer stochastic block models