# An Exact No Free Lunch Theorem for Community Detection

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Mar 2019.

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

- [Image Clustering Conditioned on Text Criteria](https://mlsanity.com/paper/2310.18297/) (2023)
- [Bayesian Detection of Mesoscale Structures in Pathway Data on Graphs](https://mlsanity.com/paper/2301.11120/) (2023)

## Abstract (arXiv)

A precondition for a No Free Lunch theorem is evaluation with a loss function which does not assume a priori superiority of some outputs over others. A previous result for community detection by Peel et al. (2017) relies on a mismatch between the loss function and the problem domain. The loss function computes an expectation over only a subset of the universe of possible outputs; thus, it is only asymptotically appropriate with respect to the problem size. By using the correct random model for the problem domain, we provide a stronger, exact No Free Lunch theorem for community detection. The claim generalizes to other set-partitioning tasks including core/periphery separation, k-clustering, and graph partitioning. Finally, we review the literature of proposed evaluation functions and identify functions which (perhaps with slight modifications) are compatible with an exact No Free Lunch theorem.