# Evaluating Overfit and Underfit in Models of Network Community Structure

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2018.

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

- [Disentangling homophily, community structure and triadic closure in networks](https://mlsanity.com/paper/2101.02510/) (2021)
- [Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths](https://mlsanity.com/paper/2112.00183/) (2021)
- [Few-Sample Traffic Prediction with Graph Networks using Locale as Relational Inductive Biases](https://mlsanity.com/paper/2203.03965/) (2022)
- [Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection](https://mlsanity.com/paper/2210.09186/) (2022)
- [Exact and rapid linear clustering of networks with dynamic programming](https://mlsanity.com/paper/2301.10403/) (2023)
- [The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networks](https://mlsanity.com/paper/2310.01144/) (2023)
- [Systematic assessment of the quality of fit of the stochastic block model for empirical networks](https://mlsanity.com/paper/2201.01658/) (2022)
- [Machine Unlearning in Contrastive Learning](https://mlsanity.com/paper/2405.07317/) (2024)
- [MDL-Pool: Adaptive Multilevel Graph Pooling Based on Minimum Description Length](https://mlsanity.com/paper/2409.10263/) (2024)
- [Chordless cycle filtrations for dimensionality detection in complex networks via topological data analysis](https://mlsanity.com/paper/2509.08350/) (2025)
- [Overcoming Bias in Community Detection Evaluation](https://mlsanity.com/paper/2102.03472/) (2021)
- [Opportunities and challenges in partitioning the graph measure space of real-world networks](https://mlsanity.com/paper/2106.10753/) (2021)
- [Applied Machine Learning Methods with Long-Short Term Memory Based Recurrent Neural Networks for Multivariate Temperature Prediction](https://mlsanity.com/paper/2503.06278/) (2025)
- [Meta-learning optimizes predictions of missing links in real-world networks](https://mlsanity.com/paper/2508.09069/) (2025)
- [Learning Multi-Order Block Structure in Higher-Order Networks](https://mlsanity.com/paper/2511.21350/) (2025)
- [ERICA: Quantifying Replicability of Cluster Analysis](https://mlsanity.com/paper/2606.00302/) (2026)
- [Code evolution for link prediction in complex networks](https://mlsanity.com/paper/2606.26132/) (2026)

## Abstract (arXiv)

A common data mining task on networks is community detection, which seeks an unsupervised decomposition of a network into structural groups based on statistical regularities in the network's connectivity. Although many methods exist, the No Free Lunch theorem for community detection implies that each makes some kind of tradeoff, and no algorithm can be optimal on all inputs. Thus, different algorithms will over or underfit on different inputs, finding more, fewer, or just different communities than is optimal, and evaluation methods that use a metadata partition as a ground truth will produce misleading conclusions about general accuracy. Here, we present a broad evaluation of over and underfitting in community detection, comparing the behavior of 16 state-of-the-art community detection algorithms on a novel and structurally diverse corpus of 406 real-world networks. We find that (i) algorithms vary widely both in the number of communities they find and in their corresponding composition, given the same input, (ii) algorithms can be clustered into distinct high-level groups based on similarities of their outputs on real-world networks, and (iii) these differences induce wide variation in accuracy on link prediction and link description tasks. We introduce a new diagnostic for evaluating overfitting and underfitting in practice, and use it to roughly divide community detection methods into general and specialized learning algorithms. Across methods and inputs, Bayesian techniques based on the stochastic block model and a minimum description length approach to regularization represent the best general learning approach, but can be outperformed under specific circumstances. These results introduce both a theoretically principled approach to evaluate over and underfitting in models of network community structure and a realistic benchmark by which new methods may be evaluated and compared.