Exploring the Limitations of Quality Metrics in Detecting and Evaluating Community Structures

Document Type: Original Article

Authors

Department of Computer Science Yazd University, Yazd, Iran

Abstract

The discovery and analysis of community structures in networks has attracted increasing attention in recent years. However there are some well-known quality metrics for detecting and evaluating communities, each of them has its own limitations. In this paper, we first deeply discuss these limitations for community detection and evaluation based on the definitions and formulations of these quality metrics. Then, we perform some experiments on the artificial and real-world networks to demonstrate these limitations. Analyzed quality metrics in this paper include modularity, performance, coverage, normalized mutual information (NMI), conductance, internal density, triangle participation ratio and cut ratio. Comparing with previous works, we go through the limitations of modularity with much more accurate details. Moreover, for the first time, we present some limitations of NMI.  In addition, however it is known that performance has tendency to get high values in large graphs, we explore this limitation by its formulation and discuss several specific cases in which performance even on small graphs gets high scores

Keywords

Main Subjects