# Graph energy as a measure of community detectability in networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 57 references that are in the map.
- First posted on arXiv 8 Jan 2026.

## Builds on (most cited first, 17 of 17)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [Bayesian stochastic blockmodeling](https://mlsanity.com/paper/1705.10225/) (2017)
- [20 years of network community detection](https://mlsanity.com/paper/2208.00111/) (2022)
- [The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness](https://mlsanity.com/paper/1702.00467/) (2017)
- [Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity](https://mlsanity.com/paper/1403.5787/) (2014)
- [Complex networks with complex weights](https://mlsanity.com/paper/2212.06257/) (2022)
- [Detectability thresholds and optimal algorithms for community structure in dynamic networks](https://mlsanity.com/paper/1506.06179/) (2015)
- [Sharp Phase Transitions in Estimation with Low-Degree Polynomials](https://mlsanity.com/paper/2502.14407/) (2025)
- [Spectral Embedding Norm: Looking Deep into the Spectrum of the Graph Laplacian](https://mlsanity.com/paper/1810.10695/) (2018)
- [Stochastic block models with many communities and the Kesten--Stigum bound](https://mlsanity.com/paper/2503.03047/) (2025)
- [Phase Transition for Stochastic Block Model with more than √n Communities (II)](https://mlsanity.com/paper/2511.21526/) (2025)
- [Spectra of random graphs with community structure and arbitrary degrees](https://mlsanity.com/paper/1310.0046/) (2013)
- [A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks](https://mlsanity.com/paper/1608.06196/) (2016)
- [Spectra of random networks with arbitrary degrees](https://mlsanity.com/paper/1901.02029/) (2019)

## Abstract (arXiv)

A key challenge in network science is the detection of communities, which are sets of nodes in a network that are densely connected internally but sparsely connected to the rest of the network. A fundamental result in community detection is the existence of a nontrivial threshold for community detectability on sparse graphs that are generated by the planted partition model (PPM). Below this so-called ``detectability limit'', no community-detection method can perform better than random chance. Spectral methods for community detection fail before this detectability limit because the eigenvalues corresponding to the eigenvectors that are relevant for community detection can be absorbed by the bulk of the spectrum. One can bypass the detectability problem by using special matrices, like the non-backtracking matrix, but this requires one to consider higher-dimensional matrices. In this paper, we show that the difference in graph energy between a PPM and an ErdHos--R'enyi (ER) network has a distinct transition at the detectability threshold even for the adjacency matrices of the underlying networks. The graph energy is based on the full spectrum of an adjacency matrix, so our result suggests that standard graph matrices still allow one to separate the parameter regions with detectable and undetectable communities.