Normalized Mutual Information to evaluate overlapping community finding algorithms

2011/10/11 by McDaid, Aaron F., Greene, Derek, Hurley, Neil · 7 citations
#Data Analysis #FOS: Computer and information sciences #FOS: Physical sciences #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI) #Statistics and Probability (physics.data-an)

paper · doi:10.48550/arxiv.1110.2515

Abstract

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].

Cited by

• Topological Federated Clustering via Gravitational Potential Fields under Local Differential Privacy
• Interactive Hypergraph Visual Analytics for Exploring Large and Complex Image Collections
• OS-HGAdapter: Open Semantic Hypergraph Adapter for Large Language Models Assisted Entropy-Enhanced Image-Text Alignment
• Measuring Data Quality for Project Lighthouse
• Evading Overlapping Community Detection via Proxy Node Injection
• scI2CL: Effectively Integrating Single-cell Multi-omics by Intra- and Inter-omics Contrastive Learning
• Hybrid Topic-Semantic Labeling and Graph Embeddings for Unsupervised Legal Document Clustering

Related

• Normalized mutual information is a biased measure for classification and community detection
• Evaluation of Community Detection Methods
• Resampled Mutual Information for Clustering and Community Detection
• Pairwise Adjusted Mutual Information
• Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach