I will defend my thesis titled ‘Multiplicity in the Partitioning of Signed Graphs’ on Tuesday, June 29th at 2 p.m. The presentation will be in French and will take place in a hybrid mode: at the Blaise Pascal amphitheater of the CERI and via video conference. The video link is: https://pod.univ-avignon.fr/live/these2/
You are all cordially invited.
The jury will consist of:
- Nadia Brauner, G-SCOP-Université Grenoble Alpes (Reviewer)
- Mathieu Latapy, LIP6-CNRS and Sorbonne Université (Reviewer)
- Rachid Elazouzi, LIA-Avignon Université (Supervisor)
- Rosa Figueiredo, LIA-Avignon Université (Co-supervisor)
- Vincent Labatut, LIA-Avignon Université (Co-supervisor)
- Zacharie Ales, UMA-CEDRIC-ENSTA Paris (Examiner)
- Christine Largeron, LabHC-Université Jean Monnet (Examiner)
You are also invited to the thesis reception following the defense.
Abstract: The partitioning of signed graphs is an important task from an application standpoint, as finding a balanced partition helps in understanding the system modeled by the signed graph. However, the standard approach in the literature aims to find a single partition, as if it adequately characterizes the system under study. Yet, multiple partitions may be needed to construct a fairer image of the studied system. Although this notion of multiplicity is crucial from the end-users’ perspective, it has been scarcely addressed in the literature. In this thesis, we aim to relax the assumption of a unique partition and search for multiple partitions, each within two distinct situations.
The first situation concerns signed multiplex graphs. Such a graph consists of several separate graphs, referred to as layers, each containing the same vertices but possibly different edges. All traditional approaches proposed for multiplex graphs produce a single partition in the end. To address this issue, we propose a new approach that integrates a clustering process before merging individual layers, thereby grouping structurally similar layers.
The second situation is specific to the CC problem. When solving an instance of this problem, multiple optimal partitions may coexist. The question arises about what we lose if we consider only one optimal partition when multiple such partitions exist. Ideally, all partitions should be enumerated before conducting a conclusive analysis. To achieve this, we propose a new enumeration method and a framework based on clustering analysis to first fully enumerate the space of optimal partitions and then empirically study such a space.
In both situations described above, measuring the similarity between two partitions is crucial. However, there is no single best measure for this, given that any definition of similarity is subjective and depends on the application considered. Consequently, numerous measures have been described in the literature. However, the abundance of similarity measures is more of a limitation than an advantage, as selecting the most suitable measure for a given application becomes a challenge for end-users. In addition to the two described multiplicity situations, we also investigate this secondary problem.
Keywords: Signed Graph, Correlation Clustering, Structural Balance, Signed Multiplex Graph, Space of Optimal Solutions, Evaluation Measures between Partitions.