La quantité d'informations stockée dans les bases de données est en constante augmentation rendant ainsi nécessaire la mise au point de systèmes d'analyse et de visualisation. Nous nous intéressons dans cette thèse aux données relationnelles et plus particulièrement aux données biologiques. Cette thèse s'oriente autour de trois axes principaux : tout d'abord, la décomposition de graphes en groupes d'éléments ”similaires” afin de détecter d'éventuelles structures de communauté ; le deuxième aspect consiste à mettre en évidence ces structures dans un système de visualisation, et dans un dernier temps, nous nous intéressons à l'utilisabilité de l'un de ces systèmes de visualisation via une évaluation expérimentale.<br />Les travaux de cette thèse ont été appliqués sur des données réelles provenant de deux domaines de la biologie : les réseaux métaboliques et les réseaux d'interactions gènes-protéines.

La quantité d’informations stockée dans les bases de données est en constante augmentation rendant ainsi nécessaire la mise au point de systémes d’analyse et de visualisation. Nous nous intéressons dans cette thèse aux données relationnelles et plus particulièrement aux données biologiques. Cette thèse s’oriente autour de trois axes principaux : tout d’abord, la décomposition de graphes en groupes d’éléments ”similaires” a?n de détecter d’éventuelles structures de communauté ; le deuxième aspect consiste à mettre en évidence ces structures dans un système de visualisation, et dans un dernier temps, nous nous intéressons à l’utilisabilité de l’un de ces systèmes de visualisation via une évaluation expérimentale. Les travaux de cette thèse ont été appliqués sur des données réelles provenant de deux domaines de la biologie : les réseaux métaboliques et les réseaux d’interactions génes- protéines. / The amount of information stored in databases is constantly increasing making necessary to develop systems for analysis and visualization. In this thesis, we are interested in relational data and in particular, in biological data. This thesis focuses on three main axes : ?rstly, the decomposition of graph into clusters of ”similar” elements in order to detect the community structures ; the second aspect is to highlight these structures in a visualization system; and thirdly, we are interested in the usability of one of these visualization systems through an experimental evaluation. The work presented in this thesis was applied on real data from two ?elds of biology : the metabolic networks and the gene-protein interaction networks.

Le raisonnement efficace dans une grande base de connaissance en logique de description est un défi actuel en raison des inférences "insurmontables", même pour des langages des logiques de description relativement inexpressives. En effet, la présence des axiomes dans la terminologie (TBox) est une des raisons importantes causant une augmentation exponentielle de la taille de l'espace de recherche explorée par les algorithmes d'inférence. Le raisonnement dans la logique de description (LD), c'est essentiellement le test de la relation de la subsomption entre les concepts. Par conséquent, on cherche toujours les expédients pour optimiser ce raisonnement. Des techniques d'optimisation pour améliorer la performance du raisonneur d'une LD se divisent donc naturellement en trois niveaux. Le premier est le niveau conceptuel considérant des techniques pour optimiser les structures d'axiomes dans la TBox. Le deuxième, le niveau algorithmique examinant des techniques pour réduire les exigences de stockage de l'algorithme de tableaux et pour optimiser le test de la relation de subsomption (satisfaisabilité). Le troisième, l'optimisation de requête cherchant des stratégies d'exécution optimales d'une requête d'interrogation dans une base de connaissances. Dans ce mémoire, nous avons étudié une approche de décomposition de l'ontologie s'appelant la "décomposition overlay" qui vise à un deux objectifs principaux : l'optimisation du raisonnement et la méthodologie de conception des ontologies. D'une part l'optimisation pour laquelle nous cherchons à diviser une ontologie dans un ensemble de sous ontologies dont chacune contient une partie de l'ensemble d'axiomes de l'ontologie originale permet d'obtenir ainsi une réduction relative du temps de raisonnement ; d'autre part la méthodologie de conception qui permet de remplacer une ontologie par un ensemble d'ontologies dans une organisation plus ou moins "optimale". Pour le premier objectif, la décomposition overlay d'une ontologie a comme résultat un ensemble de sous-ontologies regroupées dans une ontologie distribuée, appelée ontologie-décomposante (TBox-décomposante) et représentée par la logique de description distribuée. Intuitivement, le fait de pouvoir raisonner parallèlement sur ces sous-ontologies ayant chacune un espace de recherche réduit peut conduire à une réduction du temps relatif du raisonnement. Une propriété importante de cette ontologie est d'être interprétée dans le même domaine que l'ontologie originale. Ceci est une base qui nous suggère la proposition de deux algorithmes de raisonnement pour cette ontologie-décomposante. Concernant l'objectif de méthodologie de conception, nous introduisons deux méthodes de décomposition de l'ontologie reposant sur la décomposition heuristique des graphes. Une méthode repose sur la décomposition selon les séparateurs minimaux des graphes triangulaires et la seconde sur la décomposition selon la mesure des coupes normalisées des régions d'un graphe.

