Core estrito de um jogo de apreciação de amigos como uma solução de clustering

Abstract

Data clustering is a set of techniques aimed at analyzing a dataset and dividing it into groups such that the elements within the same group are similar to each other, while elements from different groups exhibit significant differences. One way to obtain a data clustering is by applying an approach that generates a partition of the dataset. Among the various existing approaches, some are based on concepts from cooperative game theory, a field that studies strategic interactions among rational agents and the formation of coalitions among them. In particular, hedonic games are a type of cooperative game in which players have preferences over the coalitions they may join. Several concepts from cooperative game theory have already been applied to clustering algorithms, such as the Shapley value and, in the context of hedonic games, the use of Nash-stable coalitions. However, in the context of hedonic games, there remains a gap regarding the use of the core, one of the most fundamental and robust concepts in cooperative game theory. Therefore, this work proposes two new clustering algorithms, the CEAC and CEAC++, which identify the strongly connected components of the graph associated with the game, differing in the way each player’s friends are selected. The proposed algorithms were compared with classical methods, such as k-means, hierarchical clustering, and DBSCAN. The experimental results indicated statistically significant differences according to the Friedman test, with differences observed between CEAC++ and the k-means method as well as hierarchical clustering with complete, single, and average linkage, according to the Nemenyi post hoc test, demonstrating the potential of the proposed approach.