# Evaluation of Community Detection Methods

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

## Key facts

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

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

- [DIGRAC: Digraph Clustering Based on Flow Imbalance](https://mlsanity.com/paper/2106.05194/) (2021)
- [Characterizing and comparing external measures for the assessment of cluster analysis and community detection](https://mlsanity.com/paper/2102.00708/) (2021)
- [Robust Graph Clustering via Meta Weighting for Noisy Graphs](https://mlsanity.com/paper/2311.00322/) (2023)
- [CCFC: Bridging Federated Clustering and Contrastive Learning](https://mlsanity.com/paper/2401.06634/) (2024)
- [Federated clustering with GAN-based data synthesis](https://mlsanity.com/paper/2210.16524/) (2022)
- [CCFC++: Enhancing Federated Clustering through Feature Decorrelation](https://mlsanity.com/paper/2402.12852/) (2024)
- [Selective clustering ensemble based on kappa and F-score](https://mlsanity.com/paper/2204.11062/) (2022)
- [Overcoming Bias in Community Detection Evaluation](https://mlsanity.com/paper/2102.03472/) (2021)
- [Regularized Optimal Transport for Dynamic Semi-supervised Learning](https://mlsanity.com/paper/2103.11937/) (2021)
- [Local and Global Structure Preservation Based Spectral Clustering](https://mlsanity.com/paper/2210.12778/) (2022)
- [Evolving Restricted Boltzmann Machine-Kohonen Network for Online Clustering](https://mlsanity.com/paper/2402.09167/) (2024)
- [OmniFC: Rethinking Federated Clustering via Lossless and Secure Distance Reconstruction](https://mlsanity.com/paper/2505.13071/) (2025)
- [Multimodal Coordinated Online Behavior: Trade-offs and Strategies](https://mlsanity.com/paper/2507.12108/) (2025)
- [DCMM-Transformer: Degree-Corrected Mixed-Membership Attention for Medical Imaging](https://mlsanity.com/paper/2511.12047/) (2025)

## Abstract (arXiv)

Community structures are critical towards understanding not only the network topology but also how the network functions. However, how to evaluate the quality of detected community structures is still challenging and remains unsolved. The most widely used metric, normalized mutual information (NMI), was proved to have finite size effect, and its improved form relative normalized mutual information (rNMI) has reverse finite size effect. Corrected normalized mutual information (cNMI) was thus proposed and has neither finite size effect nor reverse finite size effect. However, in this paper we show that cNMI violates the so-called proportionality assumption. In addition, NMI-type metrics have the problem of ignoring importance of small communities. Finally, they cannot be used to evaluate a single community of interest. In this paper, we map the computed community labels to the ground-truth ones through integer linear programming, then use kappa index and F-score to evaluate the detected community structures. Experimental results demonstrate the advantages of our method.