Titre: « Multiplicité dans le partitionnement de graphes signés ».

 

La présentation sera en français, et aura lieu en mode hybride : à l’amphithéâtre Blaise Pascal du CERI et en visio.

Le lien de la visio sera déterminé plus tard (probablement juste avant la soutenance).

Le jury sera composé de :
Nadia Brauner, G-SCOP-Université Grenoble Alpes (Rapportrice)
Mathieu Latapy, LIP6-CNRS and Sorbonne Université (Rapporteur)
Rachid Elazouzi, LIA-Avignon Université (Directeur)
Rosa Figueiredo, LIA-Avignon Université (Co-directrice)
Vincent Labatut, LIA-Avignon Université (Co-directeur)
Zacharie Ales, UMA-CEDRIC-ENSTA Paris (Examinateur)
Christine Largeron, LabHC-Université Jean Monne (Examinatrice)

Résumé :
Le partitionnement de graphes signés constitue une tâche importante du point de vue applicatif, étant donné que trouver une partition équilibrée aide à comprendre le système modélisé par le graphe signé. Cependant, l’approche standard dans la littérature se contente de chercher une seule partition, comme si elle caractérisait suffisamment le système étudié. Or, on peut avoir besoin de plusieurs partitions pour construire une image plus juste du système étudié. Même si cette notion de la multiplicité est extrêmement important du point de vue des utilisateurs finaux, elle a été très peu abordée dans la littérature. Dans cette thèse, on veut relaxer l’hypothèse de partition unique pour en chercher plusieurs, et ce dans deux situations séparées. La première concerne les graphes multiplexes signés. Un tel graphe est composé de plusieurs graphes séparés, appelés couches, et chacun contient les mêmes sommets, mais possiblement des liens différents. Toutes les approches traditionnelles proposées pour les graphes multiplexes produisent une seule partition à la fin. Pour pallier ce problème, nous proposons une nouvelle approche qui intègre un processus de clustering avant de fusionner les couches individuelles, ce qui permet de regrouper les couches structurellement similaires. La deuxième situation est spécifique au problème CC. Quand on résout une instance de ce problème, plusieurs partitions optimales peuvent coexister. La question qui se pose est de savoir ce qu’on perd, si on considère une seule partition optimale, alors qu’il en existe plusieurs. Idéalement, il faut les énumérer toutes avant de faire une analyse concluante. Pour ce faire, on propose une nouvelle méthode d’énumération et un framework basé sur l’analyse de clustering afin de d’abord complètement énumérer l’espace des partitions optimales, puis étudier empiriquement un tel espace. Dans les deux situations décrites ci-dessus, mesurer la similarité entre deux partitions est un point essentiel. Pourtant, il n’existe pas une définition de la meilleure mesure pour cela, étant donné que toute définition de la similarité est subjective et dépend notamment de l’application considérée. En conséquence, de nombreuses mesures ont été décrites dans la littérature. Cependant, l’abondance de mesures de similarité est une limitation plutôt qu’un avantage, car la sélection de la mesure la plus appropriée pour une application donnée devient un défi pour les utilisateurs finaux. En plus deux situations de multiplicité décrites ci-dessus, on étudie également ce problème secondaire.

Mots clefs : Graphe Signé, Correlation Clustering, Équilibre Structural, Graphe Multiplexe Signé, Espace des Solutions Optimales, Mesures d’Évaluation entre les Partitions