SCD-Universite de Rennes 1 A search space of graph motifs for graph compression : from Powergraphs to triplet concepts Un espace de recherche des motifs de graphes pour la compression de graphe : de Powergraph aux concepts triplets Compression de graphesVisualisation de graphesCliques et bicliquesAnalyse de concepts formelsProgrammation par ensembles réponses Graph compressionGraph visualizationCliques and bicliquesFormal concept analysisAnswer set programming Graphes, Théorie des Données -- Compression (informatique) Bioinformatique Analyse formelle de concepts 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 graphe 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 clôt sur la présentation d'un environnement de visualisation et de spécification de haut-niveau en théorie des graphes. Power Graph Analysis is a lossless graph compression method aiming at reducing the visual complexity of a graph. The process is to detect motifs, cliques and bicliques, which enables the hierarchical clustering of nodes, the grouping of edges, and ultimately a graph reduced to these groups. This thesis exposes first the formalization of the Power Graph Analysis search space, using Formal Concept Analysis as a theoretical ground to express the compression process. Because the independent treatment of two motifs presents some caveats, we propose a unification framework, triplet concepts, which encode a more general motif for compression. Both Power Graph Analysis and the new approach have been implemented in Answer Set Programming (ASP), a logical formalism, and we present some applications in bioinformatics of these two approaches. This thesis ends on the presentation of an high-level specification and visualization environment for graph theory. Electronic Thesis or DissertationText en application/pdf1 : 15063 Kohttps://ged.univ-rennes1.fr/nuxeo/site/esupversions/7e67fe9b-247e-4ed4-879a-07d3a0cf9e33 Bourneuf Lucas 1993-10-13 FR 24296866X lucas.bourneuf@laposte.net 2019REN1S060 http://www.theses.fr/2019REN1S060 2019-12-17 Informatique Universite de Rennes 1thesis.degree.grantor_1 02778715X Doctorat Universite Bretagne LoirepartenaireRecherche_1 191639044 non ouiNicolasJacquesintervenant_1116276142 MATHSTICecoleDoctorale_1 204770424 INRIA-RENNES partenaireRecherche_2 133175863 ddc:004 NicolasJacquesUniversite de Rennes 1Sciences et technologie, medecine, pharmacie, odontologie, droit, economie, gestion, philosophieMATHSTICÉcole doctorale Mathématiques et sciences et technologies de l'information et de la communication (Rennes)Universite Bretagne Loire Communaute des etablissements d enseignement superieur et de recherche (ComuE) INRIA-RENNES ASCII PDF 15424629