/thèse

L’Analyse Power Graph est une technique de compression sans perte de graphe visant à réduire la complexité visuelle d’un graphe. Le processus consiste à détecter des motifs, les cliques et les bicliques, qui permettent d’établir des groupes de nœuds organisés hiérarchiquement, des groupes d’arcs, et finalement un graph réduit à ces groupes. Cette thèse propose tout d’abord la formalisation de l’espace de recherche de l’Analyse Power Graph, en utilisant l’Analyse de Concepts Formels comme base théorique pour exprimer le processus de compression. Le traitement indépendant de deux motifs présente des difficultés et nous proposons une notion unificatrice, les concepts triplets, qui conduiront à un motif unique plus général pour la compression. L’Analyse Power Graph et la nouvelle approche ont été implémentés dans un formalisme logique de Programmation par Ensembles Réponses (ASP), et nous présentons quelques applications en bioinformatique pour les deux approches. La thèse se clot sur la présentation d’un environnement de visualisation et de spécification de haut-niveau en théorie des graphes.