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

Area of Science:

• Computer Science
• Information Theory
• Data Mining

Background:

• Normalized mutual information (NMI) is a standard metric for evaluating clustering and classification algorithms.
• Existing NMI calculations contain biases stemming from ignoring information content and symmetric normalization.

Purpose of the Study:

• To address the limitations of traditional NMI.
• To introduce a modified, unbiased mutual information measure.
• To demonstrate the impact of NMI bias on algorithm performance conclusions.

Main Methods:

• Developed a modified mutual information calculation.
• Conducted extensive numerical tests on network community detection algorithms.
• Compared results using traditional NMI versus the modified measure.

Main Results:

• Identified two key biases in traditional NMI: ignoring contingency table information and spurious dependence from symmetric normalization.
• The modified mutual information measure corrects these identified shortcomings.
• Conclusions regarding the best-performing algorithms for network community detection are significantly altered by using the unbiased measure.

Conclusions:

• Traditional NMI introduces significant biases in performance evaluation.
• The proposed modified mutual information offers a more accurate and reliable similarity measure.
• Employing an unbiased measure is crucial for drawing correct conclusions in algorithm comparison studies, particularly in network community detection.