Computational and statistical thresholds in multi-layer stochastic block models

DOI10.1214/24-AOS2441MaRDI QIDQ6656627zbMATH OpenFDO

Authors Jing Lei, Anru R. Zhang, Zihan Zhu

Publication date 3 January 2025

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

Full work available at URL https://doi.org/10.1214/24-AOS2441

zbMATH Keywords

community detection and recoverycomputational barrierlow-degree polynomial hardnessmultilayer network

Mathematics Subject Classification ID

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

Cites work

• A nearly tight sum-of-squares lower bound for the planted clique problem
• A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging
• A survey of statistical network models
• Achieving optimal misclassification proportion in stochastic block models
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Clustering With Multi-Layer Graphs: A Spectral Perspective
• Community detection and stochastic block models: recent developments
• Computational barriers in minimax submatrix detection
• Computational barriers to estimation from low-degree polynomials
• Computationally efficient sparse clustering
• Consistency of spectral clustering in stochastic block models
• Consistent community detection in multi-layer network data
• Dynamic network models and graphon estimation
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit
• Exact Recovery in the Stochastic Block Model
• Global and individualized community detection in inhomogeneous multilayer networks
• Global spectral clustering in dynamic networks
• HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
• scientific article; zbMATH DE number 7625156 (Why is no real title available?)
• scientific article; zbMATH DE number 7650426 (Why is no real title available?)
• Introduction to nonparametric estimation
• Minimax rates of community detection in stochastic block models
• Network Models for Data Science
• Networks. An introduction.
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Optimal detection of sparse principal components in high dimension
• Optimal estimation and computational limit of low-rank Gaussian mixtures
• Spectral and matrix factorization methods for consistent community detection in multi-layer networks
• Statistical analysis of network data. Methods and models
• Statistical clustering of temporal networks through a dynamic stochastic block model
• Subexponential-time algorithms for sparse PCA
• Tensor clustering with planted structures: statistical optimality and computational limits
• Tensor SVD: Statistical and Computational Limits
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property

Cited in

(5)

• Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models
• Randomized spectral clustering for large-scale multi-layer networks
• On Optimal Tracking of Structural Changes in Time-Varying Networks
• Dynamic clustering for heterophilic stochastic block models with time-varying node memberships
• Detection and estimation of vertexwise latent position shifts across networks

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

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