IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v36y2024i2p672-689.html
   My bibliography  Save this article

Correlation Clustering Problem Under Mediation

Author

Listed:
  • Zacharie Ales

    (Unité de Mathématiques Appliquées, École nationale supérieure de techniques avancées Paris, Institut Polytechnique de Paris, 91120 Palaiseau, France; Centre d’études et de recherche en informatique et communications, Conservatoire National des Arts et Métiers, 75003 Paris, France)

  • Céline Engelbeen

    (Laboratoire Quaresmi, Institut Catholique des Hautes Études Commerciales, Brussels, 1150 Woluwe-Saint-Pierre, Belgium)

  • Rosa Figueiredo

    (Laboratoire Informatique d’Avignon, Avignon Université, 84911 Avignon, France)

Abstract

In the context of community detection, correlation clustering (CC) provides a measure of balance for social networks as well as a tool to explore their structures. However, CC does not encompass features such as the mediation between the clusters, which could be all the more relevant with the recent rise of ideological polarization. In this work, we study correlation clustering under mediation (CCM), a new variant of CC in which a set of mediators is determined. This new signed graph clustering problem is proved to be NP-hard and formulated as an integer programming formulation. An extensive investigation of the mediation set structure leads to the development of two efficient exact enumeration algorithms for CCM. The first one exhaustively enumerates the maximal sets of mediators in order to provide several relevant solutions. The second algorithm implements a pruning mechanism, which drastically reduces the size of the exploration tree in order to return a single optimal solution. Computational experiments are presented on two sets of instances: signed networks representing voting activity in the European Parliament and random signed graphs.

