Phys. Rev. E 101, 042304 (2020) - Improved mutual information measure for clustering, classification, and community detection

Loading [MathJax]/extensions/MathMenu.js

Learn about our response to COVID-19, including freely available research and expanded remote access support.

Go Mobile »
Access by University of Bath Library

Improved mutual information measure for clustering, classification, and community detection

M. E. J. Newman, George T. Cantwell, and Jean-Gabriel Young

Phys. Rev. E 101, 042304 – Published 23 April 2020

Abstract

The information theoretic measure known as mutual information is widely used as a way to quantify the similarity of two different labelings or divisions of the same set of objects, such as arises, for instance, in clustering and classification problems in machine learning or community detection problems in network science. 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 derive an expression for this missing term and hence write a corrected mutual information that gives accurate results even in cases where the standard measure fails. We discuss practical implementation of the new measure and give example applications.

Received 7 August 2019
Revised 13 February 2020
Accepted 25 March 2020

DOI:https://doi.org/10.1103/PhysRevE.101.042304

©2020 American Physical Society

Physics Subject Headings (PhySH)

Community structure Information & communication theory Patterns in complex systems

Information theory Machine learning

Statistical PhysicsInterdisciplinary PhysicsGeneral PhysicsNetworks

Authors & Affiliations

M. E. J. Newman ^1,2, George T. Cantwell¹, and Jean-Gabriel Young²

¹Department of Physics, University of Michigan, Ann Arbor, Michigan 48109, USA
²Center for the Study of Complex Systems, University of Michigan, Ann Arbor, Michigan 48109, USA

Article Text

Click to Expand

References

Click to Expand

Issue

Vol. 101, Iss. 4 — April 2020

Reuse & Permissions

Physical Review A•B•C•D - 50 Years

To celebrate 50 years of enduring discoveries, APS is offering 50% off APCs for any manuscript submitted in 2020, published in any of its hybrid journals: PRL, PRA, PRB, PRC, PRD, PRE, PRApplied, PRFluids, and PRMaterials. Learn More »

Access Options

Article part of CHORUS

Ways to Access APS Journal Articles Off-Campus

Many researchers now find themselves working away from their institutions and, thus, may have trouble accessing the Physical Review journals. To address this, we have been improving access via several different mechanisms. See Off-Campus Access to Physical Review for further instructions.

APS and the Physical Review Editorial Office Continue to Support Researchers

COVID-19 has impacted many institutions and organizations around the world, disrupting the progress of research. Through this difficult time APS and the Physical Review editorial office are fully equipped and actively working to support researchers by continuing to carry out all editorial and peer-review functions and publish research in the journals as well as minimizing disruption to journal access.

We appreciate your continued effort and commitment to helping advance science, and allowing us to publish the best physics journals in the world. And we hope you, and your loved ones, are staying safe and healthy.

Images

Figure 1
(a) The number of ways of choosing $S$ $S$ strictly positive integers $b_{s}$ $b_{s}$ such that they sum to $n$ $n$ is equal to the number of ways of placing $S - 1$ $S - 1$ dividers (the vertical bars) between $n$ $n$ objects (represented by the line of gray squares), with no two dividers allowed to fall in the same place. The number of squares between each divider and the next represents the value of one of the $b_{s}$ $b_{s}$ , and trivially they sum to $n$ $n$ . Since there are $n - 1$ $n - 1$ places the dividers can go, the total number of ways of choosing the $b_{s}$ $b_{s}$ is $(\frac{n - 1}{S - 1})$ $(\binom{n - 1}{S - 1})$ . (b) The number of ways of choosing $S$ $S$ integers $b_{s}$ $b_{s}$ such that they sum to $n$ $n$ , where individual integers are now allowed to be zero (but not negative), is equal to the number of ways of placing an additional $S - 1$ $S - 1$ divider objects (the dark squares) among the $n$ $n$ lighter squares, for a total of $n + S - 1$ $n + S - 1$ squares overall. The values of the $b_{s}$ $b_{s}$ are again the numbers of squares between the dividers, which again necessarily sum to $n$ $n$ . Since two divider squares can now be adjacent, however, we can have $b_{s} = 0$ $b_{s} = 0$ , and the total number of divisions is $(\frac{n + S - 1}{S - 1})$ $(\binom{n + S - 1}{S - 1})$ .
Reuse & Permissions
Figure 2
Two divisions into communities of the “karate club” network of Zachary [21]. (a) Division found by statistical inference, maximizing the profile likelihood for the degree-corrected stochastic block model [22]. (b) Division found by maximizing modularity [23]. The accepted ground-truth division is indicated by the shaded regions. According to the standard mutual information, division (b) has the stronger similarity to the ground truth, but division (a) is more similar according to the reduced mutual information of Eq. (23).
Reuse & Permissions
Figure 3
Clustering analysis of the wine data set described in the text [25], which represents 12 measured attributes of 178 different Italian wines. (a) A three-group clustering of the data found using $k$ $k$ -means applied to a normalized version of the data. The data points are projected onto the data set's two most significant principal components, with colors representing the calculated clustering and shapes representing the ground truth. (b) A six-group clustering of the same data, again computed using $k$ $k$ -means. (c) The standard mutual information and the reduced mutual information of Eq. (23) for divisions into 2, 3, 4, 5, and 6 groups using $k$ $k$ -means. While the standard measure increases with increasing number of groups, the modified measure peaks at the correct ground-truth value of three.
Reuse & Permissions

1 of 3

Sign up to receive regular email alerts from Physical Review E

This site uses cookies. To find out more, read our Privacy Policy. I Agree