Première direction de recherche

Au cours de ma thèse (2000-2002), dirigée par Anne Berry, j'ai exploré un premier procédé d'analyse de données par des graphes : une mesure de dissimilarité entre objets (comme on peut en observer en phylogénie) peut être modélisé par une famille de graphes emboités au sens des arêtes, ces graphes différant par le seuil de dissimilarité décidant la présence ou l'absence d'une arête. Un prétraitement des données peut ainsi corriger certaines incohérences de mesure et fournir une distance (structuration plus forte qu'une dissimilarité) entre les objets étudiés. Le prétraitement que nous avons proposé consistait en une sous-triangulation d'un graphe pour un seuil soigneusement choisi.

Toujours sous la direction d'Anne Berry, notre équipe de recherche a continué d'utiliser ces familles de graphes pour l'analyse d'autres données : génomiques, textuelles, etc. Après ma thèse, l'équipe a mis au point un deuxième procédé algorithmique : la décomposition atomique. Cela consiste, pour un seuil donné, à décomposer le graphe associé à la disssimilarité en unités atomiques séparées par les séparateurs minimaux complets du graphe. La particularité de chaque étape de décomposition est de conserver les sommets du séparateur dans chacune des composantes induites. Ainsi, cette duplication des données aboutit finalement à une partition avec recouvrement des sommets du graphe offrant des informations structurelles sur les données traitées plus précises qu'avec un simple partitionnement.

Deuxième direction de recherche

  La deuxième direction explorée au cours de ma thèse, et qui constitue l'essentielle de ma recherche actuelle, est l'étude des treillis de Galois, utilisés notamment en FCA (Analyse Formelle de Concept), abordée ici encore par le biais d'une modélisation par un graphe non orienté : une relation R sur un ensemble O d'objets et un ensemble A d'attributs (de propriétés) peut être associée à un graphe biparti bip(R)=(0+A,E), avec xy∈E ssi (x,y)∈R, et à son complémentaire cobip(R). Nous avons tout d'abord montré que les séparateurs minimaux de cobip(R) sont en bijection avec les éléments du treillis de Galois L(R)de R (L(R), appelé aussi treillis des concepts de R, et constitué de l'ensemble des sous-produits cartésiens maximaux –au sens de l'inclusion– de la relation, vue comme une partie de OxA). Conséquence de ceci, la saturation (transformation en clique) d'un séparateur minimal de cobip(R) créée un "point d'articulation" dans L(R) et les triangulations de cobip(R) sont en bijection avec les chaînes maximales de L(R). Nous en avons déduit un nouvel algorithme efficace de génération de L(R), ainsi qu'un algorithme de calcul des chaines maximales de L(R) pertinent en sciences humaines avec l'étude des "échelles de Gutmann". Ces nouvelles méthodes nous ont aussi permis d'améliorer la complexité algorithmique des triangulations de graphes et débouchent sur d'autres problématiques de la théorie des graphes étudiées par la suite par Anne Berry.

  Par ailleurs, la taille potentiellement exponentielle de L(R) lui fait souvent préférer l'utilisation d'un sous-ordre, que nous appellerons ordre de Galois P(R), construit sur les éléments les plus pertinents du treillis (les introducteurs, aussi appelés object-concepts et attribute-concepts). P(R) est notamment utilisé dans les hiérarchies d'héritage des langages objets sous le nom de sous-hiérarchie de Galois et en FCA sous le nom d'AOC-poset.

  Nous avons montré que la notion de domination, définie initialement pour les graphes, peut être étendue à L(R) et P(R) et d'une manière plus générale à tout système de fermeture. Cette domination est au coeur de mon travail de recherche car elle me fournit une vision orientée (on pourrait dire hiérarchique) de structures mathématiques qui n'en ont pas l'apparence et facilite la conception d'algorithmes. Par exemple, un multiple éclatement de partition appliqué à bip(R) permet d'obtenir une extension linéaire de P(R) (algorithme TomThumb) que nous avons utilisé dans un nouvel algorithme efficace de génération de P(R), Pluton, dont le comportement pratique a été montré efficace en comparaison avec les algorithmes précédents (Arès, Cérès). Ces considérations théoriques nous ont aussi permi de proposer un autre algorithme, Hermès, d'une grande simplicité de mise en oeuvre et qui pourrait se révéler très efficace en optimisant les procédures qu'il utilise.

  Comme la taille de L(R) peut être exponentielle dans le nombre d'objet utilisé par la relation, il y a un intérêt majeur à déterminer s'il existe des classes pour lesquelles on peut être certain que L(R) a une taille raisonnable. Pour cela, nous avons utlisé la bijection des séparateurs minimaux de cobip(R) avec les éléments du treillis, mais aussi par un résultat ancien leur bijection avec les bicliques maximales de bip(R). Comme certaines classes de graphes bipartis ont un nombre polynomial de bicliques maximales, le treillis correspondant a un nombre polynomial d'éléments. De plus, dans certains cas la matrice de bip(R) peut présenter un organisation particulière facilitant la génération de L(R). Nous avons en particulier proposé un algorithme efficace de génération de L(R) pour les relations 1-consecutives, où L(R) a une taille quadratique sur le nombre d'objets ou d'attributs, et accepte de plus un tracé planaire. Plus généralement, nous avons défini une hiérarchie de treillis polynomiaux, basée sur une hiérarchisation des classes de graphes associés.

  Nous avons plus récemment exploré plus en profondeur les relations qui relient R, bip(R), cobip(R), L(R) et leurs complémentaires (leurs miroirs). La présence d'un point d'articulation (séparateur de taille un) ou d'une arête d'articulation (séparateur complet de taille deux) dans bip(R) permet une décomposition atomique du graphe. Cette décomposition, et la triangulation des sous-graphes qu'elle induit, structure fortement L(R) et améliore les procédés de visualisation de treillis. D'autre part, la présence d'un point d'articulation directement dans L(R) (plus précisément dans son diagramme de Hasse) est une propriété qui passe au treillis de la relation complémentaire, établissant ainsi un lien structurel fort entre une relation et son complémentaire.