  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.
