IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v262y2017i1p1-13.html
   My bibliography  Save this article

Dominant-set clustering: A review

Author

Listed:
  • Rota Bulò, Samuel
  • Pelillo, Marcello

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.

Suggested Citation

  • Rota Bulò, Samuel & Pelillo, Marcello, 2017. "Dominant-set clustering: A review," European Journal of Operational Research, Elsevier, vol. 262(1), pages 1-13.
  • Handle: RePEc:eee:ejores:v:262:y:2017:i:1:p:1-13
    DOI: 10.1016/j.ejor.2017.03.056
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717302783
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2017.03.056?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Nisan,Noam & Roughgarden,Tim & Tardos,Eva & Vazirani,Vijay V. (ed.), 2007. "Algorithmic Game Theory," Cambridge Books, Cambridge University Press, number 9780521872829, October.
    2. Benati, Stefano & Puerto, Justo & Rodríguez-Chía, Antonio M., 2017. "Clustering data that are graph connected," European Journal of Operational Research, Elsevier, vol. 261(1), pages 43-53.
    3. Wu, Qinghua & Hao, Jin-Kao, 2015. "A review on algorithms for maximum clique problems," European Journal of Operational Research, Elsevier, vol. 242(3), pages 693-709.
    4. Jorgen W. Weibull, 1997. "Evolutionary Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262731215, April.
    5. Santi, Éverton & Aloise, Daniel & Blanchard, Simon J., 2016. "A model for clustering data from heterogeneous dissimilarities," European Journal of Operational Research, Elsevier, vol. 253(3), pages 659-672.
    6. Florian Frommlet, 2010. "Tag SNP selection based on clustering according to dominant sets found using replicator dynamics," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 4(1), pages 65-83, April.
    7. repec:hhs:iuiwop:487 is not listed on IDEAS
    8. Hassin, Refael & Or, Einat, 2010. "Min sum clustering with penalties," European Journal of Operational Research, Elsevier, vol. 206(3), pages 547-554, November.
    9. De Angelis, Luca & Dias, José G., 2014. "Mining categorical sequences from data using a hybrid clustering method," European Journal of Operational Research, Elsevier, vol. 234(3), pages 720-730.
    10. Rota Bulò, Samuel & Bomze, Immanuel M., 2011. "Infection and immunization: A new class of evolutionary game dynamics," Games and Economic Behavior, Elsevier, vol. 71(1), pages 193-211, January.
    11. Meyer, Patrick & Olteanu, Alexandru-Liviu, 2013. "Formalizing and solving the problem of clustering in MCDA," European Journal of Operational Research, Elsevier, vol. 227(3), pages 494-502.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zhu, Shan & Hu, Xiangpei & Huang, Kai & Yuan, Yufei, 2021. "Optimization of product category allocation in multiple warehouses to minimize splitting of online supermarket customer orders," European Journal of Operational Research, Elsevier, vol. 290(2), pages 556-571.
    2. Immanuel M. Bomze & Michael Kahr & Markus Leitner, 2021. "Trust Your Data or Not—StQP Remains StQP: Community Detection via Robust Standard Quadratic Optimization," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 301-316, February.
    3. Chen, Claire Y.T. & Sun, Edward W. & Miao, Wanyu & Lin, Yi-Bing, 2024. "Reconciling business analytics with graphically initialized subspace clustering for optimal nonlinear pricing," European Journal of Operational Research, Elsevier, vol. 312(3), pages 1086-1107.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Zhu, Shan & Hu, Xiangpei & Huang, Kai & Yuan, Yufei, 2021. "Optimization of product category allocation in multiple warehouses to minimize splitting of online supermarket customer orders," European Journal of Operational Research, Elsevier, vol. 290(2), pages 556-571.
    2. Chen, Yi-Ting & Sun, Edward W. & Lin, Yi-Bing, 2020. "Merging anomalous data usage in wireless mobile telecommunications: Business analytics with a strategy-focused data-driven approach for sustainability," European Journal of Operational Research, Elsevier, vol. 281(3), pages 687-705.
    3. Dufwenberg, Martin, 1997. "Some relationships between evolutionary stability criteria in games," Economics Letters, Elsevier, vol. 57(1), pages 45-50, November.
    4. Lichi Zhang & Yanyan Jiang & Junmin Wu, 2022. "Evolutionary Game Analysis of Government and Residents’ Participation in Waste Separation Based on Cumulative Prospect Theory," IJERPH, MDPI, vol. 19(21), pages 1-16, November.
    5. Gu, Tianqi & Xu, Weiping & Liang, Hua & He, Qing & Zheng, Nan, 2024. "School bus transport service strategies’ policy-making mechanism – An evolutionary game approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 182(C).
    6. Trindade, Graça & Dias, José G. & Ambrósio, Jorge, 2017. "Extracting clusters from aggregate panel data: A market segmentation study," Applied Mathematics and Computation, Elsevier, vol. 296(C), pages 277-288.
    7. Sprumont, Yves, 2013. "Constrained-optimal strategy-proof assignment: Beyond the Groves mechanisms," Journal of Economic Theory, Elsevier, vol. 148(3), pages 1102-1121.
    8. Frommlet, Florian & Ruhaltinger, Felix & Twaróg, Piotr & Bogdan, Małgorzata, 2012. "Modified versions of Bayesian Information Criterion for genome-wide association studies," Computational Statistics & Data Analysis, Elsevier, vol. 56(5), pages 1038-1051.
    9. Kulsum, Umma & Alam, Muntasir & Kamrujjaman, Md., 2024. "Modeling and investigating the dilemma of early and delayed vaccination driven by the dynamics of imitation and aspiration," Chaos, Solitons & Fractals, Elsevier, vol. 178(C).
    10. Guohui Song & Yongbin Wang, 2021. "Mainstream Value Information Push Strategy on Chinese Aggregation News Platform: Evolution, Modelling and Analysis," Sustainability, MDPI, vol. 13(19), pages 1-17, October.
    11. Sandholm,W.H., 2003. "Excess payoff dynamics, potential dynamics, and stable games," Working papers 5, Wisconsin Madison - Social Systems.
    12. Angelo Antoci & Simone Borghesi & Marcello Galeotti, 2013. "Environmental options and technological innovation: an evolutionary game model," Journal of Evolutionary Economics, Springer, vol. 23(2), pages 247-269, April.
    13. Hui Yu & Wei Wang & Baohua Yang & Cunfang Li, 2019. "Evolutionary Game Analysis of the Stress Effect of Cross-Regional Transfer of Resource-Exhausted Enterprises," Complexity, Hindawi, vol. 2019, pages 1-16, November.
    14. Müller, Stephan, 2014. "The evolution of inequality aversion in a simplified game of life," University of Göttingen Working Papers in Economics 219, University of Goettingen, Department of Economics.
    15. Laurent, Monique & Vargas, Luis Felipe, 2022. "Finite convergence of sum-of-squares hierarchies for the stability number of a graph," Other publications TiSEM 3998b864-7504-4cf4-bc1d-f, Tilburg University, School of Economics and Management.
    16. E. Nikolova & N. E. Stier-Moses, 2014. "A Mean-Risk Model for the Traffic Assignment Problem with Stochastic Travel Times," Operations Research, INFORMS, vol. 62(2), pages 366-382, April.
    17. Witte, Björn-Christopher, 2012. "Fund managers - Why the best might be the worst: On the evolutionary vigor of risk-seeking behavior," Economics Discussion Papers 2012-20, Kiel Institute for the World Economy (IfW Kiel).
    18. Antonio Cabrales & Giovanni Ponti, 2000. "Implementation, Elimination of Weakly Dominated Strategies and Evolutionary Dynamics," Review of Economic Dynamics, Elsevier for the Society for Economic Dynamics, vol. 3(2), pages 247-282, April.
    19. Wenke Wang & Xiaoqiong You & Kebei Liu & Yenchun Jim Wu & Daming You, 2020. "Implementation of a Multi-Agent Carbon Emission Reduction Strategy under the Chinese Dual Governance System: An Evolutionary Game Theoretical Approach," IJERPH, MDPI, vol. 17(22), pages 1-21, November.
    20. Srinivas Arigapudi & Yuval Heller & Amnon Schreiber, 2023. "Heterogeneous Noise and Stable Miscoordination," Papers 2305.10301, arXiv.org.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:262:y:2017:i:1:p:1-13. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.