Dominant-set clustering: A review

Samuel Rota Bulò and Marcello Pelillo

European Journal of Operational Research, 2017, vol. 262, issue 1, 1-13

Abstract: 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.

Keywords: Artificial intelligence; Clustering; Dominant sets; ESS equilibria; Maximal cliques (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717302783
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:262:y:2017:i:1:p:1-13

DOI: 10.1016/j.ejor.2017.03.056

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().