Fundamental limits of community detection from multi-view data: Multi-layer, dynamic and partially labeled block models
Xiaodong Yang, Buyu Lin, Subhabrata Sen
The Annals of Statistics · 2025 · Volume 53 · Issue 6
Abstract
Multi-view data arises frequently in modern network analysis for example, relations of multiple types among individuals in social network analysis, longitudinal measurements of interactions among observational units, annotated networks with noisy partial labeling of vertices etc. We study community detection in these disparate settings via a unified theoretical framework, and investigate the fundamental thresholds for community recovery. We characterize the mutual information between the data and the latent parameters, provided the degrees are sufficiently large. Based on this general result, (i) we derive a sharp threshold for community detection in an inhomogeneous multi-layer block model (Ann. Statist. 50 (2022) 2664–2693), (ii) characterize a sharp threshold for weak recovery in a dynamic stochastic block model (J. R. Stat. Soc. Ser. B. Stat. Methodol. 79 (2017) 1119–1141), and (iii) identify the limiting mutual information in an unbalanced partially labeled block model. Finally, we introduce iterative algorithms based on Approximate Message Passing for community detection in these problems.
Keywords
60C05, 62F15, 94A16, dynamical networks, multi-layer networks, Stochastic block model, weak recovery
Enable JavaScript for citation tools and additional paper interactions.