# Evaluating accuracy of community detection using the relative normalized mutual information

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2015.

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

- [DIGRAC: Digraph Clustering Based on Flow Imbalance](https://mlsanity.com/paper/2106.05194/) (2021)
- [Smoothness Really Matters: A Simple Yet Effective Approach for Unsupervised Graph Domain Adaptation](https://mlsanity.com/paper/2412.11654/) (2024)
- [Normalized mutual information is a biased measure for classification and community detection](https://mlsanity.com/paper/2307.01282/) (2023)
- [Characterizing and comparing external measures for the assessment of cluster analysis and community detection](https://mlsanity.com/paper/2102.00708/) (2021)
- [Selective clustering ensemble based on kappa and F-score](https://mlsanity.com/paper/2204.11062/) (2022)
- [Mutual information and the encoding of contingency tables](https://mlsanity.com/paper/2405.05393/) (2024)
- [Multimodal Coordinated Online Behavior: Trade-offs and Strategies](https://mlsanity.com/paper/2507.12108/) (2025)

## Abstract (arXiv)

The Normalized Mutual Information (NMI) has been widely used to evaluate the accuracy of community detection algorithms. However in this article we show that the NMI is seriously affected by systematic errors due to finite size of networks, and may give a wrong estimate of performance of algorithms in some cases. We give a simple theory to the finite-size effect of NMI and test our theory numerically. Then we propose a new metric for the accuracy of community detection, namely the relative Normalized Mutual Information (rNMI), which considers statistical significance of the NMI by comparing it with the expected NMI of random partitions. Our numerical experiments show that the rNMI overcomes the finite-size effect of the NMI.