Defining quality metrics for graph clustering evaluation

Abstract

Evaluation of clustering has significant importance in various applications of expert and intelligent systems. Clusters are evaluated in terms of quality and accuracy. Measuring quality is a unsupervised approach that completely depends on edges, whereas measuring accuracy is a supervised approach that measures similarity between the real clustering and the predicted clustering. Accuracy cannot be measured for most of the real-world networks since real clustering is unavailable. Thus, it will be advantageous from the viewpoint of expert systems to develop a quality metric that can assure certain level of accuracy along with the quality of clustering. In this paper we have proposed a set of three quality metrics for graph clustering that have the ability to ensure accuracy along with the quality. The effectiveness of the metrics has been evaluated on benchmark graphs as well as on real-world networks and compared with existing metrics. Results indicate competency of the suggested metrics while dealing with accuracy, which will definitely improve the decision-making in expert and intelligent systems. We have also shown that our metrics satisfy all of the six quality-related properties. © 2016 Elsevier Ltd