Mes travaux de recherche


       Je travaille sur les graphes. Il s'agit d'objets largement utilsés par toutes les disciplines scientifique, afin de modéliser des problèmes. Un graphe, dans la version la plus simple, n'est rien d'autre qu'une relation binaire sur un ensemble fini. En d'autres termes, on trace des points sur une feuille, on s'intéresse à des sommets que des arêtes relient, et la seule information intéressante est de savoir si deux sommets sont reliés ou non. Je m'intéresse aux décompositions de graphes, c'est-à-dire à des méthodes permettant de découper le graphe en sous-graphes disjoints. Ces sous-graphes entretiennent entre eux des relations particulières, dont l'exploitation permet de résoudre plus efficacement des problèmes. Par exemple, si l'on divise un graphe en composantes connexes, de nombreux problèmes (routage, coloration, clique maximum...) peuvent être résolus (en parallèle) sur chaque composante, puis on fait l'union (ou le maximum, ou une opération plus complexe) des solutions pour obtenir la solution pour le graphe de départ. Je me suis intéressé à une décomposition récursive, qui va plus loin que la décomposition en composantes connexes : la décomposition modulaire. J'ai travaillé sur une généralisation plus abstraite, des décompositions qui l'étendent, ou encore qui qui l'adaptent au graphes bipartis, et sur des algorithmes pour la calculer. Je me suis aussi intéressé en la décomposition des graphes réalistes en communautés (clusters).

oLa décomposition modulaire

Un sommet v d'un graphe distingue un ensemble de sommets X de ce même si il est voisin de certains sommets de V, mais non de tous (et si v n'appartient pas à X). Un ensemble de sommets que nul ne distingue est un module.
Il existe une façon canonique (sans équivoque) de décomposer le graphe, en faisant une partition dont chaque partie est un module, puis en repartant  récursivement sur chaque graphe induit par un module. On obtient ainsi l'arbre de décomposition modulaire, qui permet de représenter dans un espace O(n) la famille (pourtant de taille exponentielle) des modules du graphe. De nombreux problèmes NP-complets (très durs) peuvent être résolus en temps polynomial (rapide) si cet arbre a de bonnes propriétés.

oFamilles partitives et bipartitives

Il s'agit d'un outil ensembliste, qui reprend en un formalisme unifié des propriétés communes de beaucoup d'objets combinatoire. Les familles partitives sont des familles de parties d'un ensemble donné qui possèdent certaines propriétés de fermeture pour l'union, l'intersection et la différence ensembliste. Elles possèdent une structure arborescente, ce qui permet de stocker la famille de façon compacte et de résoudre récursivement des problèmes algorithmiques. Par exemple, les modules des graphes, les comités des hypergraphes, les blocs des graphes d'héritage sont des familles partitives. Une généralisation est de considérer non plus des parties mais des bipartitions, c'est-à-dire des façons de couper en deux un ensemble. On arrive alors aux familles bipartitives, cadre qui permet de décrire les décompositions en splits, en 2-joints ou en composantes 3-connexes des graphes (et d'autres encore) de façon homogène.

oAlgorithmes de décomposition modulaire

J'ai travaillé sur la façon optimale de calculer la décomposition modulaire des graphes, et ai écrit cinq algorithmes de décomposition, tournant tous en temps linéaires en la taille de la donnée (et donc de complexité temporelle optimale).

  

oDécompositions 2-modulaires

Les 2-modules sont une extension des modules. {A, B} est un 2-module d'un graphe si aucun sommet extérieur au 2-module ne sépareA ou B. Il semble que les 2-modules ne donnent pas lieu à une décomposition arborescente récursive, car un 2-module d'un graphe induit n'est pas un 2-module du graphe de départ (cette propriété est par contre vraie pour les modules, ce qui permet de relancer récursivement la décomposition). Je me suis intéressé aux cas qui l'empêchent, les conflits, et les ai caractérisés. Dans les graphes premiers (indécomposable pour la décomposition modulaires) ils sont peu nombreux, au sens qu'en enlevant un ou deux sommets à un 2-module conflictuel, on peut obtenir un 2-module non-conflictuel. On peut alors définir une partition en 2-modules maximaux ayant du sens.

oDécomposition des graphes bipartis

Les graphes bipartis ont des sommets noirs et des blancs ; seuls les sommets de couleur différentes peuvent être adjacents. Les graphes bipartis ont très peu de modules, car la notion de distinction n'est pas adaptée au cas bipartis. En la modifiant un peu (un noir sommet v distingue un ensemble X s'il est voisin de certains sommets blancs de X, mais non de tous. Même définition pour v blanc) on arrive à définir le bimodule (ensemble indistinguable avec cette nouvelle définition). Avec Jean-Luc Fouquet, Michel Habib et Jean-Marie Vanherpe, nous avons étudiés la décomposition correspondante. Elle est moins facile que la décomposition modulaire (présence de conflits, difficulté à définir un quotient, etc) mais nous avons défini la décomposition canonique qui ressemble beaucoup à la décomposition modulaire des graphes oriuentés, et montré qu'elle représente tous les bimodules du graphe. 

o Graphes réalistes et graphe du Web

Les graphes réalistes (small-world) sont définis par une distance inter-sommets faible, un voisinage dense pour chaque sommets (les voisins de x sont voisins entre eux) et la distribution des degrés décroissant exponentiellement. Il se trouvent que les réseaux sociaux, les pages web (liées hypertextuellement) et bien d'autre modélisations de la nature sont de tels small-world graphs.

En collaboration avec Toufik Bennouas, Mohamed Bouklit, Fabien Mathieu et Jean Privat, nous avons développé un modèle particulaire des graphes : chaque page devient une particule évoluant dans l'espace (tridimentionnel ou torique) et chaque lien devient une interraction gravitationnelle (ou une autre force, selon le modèle choisi). Les sommets/particules se regroupent en "galaxies".  Ce modèle gravitationnel donne des résulats signifiants sur les small-world graphs : en particulier sur le graphe du Web on détecte les cybercommunantés, pages du même sujets et densément hyperliées (communautés de pairs, construites sans a-priori).


o[Retour]