Correlation Clustering Problem Under Mediation

Zacharie Ales (), Céline Engelbeen () and Rosa Figueiredo ()
Additional contact information
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

INFORMS Journal on Computing, 2024, vol. 36, issue 2, 672-689

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.

Keywords: accessible system; correlation clustering; enumeration algorithm; signed graph; structural balance (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0129 (application/pdf)

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:inm:orijoc:v:36:y:2024:i:2:p:672-689

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().