Dans le cadre des séminaires de l’équipe Cornet, Rosa Figueiredo (LIA) présentera son travail de recherche sur la Multiplicité dans le partitionnement de graphes signés, le 17 juin 2022 à 11h35 en salle de réunion.
Résumé : Afin d’étudier des systèmes du monde réel, de nombreux travaux les modélisent à travers des graphes signés, c’est-à-dire des graphes dont les arêtes sont étiquetées comme étant soit positives, soit négatives. Un tel graphe est considéré comme étant structurellement équilibré lorsqu’il peut être partitionné en un certain nombre de modules, de telle sorte que les arêtes positives (négatives) se trouvent à l’intérieur (entre) les modules. Lorsque ce n’est pas le cas, les auteurs cherchent la partition la plus proche de cet équilibre, un problème appelé regroupement de corrélation (CC). L’approche standard utilisée dans la littérature consiste à trouver une seule partition et à se concentrer sur le reste de l’analyse comme si elle suffisait à caractériser pleinement le système étudié. Cependant, cette approche peut ne pas refléter la structure du réseau, et il peut être nécessaire de rechercher d’autres partitions pour obtenir une meilleure vision d’ensemble. Nous étudions l’espace des solutions optimales du CC. Nous proposons une méthode d’énumération efficace permettant de retrouver l’ensemble complet des solutions optimales du CC. Elle combine une stratégie d’énumération exhaustive avec des voisinages de tailles variables, afin d’obtenir une efficacité computationnelle. En appliquant notre méthode, nous montrons empiriquement que dans certaines conditions, il peut y avoir de nombreuses partitions optimales pour un graphe signé. Certaines d’entre elles sont très différentes et fournissent donc des perspectives distinctes sur le système, comme illustré sur un petit réseau du monde réel. Il s’agit d’un résultat important, car il implique que l’on puisse devoir trouver plusieurs, voire toutes, les solutions optimales du CC pour étudier correctement le système considéré.