Suggested Citation

  • Zacharie Ales & Céline Engelbeen & Rosa Figueiredo, 2024. "Correlation Clustering Problem Under Mediation," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 672-689, March.
    • Handle: RePEc:inm:orijoc:v:36:y:2024:i:2:p:672-689
    DOI: 10.1287/ijoc.2022.0129
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.0129
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.0129?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
    ---><---

    References listed on IDEAS

    as
    1. Nejat Arınık & Rosa Figueiredo & Vincent Labatut, 2023. "Efficient enumeration of the optimal solutions to the correlation clustering problem," Journal of Global Optimization, Springer, vol. 86(2), pages 355-391, June.
    2. Anuj Mehrotra & Michael A. Trick, 1996. "A Column Generation Approach for Graph Coloring," INFORMS Journal on Computing, INFORMS, vol. 8(4), pages 344-354, November.
    3. Mario Levorato & Rosa Figueiredo & Yuri Frota & Lúcia Drummond, 2017. "Evaluating balancing on social networks through the efficient solution of correlation clustering problems," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(4), pages 467-498, December.
    4. Mario Levorato & Rosa Figueiredo & Yuri Frota & Lúcia Drummond, 2017. "Erratum to: Evaluating balancing on social networks through the efficient solution of correlation clustering problems," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(4), pages 499-499, December.
    5. Figueiredo, Rosa & Frota, Yuri, 2014. "The maximum balanced subgraph of a signed graph: Applications and solution approaches," European Journal of Operational Research, Elsevier, vol. 236(2), pages 473-487.
    6. Stephen P. Borgatti, 2006. "Identifying sets of key players in a social network," Computational and Mathematical Organization Theory, Springer, vol. 12(1), pages 21-34, April.
    Full references (including those not matched with items on IDEAS)

    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. Dewan F. Wahid & Elkafi Hassini, 2022. "A Literature Review on Correlation Clustering: Cross-disciplinary Taxonomy with Bibliometric Analysis," SN Operations Research Forum, Springer, vol. 3(3), pages 1-42, September.
    2. Eduardo Queiroga & Anand Subramanian & Rosa Figueiredo & Yuri Frota, 2021. "Integer programming formulations and efficient local search for relaxed correlation clustering," Journal of Global Optimization, Springer, vol. 81(4), pages 919-966, December.
    3. Alex Gliesch & Marcus Ritt, 2022. "A new heuristic for finding verifiable k-vertex-critical subgraphs," Journal of Heuristics, Springer, vol. 28(1), pages 61-91, February.
    4. Mark J. O. Bagley, 2019. "Networks, geography and the survival of the firm," Journal of Evolutionary Economics, Springer, vol. 29(4), pages 1173-1209, September.
    5. Hosseinali Salemi & Austin Buchanan, 2022. "Solving the Distance-Based Critical Node Problem," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1309-1326, May.
    6. Xiao-Feng Xie & Jiming Liu, 2009. "Graph coloring by multiagent fusion search," Journal of Combinatorial Optimization, Springer, vol. 18(2), pages 99-123, August.
    7. Raddant, Matthias & Takahashi, Hiroshi, 2019. "The Japanese corporate board network," Kiel Working Papers 2130, Kiel Institute for the World Economy (IfW Kiel).
    8. Marco Di Summa & Syed Md Omar Faruk, 2023. "Critical node/edge detection problems on trees," 4OR, Springer, vol. 21(3), pages 439-455, September.
    9. N. Cherfi & M. Hifi, 2010. "A column generation method for the multiple-choice multi-dimensional knapsack problem," Computational Optimization and Applications, Springer, vol. 46(1), pages 51-73, May.
    10. M Plumettaz & D Schindl & N Zufferey, 2010. "Ant Local Search and its efficient adaptation to graph colouring," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(5), pages 819-826, May.
    11. Heetae Kim & Petter Holme, 2015. "Network Theory Integrated Life Cycle Assessment for an Electric Power System," Sustainability, MDPI, vol. 7(8), pages 1-15, August.
    12. Alexander Veremyev & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2014. "An integer programming framework for critical elements detection in graphs," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 233-273, July.
    13. Lindquist, Matthew J. & Zenou, Yves, 2019. "Crime and Networks: 10 Policy Lessons," IZA Discussion Papers 12534, Institute of Labor Economics (IZA).
    14. Caterina Liberati & Massimiliano Marzo & Paolo Zagaglia & Paola Zappa, 2015. "Drivers of demand and supply in the Euro interbank market: the role of “Key Players” during the recent turmoil," Financial Markets and Portfolio Management, Springer;Swiss Society for Financial Market Research, vol. 29(3), pages 207-250, August.
    15. Mishael Milaković & Simone Alfarano & Thomas Lux, 2010. "The small core of the German corporate board network," Computational and Mathematical Organization Theory, Springer, vol. 16(2), pages 201-215, June.
    16. Massimiliano Caramia & Paolo Dell'Olmo, 2001. "Iterative coloring extension of a maximum clique," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(6), pages 518-550, September.
    17. Deb Verhoeven & Katarzyna Musial & Stuart Palmer & Sarah Taylor & Shaukat Abidi & Vejune Zemaityte & Lachlan Simpson, 2020. "Controlling for openness in the male-dominated collaborative networks of the global film industry," PLOS ONE, Public Library of Science, vol. 15(6), pages 1-23, June.
    18. César Yajure & Darihelen Montilla & Jose Emmanuel Ramirez-Marquez & Claudio M Rocco S, 2013. "Network vulnerability assessment via bi-objective optimization with a fragmentation approach as proxy," Journal of Risk and Reliability, , vol. 227(6), pages 576-585, December.
    19. Matjaž Krnc & Riste Škrekovski, 2020. "Group Degree Centrality and Centralization in Networks," Mathematics, MDPI, vol. 8(10), pages 1-11, October.
    20. repec:hal:pseose:halshs-00977005 is not listed on IDEAS
    21. Syam Menon & Rakesh Gupta, 2008. "Optimal Broadcast Scheduling in Packet Radio Networks via Branch and Price," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 391-399, August.

    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:inm:orijoc:v:36:y:2024:i:2:p:672-689. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.