Avaliação da qualidade de agrupamentos em grafos

Abstract

The process of discovering groups of similar, connected vertices in a graph, known as graph clustering, has interesting applications in several scenarios, such as biology, marketing and recommendation systems. A major challenge concerning this problem is the evaluation of cluster quality, which is used to measure the effectiveness of clusteringalgorithms. Many quality metrics for graph cluster evaluation exist, but there is no consensus on which ones are best suited for this task, and most authors in the literature just assume that a chosen metric is good enough, with little or no interest in evaluating the strength of such claims.To better understand the effectiveness of the most popular cluster quality metrics presented in the literature, we studied them indifferent scenarios. We discovered that they present strong biases and structural inconsistencies that cause the quality of their results to be, at least, doubtful. Our studies demonstrated that, while in general thosepopular quality metrics do a good job evaluating the external sparsity between clusters, they do poorly when evaluating their internal density, ignoring essential information, such as the cluster's vertex count, or having its internal density ignored in practice because of computational costs. With that in mind, we proposed a new method for evaluating the internal density of a given cluster, one that not only uses more complete information to evaluate that density, but also takes into consideration structural characteristics of the original graph. With this proposed method, the internal density of a cluster is evaluated in terms of the expected density of similar clusters in that same graph. That is in contrastto the traditional quality metrics available, where clusters from different graphs are compared by the same standards, a behavior that penalizes naturally sparser graphs. Then, we proposed a new quality metric for graph clusters, combining our metric for internal quality evaluation and Conductance, a popularly used metric for external sparsity evaluation. This way, the proposed metric evaluates the two main structuralcharacteristics expected from well formed clusters. Our experiments showed that the proposed metric is capable of correctly penalizing badly formed clusters that were highly ranked by other quality metrics from the literature, while still awarding high scores for good ones.