[Soutenance de thèse] Nejat Arinik : "Multiplicité dans le partitionnement de graphes signés", LIA, le 29/06/21

Discipline

Informatique

Laboratoire

Laboratoire Informatique d'Avignon

Direction

• Rachid Elazouzi
• Vincent Labatut
• Rosa Figueiredo

Composition du jury de soutenance

• M. Zacharie Ales
• Mme Nadia Brauner
• Mme Christine Largeron
• M. Mathieu Latapy

Résumé de la thèse

Selon la théorie de l'équilibre structural, un graphe signé est structurellement équilibré s’il peut être partitionné en sous-groupes mutuellement hostiles (i.e. reliés seulement par des liens négatifs) tout en exhibant une solidarité interne (i.e. contenant uniquement des liens positifs). Mais un réseau réel (i.e. un graphe représentant un système du monde réel) est rarement parfaitement équilibré: on trouvera quelques liens positifs entre les groupes et/ou quelques liens négatifs à l’intérieur de certains groupes. L’un des défis du domaine est de quantifier le niveau de déséquilibre d’un tel réseau et d'identifier les liens qui causent ce déséquilibre. Le problème Correlation Clustering (CC) se définit précisément par l'obtention d'une partition possédant un déséquilibre minimal.

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. En l'appliquant sur les données du Parlement Européen, cela nous a permis non seulement d'extraire plusieurs comportements de vote caractéristiques, ce qui améliore l'interprétation, mais aussi d'expliquer le contexte associé aux comportements, grâce aux documents législatifs concernés.

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. Nos résultats ont révélé une typologie de l'espace de partitions optimales: 1) une seule partition optimale; 2) quelques partitions constituant une seule classe; 3) beaucoup de partitions optimales constituant une seule classe de forme allongée et 4) plusieurs partitions optimales constituant plusieurs classes de partitions.

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. Pour pallier ce problème, nous proposons un nouveau framework. Celui-ci prend en compte plusieurs paramètres liés au partitionnement (e.g. nombre de sommets, nombre de modules), et évalue statistiquement les mesures dans plusieurs scénarios de partitionnement à travers ces paramètres, via l'analyse de régression. Nos résultats montrent l'importance d'une évaluation générique et paramétrique, car le comportement d'une mesure dans un scénario spécifique peut être complètement différent en fonction des valeurs des paramètres.