# Community detection and graph partitioning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 May 2013.

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

- [A graph representation based on fluid diffusion model for data analysis: theoretical aspects and enhanced community detection](https://mlsanity.com/paper/2112.04388/) (2021)
- [Inferences on Mixing Probabilities and Ranking in Mixed-Membership Models](https://mlsanity.com/paper/2308.14988/) (2023)
- [Exploring Heterophily in Graph-level Tasks](https://mlsanity.com/paper/2509.18893/) (2025)

## Abstract (arXiv)

Many methods have been proposed for community detection in networks. Some of the most promising are methods based on statistical inference, which rest on solid mathematical foundations and return excellent results in practice. In this paper we show that two of the most widely used inference methods can be mapped directly onto versions of the standard minimum-cut graph partitioning problem, which allows us to apply any of the many well-understood partitioning algorithms to the solution of community detection problems. We illustrate the approach by adapting the Laplacian spectral partitioning method to perform community inference, testing the resulting algorithm on a range of examples, including computer-generated and real-world networks. Both the quality of the results and the running time rival the best previous methods.