Normalized mutual information is a biased measure for classification and community detection

Abstract

Normalized mutual information is widely used as a similarity measure for evaluating the performance of clustering and classification algorithms. In this paper, we argue that results returned by the normalized mutual information are biased for two reasons: first, because they ignore the information content of the contingency table and, second, because their symmetric normalization introduces spurious dependence on algorithm output. We introduce a modified version of the mutual information that remedies both of these shortcomings. As a practical demonstration of the importance of using an unbiased measure, we perform extensive numerical tests on a basket of popular algorithms for network community detection and show that one's conclusions about which algorithm is best are significantly affected by the biases in the traditional mutual information.

22 pages, 8 figures; reworked figures

References in corpus (10)

• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• Community detection algorithms: a comparative analysis
• Community detection in networks: A user guide
• The ground truth about metadata and community detection in networks
• Phase transition in the detection of modules in sparse networks
• Evaluating accuracy of community detection using the relative normalized mutual information
• Improved mutual information measure for classification and community detection
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Mutual information and the encoding of contingency tables