Contextual Stochastic Block Model: Sharp Thresholds and Contiguity
We study community detection in the contextual stochastic block model arXiv:1807.09596 [cs.SI], arXiv:1607.02675 [stat.ME]. In arXiv:1807.09596 [cs.SI], the second author studied this problem in the setting of sparse graphs with high-dimensional node-covariates. Using the non-rigorous cavity method from statistical physics, they conjectured the sharp limits for community detection in this setting. Further, the information theoretic threshold was verified, assuming that the average degree of the observed graph is large. It is expected that the conjecture holds as soon as the average degree exceeds one, so that the graph has a giant component. We establish this conjecture, and characterize the sharp threshold for detection and weak recovery.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionmodelStochastic Block ModelSimilar Papers 제목 키워드 기반
Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
The low-degree polynomial framework has emerged as a powerful tool for providing evidence of statistical-computational gaps in high-dimensional inference. For detection problems, the standard approach bounds the low-degr…
Bayesian estimation from few samples: community detection and related problems
We propose an efficient meta-algorithm for Bayesian estimation problems that is based on low-degree polynomials, semidefinite programming, and tensor decomposition. The algorithm is inspired by recent lower bound constru…
Community DetectionStochastic Block ModelTensor DecompositionCommunity recovery in non-binary and temporal stochastic block models
This article studies the estimation of latent community memberships from pairwise interactions in a network of $N$ nodes, where the observed interactions can be of arbitrary type, including binary, categorical, and vecto…
Stochastic Block ModelTime SeriesTime Series AnalysisLow degree conjecture implies sharp computational thresholds in stochastic block model
We investigate implications of the (extended) low-degree conjecture (recently formalized in [MW23]) in the context of the symmetric stochastic block model. Assuming the conjecture holds, we establish that no polynomial-t…
Stochastic Block ModelFundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models
Multi-view data arises frequently in modern network analysis e.g. relations of multiple types among individuals in social network analysis, longitudinal measurements of interactions among observational units, annotated n…
Community DetectionStochastic Block Model