Improved mutual information measure for classification and community detection

M. E. J. Newman, 1, 2 George T. Cantwell, 1 and Jean Gabriel Young 2 1 Department of Physics, University of Michigan, Ann Arbor, Michigan, USA 2 Center for the Study of Complex Systems, University of Michigan, Ann Arbor, Michigan, USA 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. I. INTRODUCTION Mutual information is widely used in physics, statistics, and machine learning as a tool for comparing different labelings of a set of objects [1]. For instance, within physics it is used in statistical mechanics for comparing states of spin models [2] and particularly in network science for comparing partitions of networks into communities, mutual information being perhaps the standard measure for quantifying the performance of community detection algorithms [3, 4]: it tells us the extent to which the set of communities found by an algorithm agree with a given set of ground-truth communities. In machine learning and statistics, mutual information is similarly used in classification problems to quantify the similarity of different labelings of sets of objects [5]. For instance, we might attempt to deduce characteristics of a set of users of an online service, such as their age group or gender, and then calibrate our algorithm by using mutual information to compare our results against known characteristics of a test set of users. Imagine then that we have some set of individuals or objects, such as people, documents, email messages, or aerial photographs, among many other possibilities. Each object can be classified or labeled as belonging to one of several types, groups, or communities. People could be labeled by sex, race, or blood type for instance; documents by topic; aerial photographs by type of terrain, and so forth. Now imagine we have two different sets of labels for our objects, one inferred by some algorithm and the other assigned for instance by human experts. The mutual information of the two labelings represents the amount of information that the first labeling gives us about the second--in effect, how good the algorithm is at mimicking the human experts.