COMPUTATIONAL AND STATISTICAL THRESHOLDS IN MULTI-LAYER STOCHASTIC BLOCK MODELS

• 成果类型: Article
• 署名作者: Lei, Jing; Zhang, Anru R.; Zhu, Zihan
• 署名单位: Carnegie Mellon University; Duke University; University of Pennsylvania
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/24-AOS2441
• 发表日期: 2024
• 页码: 2431-2455
• 关键词: consistent community detection; blockmodels; networks; barriers

摘要

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 multilayer 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 (J. Amer. Statist. Assoc. 118 (2023) 2433-2445) regarding the optimality of the bias-adjusted spectral method.