Improved mutual information measure for classification and community detection

Abstract

The information theoretic quantity known as mutual information finds wide use in classification and community detection analyses to compare two classifications of the same set of objects into groups. In the context of classification algorithms, for instance, it is often used to compare discovered classes to known ground truth and hence to quantify algorithm performance. Here we argue that the standard mutual information, as commonly defined, omits a crucial term which can become large under real-world conditions, producing results that can be substantially in error. We demonstrate how to correct this error and define a mutual information that works in all cases. We discuss practical implementation of the new measure and give some example applications.

arXiv comment12 pages, 3 figures

References in corpus (11)

• Scikit-learn: Machine Learning in Python
• Modularity and community structure in networks
• Community detection in graphs
• Cooperative Game Theory Approaches for Network Partitioning
• Comparing community structure identification
• Stochastic blockmodels and community structure in networks
• Normalized Mutual Information to evaluate overlapping community finding algorithms
• Element-centric clustering comparison unifies overlaps and hierarchy
• Evaluating accuracy of community detection using the relative normalized mutual information
• Mutual information in classical spin models
• Asymptotic enumeration of integer matrices with constant row and column sums

Cited by in corpus (14)

• A Clarified Typology of Core-Periphery Structure in Networks
• Consistency of community structure in complex networks
• Revealing consensus and dissensus between network partitions
• Characterizing and comparing external measures for the assessment of cluster analysis and community detection
• Representative community divisions of networks
• Spatial regionalization based on optimal information compression
• Network mutual information measures for graph similarity
• Normalized mutual information is a biased measure for classification and community detection
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Improved estimates for the number of non-negative integer matrices with given row and column sums
• Exact and rapid linear clustering of networks with dynamic programming
• Community Detection with the Map Equation and Infomap: Theory and Applications
• Mutual information and the encoding of contingency tables
• Towards a generalization of information theory for hierarchical partitions