Evaluating accuracy of community detection using the relative normalized mutual information

DOI10.1088/1742-5468/2015/11/P11006MaRDI QIDQ3302139zbMATH OpenOpenAlexFDO

Authors Pan Zhang

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.03844

zbMATH Keywords

community detectionnormalized mutual information (NMI)

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Statistical aspects of information-theoretic topics (62B10) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: The Normalized Mutual Information (NMI) has been widely used to evaluate the accuracy of community detection algorithms. However in this article we show that the NMI is seriously affected by systematic errors due to finite size of networks, and may give a wrong estimate of performance of algorithms in some cases. We give a simple theory to the finite-size effect of NMI and test our theory numerically. Then we propose a new metric for the accuracy of community detection, namely the relative Normalized Mutual Information (rNMI), which considers statistical significance of the NMI by comparing it with the expected NMI of random partitions. Our numerical experiments show that the rNMI overcomes the finite-size effect of the NMI.

Recommendations

• A new metric to compare local community detection algorithms in social networks using geodesic distance
• Fast and accurate determination of modularity and its effect size
• On community structure validation in real networks
• Network community detection using modularity density measures
• Mitigation of attacks and errors on community structure in complex networks

Cites work

• Estimating functions of distributions defined over spaces of unknown size
• Fast unfolding of communities in large networks
• Finite sample effects in sequence analysis
• Spectral redemption in clustering sparse networks

Cited in

(5)

• Correlation enhanced modularity-based belief propagation method for community detection in networks
• The impact of random models on clustering similarity
• Weighted community detection and data clustering using message passing
• Adaptive spectral community detection in temporal networks: a modularity optimization framework with memory and smoothing
• An improved spectral clustering community detection algorithm based on probability matrix

This page was built for publication: Evaluating accuracy of community detection using the relative normalized mutual information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3302139)