Dans cette thèse, nous étudions diverses largeurs de graphes autour de la largeur arborescente ainsi que de la largeur de clique. Nous commençons avec une étude comparative entre la largeur arborescente d’un graphe et la largeur de clique du graphe d’incidence associé, de laquelle nous extrayons des résultats algorithmiques encourageants. Puis nous présentons quelques propriétés structurelles liées à la largeur arborescente spéciale, largeur relativement récente qui est à mi-chemin entre les deux largeurs précédentes. Enfin nous nous intéressons à une notion plus générale connue sous le nom de fonction de partition sous-modulaire qui englobe, entre autres, les largeurs arborescentes « classique » et spéciale, la largeur de chemin ainsi que la largeur linéaire et les largeurs de branches de coupe et de découpe. Nous présentons alors un algorithme linéaire à paramètre fixé pour le calcul de ces différentes largeurs, lequel généralise un certain nombre de résultats propres à chacune de ces largeurs. / In this thesis, we study some width parameters on graphs, beyond tree-width and clique-width. Our first investigation is a comparative study between the tree-width of a graph and the clique-width of the associated incidence graph, from which we extract some strong algorithmic results. Then we present a few structural properties over a recently defined width called special tree-width and which takes its definition through both tree-width and clique-width. Finally, we end our journey with a more general notion named sub-modular partition fonction and which encompass both “classic” and special tree-widths, path-width, branch-width, linear-width, cut-width and carvingwidth among others. So, we introduce a fixed parameter tractable algorithm computing those widths parameters and thus we generalize a number of results specific to each of them.

Cette thèse s’intéresse aux problématiques de routage dans les réseaux, notamment dans le graphe des systèmes autonomes (AS) d’Internet. Nous cherchons d’une part à mieux comprendre les propriétés du graphe de l’Internet qui sont utiles dans la conception de nouveaux paradigmes de routage. D’autre part, nous cherchons à évaluer par simulation les performances de ces paradigmes. La première partie de mes travaux porte sur l’étude d’une propriété́ métrique, l’hyperbolicité́ selon Gromov, utilisée dans la conception de nouveaux paradigmes de routage. Je présente dans un premier temps une nouvelle approche pour le calcul de l’hyperbolicité́ d’un graphe utilisant une décomposition du graphe par les cliques-séparatrices et la notion de paires éloignées. Je propose ensuite un nouvel algorithme pour le calcul de l’hyperbolicité́ qui, combiné avec la méthode de décomposition par les cliques-séparatrices, permet son calcul sur des graphes composés de 58 000 sommets en quelques heures. La deuxième partie de mes travaux porte sur le développement de DRMSim, une nouvelle plate-forme de simulation de modèles de routage dynamiques. Celle-ci permet l’évaluation des performances des schémas de routage et leur comparaison au protocole de référence, le protocole de routeur frontière, BGP. DRMSim a permis l’étude par simulation de différents schémas de routage compact sur des topologies à O(10k) nœuds. Je détaille l’architecture de DRMSim et quelques exemples d’utilisation. Puis, je présente une étude réalisée en vue de développer une version parallèle et distribuée de DRMSim dans le cadre de la simulation de BGP / This thesis considers routing issues in networks, and particularly the graph of the autonomous systems (AS) of the Internet. Firstly, we aim at better understanding the properties of the Internet that are useful in the design of new routing paradigms. Secondly, we want to evaluate by simulation the performance of these paradigms. The first part of my work concerns the study of the Gromov hyperbolicity, a useful metric property for the design of new routing paradigms. I show how to use a decomposition of the graph by clique-separators as a pre-processing method for the computation of the hyperbolicity. Then, I propose a new algorithm to compute this property. Altogether, these methods allows us for computing the hyperbolicity of graphs up to 58 000 nodes. The second part of my work concerns the development of DRMSim, a new Dynamic Routing Model Simulator. It facilitates the evaluation of the performances of various routing schemes and their comparison to the standard routing scheme of the Internet, the border router protocol BGP. Using DRMSim, we performed simulations of several compact routing schemes on topologies up to O(10k) nodes. I describe its architecture and detail some examples. Then, I present a feasibility study for the design of a parallel/distributed version of DRMSim in order to simulate BGP on larger topologies.