Evaluating accuracy of community detection using the relative normalized mutual information

Abstract

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.

comments are welcome

References in corpus (6)

• Fast unfolding of communities in large networks
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity

Cited by in corpus (14)

• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• Element-centric clustering comparison unifies overlaps and hierarchy
• Improved mutual information measure for classification and community detection
• Characterizing and comparing external measures for the assessment of cluster analysis and community detection
• A complex network approach to political analysis: application to the Brazilian Chamber of Deputies
• Link community detection through global optimization and the inverse resolution limit of partition density
• Finite size analysis of the detectability limit of the stochastic block model
• An Exact No Free Lunch Theorem for Community Detection
• Normalized mutual information is a biased measure for classification and community detection
• Metrics matter in community detection
• Mutual information and the encoding of contingency tables
• Towards a generalization of information theory for hierarchical partitions
• Phase transitions and optimal algorithms for semi-supervised classifications on graphs: from belief propagation to graph convolution network
• Efficient Detection of Communities with Significant Overlaps in Networks: Partial Community Merger Algorithm