Community Detection: Exact Recovery in Weighted Graphs
Not on the map. Why?
Abstract (arXiv)
In community detection, the exact recovery of communities (clusters) has been mainly investigated under the general stochastic block model with edges drawn from Bernoulli distributions. This paper considers the exact recovery of communities in a complete graph in which the graph edges are drawn from either a set of Gaussian distributions with community-dependent means and variances, or a set of exponential distributions with community-dependent means. For each case, we introduce a new semi-metric that describes sufficient and necessary conditions of exact recovery. The necessary and sufficient conditions are asymptotically tight. The analysis is also extended to incomplete, fully connected weighted graphs.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 15 of its 31 references that are in the map. First posted on arXiv 8 Feb 2021.
Builds on
15 of 31 references.
References · 15
- 2017Community Detection and Stochastic Block Modelscited by 319
- 2014Exact Recovery in the Stochastic Block Modelcited by 78
- 2013Community detection thresholds and the weak Ramanujan propertycited by 47
- 2013A Proof Of The Block Model Threshold Conjecturecited by 36
- 2014Achieving Exact Cluster Recovery Threshold via Semidefinite Programmingcited by 33
- 2014Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatricescited by 29
- 2014Consistency Thresholds for the Planted Bisection Modelcited by 24
- 2014On semidefinite relaxations for the block modelcited by 22
- 2013Belief propagation, robust reconstruction and optimal recovery of block modelscited by 18
- 2015Information Limits for Recovering a Hidden Communitycited by 18
- 2014Community Detection via Random and Adaptive Samplingcited by 7
- 2015Spectral Detection in the Censored Block Modelcited by 5
Built on by
Citing papers per year: 2021: 1; 2022: 0; 2023: 1.
2 papers.