Computational and Statistical Thresholds in Multi-layer Stochastic Block Models

2023/11/13 by Jing Lei, Anru R. Zhang, Lei, Jing +3 · 2 citations
Mathematics · Physics and Astronomy · #62C20 #Complex Network Analysis Techniques #FOS: Mathematics #Opinion Dynamics and Social Influence #Statistical Methods and Bayesian Inference #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2311.07773

openalex publication_date 2023/11/13 · openalex created_date 2023/11/16 · openalex updated_date 2026/07/28

Abstract

We study the problem of community recovery and detection in multi-layer stochastic block models, focusing on the critical network density threshold for consistent community structure inference. Using a prototypical two-block model, we reveal a computational barrier for such multi-layer stochastic block models that does not exist for its single-layer counterpart: When there are no computational constraints, the density threshold depends linearly on the number of layers. However, when restricted to polynomial-time algorithms, the density threshold scales with the square root of the number of layers, assuming correctness of a low-degree polynomial hardness conjecture. Our results provide a nearly complete picture of the optimal inference in multiple-layer stochastic block models and partially settle the open question in Lei and Lin (2022) regarding the optimality of the bias-adjusted spectral method.

Cited by

• A functional tensor model for dynamic multilayer networks with common invariant subspaces and the RKHS estimation
• Perfect Clustering in Very Sparse Diverse Multiplex Networks

Related

• Community Detection and Stochastic Block Models
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Phase Transition for Stochastic Block Model with more than √(n) Communities (II)
• How Robust are Reconstruction Thresholds for Community Detection?
• Limit Results for Estimation of Connectivity Matrix in Multi-layer Stochastic Block Models