Mutual information and the encoding of contingency tables

Abstract

Mutual information is commonly used as a measure of similarity between competing labelings of a given set of objects, for example to quantify performance in classification and community detection tasks. As argued recently, however, the mutual information as conventionally defined can return biased results because it neglects the information cost of the so-called contingency table, a crucial component of the similarity calculation. In principle the bias can be rectified by subtracting the appropriate information cost, leading to the modified measure known as the reduced mutual information, but in practice one can only ever compute an upper bound on this information cost, and the value of the reduced mutual information depends crucially on how good a bound is established. In this paper we describe an improved method for encoding contingency tables that gives a substantially better bound in typical use cases, and approaches the ideal value in the common case where the labelings are closely similar, as we demonstrate with extensive numerical results.

18 pages, 9 figures

References in corpus (20)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Finding community structure in very large networks
• From Louvain to Leiden: guaranteeing well-connected communities
• Uncovering the overlapping community structure of complex networks in nature and society
• 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
• Resolution limit in community detection
• Comparing community structure identification
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Self-similar community structure in organisations
• Modularity from Fluctuations in Random Graphs and Complex Networks
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Evaluating accuracy of community detection using the relative normalized mutual information
• Improved mutual information measure for classification and community detection
• Spatial regionalization based on optimal information compression
• Improved estimates for the number of non-negative integer matrices with given row and column sums

Cited by in corpus (1)

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