# Community Detection: Exact Recovery in Weighted Graphs

arXiv: https://arxiv.org/abs/2102.04439 · HTML: https://mlsanity.com/paper/2102.04439/

## 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 (most cited first, 15 of 15)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices](https://mlsanity.com/paper/1402.1267/) (2014)
- [Consistency Thresholds for the Planted Bisection Model](https://mlsanity.com/paper/1407.1591/) (2014)
- [On semidefinite relaxations for the block model](https://mlsanity.com/paper/1406.5647/) (2014)
- [Belief propagation, robust reconstruction and optimal recovery of block models](https://mlsanity.com/paper/1309.1380/) (2013)
- [Information Limits for Recovering a Hidden Community](https://mlsanity.com/paper/1509.07859/) (2015)
- [Community Detection via Random and Adaptive Sampling](https://mlsanity.com/paper/1402.3072/) (2014)
- [Spectral Detection in the Censored Block Model](https://mlsanity.com/paper/1502.00163/) (2015)
- [Density Evolution in the Degree-correlated Stochastic Block Model](https://mlsanity.com/paper/1509.03281/) (2015)
- [Community detection in weighted brain connectivity networks beyond the resolution limit](https://mlsanity.com/paper/1609.04316/) (2016)
- [Exponential random graph models for networks with community structure](https://mlsanity.com/paper/1305.4014/) (2013)

## Built on by (most cited first, 2 of 2)

- [Semidefinite Programming for Community Detection with Side Information](https://mlsanity.com/paper/2105.02816/) (2021)
- [Community Detection with Known, Unknown, or Partially Known Auxiliary Latent Variables](https://mlsanity.com/paper/2301.04088/) (2023)

## 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.