Dominant-Set Clustering: A Review

Clustering refers to the process of extracting maximally coherent groups from a set of objects using pairwise, or high-order, similarities. Traditional approaches to this problem are based on the idea of partitioning the input data into a predetermined number of classes, thereby obtaining the clusters as a by-product of the partitioning process. A radically different perspective of the problem consists in providing a formalization of the very notion of a cluster and considering the clustering process as a sequential search of structures in the data adhering to this cluster notion. In this manuscript we review one of the pioneering approaches falling in the latter class of algorithms, which has been proposed in the early 2000s and has been found since then a number of applications in different domains. It is known as dominant set clustering and provides a notion of a cluster (a.k.a. dominant set) that has intriguing links to game-theory, graph-theory and optimization theory. From the game-theoretic perspective, clusters are regarded as equilibria of non-cooperative “clustering” games; in the graph-theoretic context, it can be shown that they generalize the notion of maximal clique to edge-weighted graphs; finally, from an optimization point of view, they can be characterized in terms of solutions to a simplex-constrained, quadratic optimization problem, as well as in terms of an exquisitely combinatorial entity. Besides introducing dominant sets from a theoretical perspective, we will also focus on the related algorithmic issues by reviewing two state-of-the-art methods that are used in the literature to find dominant sets clusters, namely the Replicator Dynamics and the Infection and Immunization Dynamics. Finally, we conclude with an overview of different extensions of the dominant set framework and of applications where dominant sets have been successfully employed.