{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T11:45:32Z","timestamp":1753875932038,"version":"3.41.2"},"reference-count":45,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2020,12,1]],"date-time":"2020-12-01T00:00:00Z","timestamp":1606780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,3,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In order to study real-world systems, many applied works model them through signed graphs, that is, graphs whose edges are labelled as either positive or negative. Such a graph is considered as structurally balanced when it can be partitioned into a number of modules, such that positive (respectively negative) edges are located inside (respectively in-between) the modules. When it is not the case, authors look for the closest partition to such balance, a problem called Correlation Clustering (CC). Due to the complexity of the CC problem, the standard approach is to find a single optimal partition and stick to it, even if other optimal or high scoring solutions possibly exist. In this work, we study the space of optimal solutions of the CC problem, on a collection of synthetic complete graphs. We show empirically that under certain conditions, there can be many optimal partitions of a signed graph. Some of these are very different and thus provide distinct perspectives on the system, as illustrated on a small real-world graph. This is an important result, as it implies that one may have to find several, if not all, optimal solutions of the CC problem, in order to properly study the considered system.<\/jats:p>","DOI":"10.1093\/comnet\/cnaa025","type":"journal-article","created":{"date-parts":[[2020,7,22]],"date-time":"2020-07-22T19:22:42Z","timestamp":1595445762000},"source":"Crossref","is-referenced-by-count":3,"title":["Multiplicity and diversity: analysing the optimal solution space of the correlation clustering problem on complete signed graphs"],"prefix":"10.1093","volume":"8","author":[{"given":"Nejat","family":"Ar\u0131n\u0131k","sequence":"first","affiliation":[{"name":"Department of Mathematics, Imperial College London, London SW7 2AZ, UK and MRC Mitochondrial Biology Unit, University of Cambridge, Cambridge Biomedical Campus Hills Road, Cambridge CB2 0XY, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rosa","family":"Figueiredo","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Imperial College London, London SW7 2AZ, UK and MRC Mitochondrial Biology Unit, University of Cambridge, Cambridge Biomedical Campus Hills Road, Cambridge CB2 0XY, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Labatut","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Imperial College London, London SW7 2AZ, UK and MRC Mitochondrial Biology Unit, University of Cambridge, Cambridge Biomedical Campus Hills Road, Cambridge CB2 0XY, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,3,7]]},"reference":[{"key":"2021031105082839500_B1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1037\/h0046049","article-title":"Structural balance: a generalization of Heider\u2019s theory","volume":"63","author":"Cartwright,","year":"1956","journal-title":"Psychol. Rev."},{"key":"2021031105082839500_B2","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1177\/001872676702000206","article-title":"Clustering and structural balance in graphs","volume":"20","author":"Davis,","year":"1967","journal-title":"Hum. Relat."},{"key":"2021031105082839500_B3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0095-8956(87)90026-8","article-title":"Balanced decompositions of a signed graph","volume":"43","author":"Zas\u013aavsky,","year":"1987","journal-title":"J. Combin. Theory B"},{"key":"2021031105082839500_B4","first-page":"238","article-title":"Correlation clustering","volume-title":"43rd Annual IEEE Symposium on Foundations of Computer Science","author":"Bansal,","year":"2002"},{"key":"2021031105082839500_B5","doi-asserted-by":"crossref","first-page":"035101(R)","DOI":"10.1103\/PhysRevE.74.035101","article-title":"Network-based predictions of retail store commercial categories and optimal locations","volume":"74","author":"Jensen,","year":"2006","journal-title":"Phys. Rev. E"},{"key":"2021031105082839500_B6","first-page":"021006","article-title":"Community detection for correlation matrices","volume":"5","author":"MacMahon,","year":"2015","journal-title":"Phys. Rev. X"},{"key":"2021031105082839500_B7","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.socnet.2019.02.001","article-title":"Multiple partitioning of multiplex signed networks","volume":"60","author":"Arinik,","year":"2020","journal-title":"Soc. Netw."},{"key":"2021031105082839500_B8","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1002\/net.21907","article-title":"A modeling and computational study of the frustration index in signed networks","volume":"75","author":"Aref,","year":"2019","journal-title":"Networks"},{"key":"2021031105082839500_B9","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1037\/a0017738","article-title":"K-balance partitioning: an exact method with applications to generalized structural balance and other psychological contexts","volume":"15","author":"Brusco,","year":"2010","journal-title":"Psychol. Methods"},{"key":"2021031105082839500_B10","doi-asserted-by":"crossref","first-page":"1483","DOI":"10.1016\/j.cor.2011.01.003","article-title":"An exact approach to the problem of extracting an embedded network matrix","volume":"38","author":"Figueiredo,","year":"2011","journal-title":"Comput. Oper. Res."},{"key":"2021031105082839500_B11","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1177\/0049124110384947","article-title":"Two algorithms for relaxed structural balance partitioning","volume":"40","author":"Brusco,","year":"2010","journal-title":"Sociol. Methods Res."},{"key":"2021031105082839500_B12","first-page":"209","article-title":"An analysis of the Slovene Parliamentary Parties Network","volume":"12","author":"Kropivnik,","year":"1996","journal-title":"Metodolo\u00c5\u00a1ki Zvezki \/ Adv. Methodol. Stat."},{"key":"2021031105082839500_B13","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/j.tcs.2006.05.008","article-title":"Correlation clustering in general weighted graphs","volume":"361","author":"Demaine,","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"2021031105082839500_B14","doi-asserted-by":"crossref","first-page":"497","DOI":"10.2307\/1910129","article-title":"An automatic method of solving discrete programming problems","volume":"28","author":"Land,","year":"1960","journal-title":"Econometrica"},{"key":"2021031105082839500_B15","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1016\/j.socnet.2013.09.002","article-title":"Mixed integer programming formulations for clustering problems related to structural balance","volume":"35","author":"Figueiredo,","year":"2013","journal-title":"Soc. Netw."},{"key":"2021031105082839500_B16","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0378-8733(95)00259-6","article-title":"A partitioning approach to structural balance","volume":"18","author":"Doreian,","year":"1996","journal-title":"Soc. Netw."},{"volume-title":"Generalized Blockmodeling","year":"2005","author":"Doreian,","key":"2021031105082839500_B17"},{"key":"2021031105082839500_B18","doi-asserted-by":"crossref","first-page":"724","DOI":"10.2307\/1241218","article-title":"Multiple optimal solutions in linear programming models","volume":"63","author":"Paris,","year":"1981","journal-title":"Am. J. Agric. Econ."},{"key":"2021031105082839500_B19","doi-asserted-by":"crossref","first-page":"1413","DOI":"10.3390\/en5051413","article-title":"Finding multiple optimal solutions to optimal load distribution problem in hydropower plant","volume":"5","author":"Liu,","year":"2012","journal-title":"Energies"},{"key":"2021031105082839500_B20","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1007\/s10107-016-0978-6","article-title":"The impact of the existence of multiple adjustable robust solutions","volume":"160","author":"de Ruiter,","year":"2016","journal-title":"Math. Program."},{"key":"2021031105082839500_B21","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1023\/A:1018570311399","article-title":"Finding all optimal solutions to the reserve site selection problem","volume":"4","author":"Arthur,","year":"1997","journal-title":"Environ. Ecol. Stat."},{"key":"2021031105082839500_B22","doi-asserted-by":"crossref","first-page":"046106","DOI":"10.1103\/PhysRevE.81.046106","article-title":"Performance of modularity maximization in practical contexts","volume":"81","author":"Good,","year":"2010","journal-title":"Phys. Rev. E"},{"key":"2021031105082839500_B23","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/978-3-540-72792-7_22","volume-title":"International Conference on Integer Programming and Combinatorial Optimization","author":"Danna,","year":"2007"},{"journal-title":"IBM ILOG CPLEX","year":"2018","key":"2021031105082839500_B24"},{"key":"2021031105082839500_B25","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/s00224-008-9130-1","article-title":"Fixed-parameter enumerability of cluster editing and related problems","volume":"46","author":"Damaschke,","year":"2010","journal-title":"Theory Comput. Syst."},{"key":"2021031105082839500_B26","doi-asserted-by":"crossref","first-page":"1127","DOI":"10.1057\/palgrave.jors.2601320","article-title":"On the uniqueness of solutions to linear programs","volume":"53","author":"Appa,","year":"2002","journal-title":"J. Oper. Res. Soc."},{"key":"2021031105082839500_B27","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/sam.10007","article-title":"Simultaneous unsupervised learning of disparate clusterings","volume":"1","author":"Jain,","year":"2008","journal-title":"Stat. Anal. Data Mining"},{"key":"2021031105082839500_B28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.dam.2016.04.002","article-title":"Polyhedral combinatorics of the K-partitioning problem with representative variables","volume":"211","author":"Ales,","year":"2016","journal-title":"Discrete Appl. Math."},{"key":"2021031105082839500_B29","first-page":"640","volume-title":"Handbook of Cluster Analysis","author":"Meil\u0103,","year":"2015"},{"key":"2021031105082839500_B30","first-page":"173","volume-title":"16th Annual Conference on Learning Theory and 7th Kernel Workshop","author":"Meil\u0103,","year":"2003"},{"key":"2021031105082839500_B31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2016.09.002","article-title":"Community detection in networks: a user guide","volume":"659","author":"Fortunato,","year":"2016","journal-title":"Phys. Rep."},{"key":"2021031105082839500_B32","doi-asserted-by":"crossref","first-page":"046119","DOI":"10.1103\/PhysRevE.77.046119","article-title":"Robustness of community structure in networks","volume":"77","author":"Karrer,","year":"2008","journal-title":"Phys. Rev. E"},{"key":"2021031105082839500_B33","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/978-3-319-21786-4_13","volume-title":"International Conference on Computational Social Networks","author":"Nguyen,","year":"2015"},{"key":"2021031105082839500_B34","article-title":"Partitioning around medoids","volume-title":"Finding Groups in Data: An Introduction to Cluster Analysis","author":"Kaufman,","year":"2009"},{"key":"2021031105082839500_B35","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0377-0427(87)90125-7","article-title":"Silhouettes: a graphical aid to the validation of cluster analysis","volume":"20","author":"Rousseeuw,","year":"1987","journal-title":"J. Comput. Appl. Math."},{"key":"2021031105082839500_B36","doi-asserted-by":"crossref","DOI":"10.1038\/srep00336","article-title":"Consensus clustering in complex networks","volume":"2","author":"Lancichinetti,","year":"2012","journal-title":"Sci. Rep."},{"key":"2021031105082839500_B37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.21307\/joss-2019-012","article-title":"Structural balance and signed international relations","volume":"16","author":"Doreian,","year":"2015","journal-title":"J. Soc. Struct."},{"key":"2021031105082839500_B38","doi-asserted-by":"crossref","first-page":"1310","DOI":"10.1257\/aer.102.4.1310","article-title":"Ethnicity and conflict: an empirical study","volume":"102","author":"Esteban,","year":"2012","journal-title":"Am. Econ. Rev."},{"key":"2021031105082839500_B39","doi-asserted-by":"crossref","first-page":"1397","DOI":"10.1016\/j.anbehav.2013.03.032","article-title":"Structural balance in the social networks of a wild mammal","volume":"85","author":"Ilany,","year":"2013","journal-title":"Anim. Behav."},{"key":"2021031105082839500_B40","first-page":"4195","volume":"108","author":"Ahmadian,","year":"2020","journal-title":"3rd International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research"},{"key":"2021031105082839500_B41","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1093\/imaman\/13.3.201","article-title":"Signed graphs for portfolio analysis in risk management","volume":"13","author":"Harary,","year":"2002","journal-title":"IMA J. Manag. Math."},{"key":"2021031105082839500_B42","doi-asserted-by":"crossref","first-page":"1361","DOI":"10.1145\/1753326.1753532","article-title":"Signed networks in social media","volume-title":"SIGCHI Conference on Human Factors in Computing Systems","author":"Leskovec,","year":"2010"},{"key":"2021031105082839500_B43","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1016\/j.dam.2019.04.019","article-title":"Rethinking structural balance in signed social networks","volume":"268","author":"Estrada,","year":"2019","journal-title":"Discrete Appl. Math."},{"key":"2021031105082839500_B44","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.ejor.2017.02.009","article-title":"Clustering data that are graph connected","volume":"261","author":"Benati,","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"2021031105082839500_B45","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0167-6377(98)00006-6","article-title":"Cliques and clustering: a combinatorial approach","volume":"22","author":"Mehrotra,","year":"1998","journal-title":"Oper. Res. Lett."}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/8\/6\/cnaa025\/36509938\/cnaa025.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/8\/6\/cnaa025\/36509938\/cnaa025.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T05:11:40Z","timestamp":1615439500000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnaa025\/6161492"}},"subtitle":[],"editor":[{"given":"Ernesto","family":"Estrada","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2020,12,1]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,3,7]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnaa025","relation":{},"ISSN":["2051-1310","2051-1329"],"issn-type":[{"type":"print","value":"2051-1310"},{"type":"electronic","value":"2051-1329"}],"subject":[],"published-other":{"date-parts":[[2020,12,1]]},"published":{"date-parts":[[2020,12,1]]},"article-number":"cnaa025"}}