Metrics matter in community detection

Abstract

We present a critical evaluation of normalized mutual information (NMI) as an evaluation metric for community detection. NMI exaggerates the leximin method's performance on weak communities: Does leximin, in finding the trivial singletons clustering, truly outperform eight other community detection methods? Three NMI improvements from the literature are AMI, rrNMI, and cNMI. We show equivalences under relevant random models, and for evaluating community detection, we advise one-sided AMI under the ${\mathbb{M}}_{\mathrm{all}}$ model (all partitions of $n$ nodes). This work seeks (1) to start a conversation on robust measurements, and (2) to advocate evaluations which do not give "free lunch".

References in corpus (21)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Finding community structure in very large networks
• Finding community structure in networks using the eigenvectors of matrices
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• Defining and identifying communities in networks
• Statistical Mechanics of Community Detection
• The map equation
• An information-theoretic framework for resolving community structure in complex networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• The ground truth about metadata and community detection in networks
• Evaluating accuracy of community detection using the relative normalized mutual information
• Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering
• Universality of the stochastic block model
• Average Stability is Invariant to Data Preconditioning. Implications to Exp-concave Empirical Risk Minimization
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• An Exact No Free Lunch Theorem for Community Detection
• Evaluation of Community Detection Methods

Cited by in corpus (1)

• An Exact No Free Lunch Theorem for Community Detection