Normalized Mutual Information to evaluate overlapping community finding algorithms

By Aaron F. McDaid, Derek Greene, Neil J. Hurley. arXiv.org, 2011

366 citations recorded by the source corpus.

Given the increasing popularity of algorithms for overlapping clustering, in particular in social network analysis, quantitative measures are needed to measure the accuracy of a method. Given a set of true clusters, and the set of clusters found by an algorithm, these sets of clusters must be compared to see how similar or different the sets are. A normalized measure is desirable in many contexts, for example assigning a value of 0 where the two sets are totally dissimilar, and 1 where they are identical. A measure based on normalized mutual information, [1], has recently become popular. We demonstrate unintuitive behaviour of this measure, and show how this can be corrected by using a more conventional normalization. We compare the results to that of other measures, such as the Omega index [2].

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/219d8ad7b424ced8844fb62fbdf3cdfb8f296b56

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Community detection in networks: A user guide (2016, methodology): “Alternatively, one could normalise by the larger of the entropies H(X) and H(Y ) (Esquivel and Rosvall, 2012; McDaid et al., 2011). and triangle inequality).”
Community Discovery in Dynamic Networks (2017, neutral): “The results reveal the extent of the problem: on a network composed of 9377 nodes and 24107 edges, constructed from a co-authorship network, the removal of a single node leads to NMIs between successive results of – respectively to each algorithm– 0.99, 0.9 and 0.75.”