In the context of team Cornet’s seminars, Rosa Figueiredo (LIA) will present her research work on Multiplicity in Signed Graph Partitioning, on June 6, 2022, at 11:35 in the meeting room.
Abstract: In order to study real-world systems many works model them through signed graphs, i.e. graphs whose edges are labeled 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 (negative) edges are located inside (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). The standard approach used in the literature is to find a single partition and focus the rest of the analysis on it, as if it was sufficient to fully characterize the studied system. Yet, it may not reflect the structure of the network, and one may need to seek for other partitions to build a better picture. We study the space of optimal solutions of the CC. We propose an efficient enumeration method allowing to retrieve the complete space of optimal solutions of the CC. It combines an exhaustive enumeration strategy with neighborhoods of varying sizes, to achieve computational effectiveness. By applying our method, 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 network. This is an important result, as it implies that one may have to find several, if not all, optimal solutions of the CC, in order to properly study the considered system.