A corrected normalized mutual information for performance evaluation of community detection

Normalized mutual information (NMI) is a widely used metric for performance evaluation of community detection methods, recently proven to be affected by finite size effects. To overcome this issue, a metric called relative normalized mutual information (rNMI) has been proposed. However, we show here that rNMI is still a biased metric and may lead, under given circumstances, to erroneous conclusions. The bias is an effect of the so-called reverse finite size effect. We discuss different strategies to address this issue, and then propose a new metric, the corrected normalized mutual information (cNMI), symmetric and well normalized, in the form of empirical calculation and closed-form expression. The experiments show that cNMI not only removes the finite size effect of NMI but also the reverse finite size effect of rNMI, and is hence more suitable for performance evaluation of community detection methods and for other approaches typical of the more general clustering context.