Academic literature on the topic 'Réseaux bipartis'

Nous contribuons au débat sur la « fracturation des élites » en examinant l’organisation collective du patronat américain dans le domaine extraprofessionnel. Nous utilisons les informations d’une base de données originale pour analyser un réseau biparti, reliant 1 472 administrateurs et dirigeants d’entreprises issus de dix secteurs économiques à 5 590 organisations dans huit domaines sociaux différents. En s’inspirant de la théorie de la mobilisation des ressources, nous démontrons l’intérêt de prendre en compte la différenciation sectorielle pour comparer deux ensembles d’élites. L’un appartient à des entreprises établies, représentées dans des secteurs historiquement plus anciens comme l’industrie, les matières premières ou l’alimentation et le commerce de détail. L’autre appartient à des entreprises « challengers » que l’on trouve dans des secteurs plus récents tels que les fonds spéculatifs ( hedge funds ), les sociétés de capital-investissement ( private equity ) et les entreprises technologiques. En modélisant l’accès au capital social, la force des liens au sein du groupe et l’implication politique, nous pouvons montrer que les élites établies ont, aujourd’hui, toujours une plus grande capacité d’action collective face aux élites challengers.

In this paper, we evaluate emergency and risk management by combining social network analysis and the study of social representations. We use a classical, bipartite network analysis method to highlight the key actors in emergency and risk management. The use of social representations anchors our data in a particular territorial experience. Indeed, the proposed article is a case study of the municipality of Saint-André-de-Kamouraska located in the Bas-Saint-Laurent administrative region of Quebec. We argue that the main advantages of our method are: to reveal the key actors in emergency and risk management; to reveal the impact of these actors on the governance of emergencies and risks; to draw the socialization to risk and emergency of the studied population.

Étude sur les graphes bipartis orientes de Moore montrant que de tels graphes existent, pour certaines valeurs du diamètre, et servent a la construction d'une classe de graphes bipartis orientes, asymptotiquement optimaux. Dans la deuxième partie du travail, quelques notions de coloration des graphes sont présentées. Celles-ci permettent de généraliser certains résultats déjà connus dans le cadre de la coloration habituelle et d'en obtenir d'autres plutôt spécifiques a ces notions. La généralisation de la notion de perfection en b-perfection est proposée ce qui permet l'obtention des graphes triangules représentant la seule classe de graphes b-parfaits

Il existe dans le monde réel un nombre important de réseaux qui apparaissent naturellement, on les retrouve un peu partout, dans de nombreuses disciplines, par exemple en informatique avec les réseaux de routeurs, les réseaux de satellites, les réseaux de pages Web, en biologie avec les réseaux des neurones, en écologie avec les réseaux d’interactions biologiques, en linguistiques avec les réseaux de synonymes, en droit avec les réseaux de décisions juridiques, en économie avec les réseaux interbancaires, en sciences humaines avec les réseaux sociaux. De manière générale, un réseau reflète les interactions entre les nombreuses entités d’un système. Ces interactions peuvent être de différentes natures, un lien social ou un lien d’amitié dans un réseau social constitué de personnes, un câble dans un réseau de routeurs, une réaction chimique dans un réseau biologique de protéines, un hyperlien dans un réseau de pages Web, etc. Plus encore, la rapide démocratisation du numérique dans nos sociétés, avec Internet notamment, a pour conséquence de produire de nouveaux systèmes qui peuvent être représentés sous forme de réseaux. Finalement, tous ces réseaux présentent des particularités bien spécifiques : ils sont issus de contextes pratiques, ils sont le plus souvent de grande taille (on retrouve quelques fois des réseaux constitués de plusieurs milliards de nœuds et de liens, contenant donc une grande quantité d’information), ils présentent des propriétés statistiques communes. À cet égard, ils sont regroupés sous l’appellation de réseaux réels, graphes de terrain ou encore réseaux complexes. Aujourd'hui, la science des réseaux est un domaine de recherche à part entière dont l’enjeu principal est de parvenir à décrire et modéliser ces réseaux avec précision afin de révéler leurs caractéristiques générales et de mieux comprendre leurs mécanismes. La plupart des travaux dans ce domaine utilisent le formalisme des graphes qui fournit un ensemble d’outils mathématiques particulièrement adaptés à l’analyse topologique et structurelle des réseaux. Il existe de nombreuses applications dans ce domaine, par exemple des applications concernant la propagation d’épidémie ou de virus informatique, la fragilité du réseau en cas de panne, sa résilience en cas d’attaque, l’étude de la dynamique pour prédire l’apparition de nouveaux liens, la recommandation, etc. L’un des problèmes complexes actuels, qui a beaucoup d’applications, est l’identification de la structure communautaire. La grande majorité des réseaux réels sont caractérisés par des niveaux d’organisation dans leur structure mésoscopique. Du fait de la faible densité globale des réseaux réels couplée à la forte densité locale, on observe la présence de groupes de nœuds fortement liés entre eux et plus faiblement liés avec le reste du réseau, que l’on appelle communautés. Ces structures ont également du sens dans le réseau lui-même, par exemple les communautés d’un réseau social peuvent correspondre à des groupes sociaux (amis, familles, etc.), les communautés d’un réseau de protéines peuvent traduire des réponses fonctionnelles, elles peuvent correspondre à des sujets similaires dans un réseau de pages Web, pour donner quelques exemples [...]
In the real world, numerous networks appear naturally, they are everywhere, in many disciplines, for example in computer science with router networks, satellite networks, webpage networks, in biology with neural networks, in ecology with biological interaction networks, in linguistic with synonym networks, in law with legal decision networks, in economy with interbank networks, in social sciences and humanities with social networks. Generally, a network reflects the interactions between many entities of a system. These interactions have different sources, a social link or a friendship link in a social network, a cable in a router network, a chemical reaction in a protein-protein interaction network, a hyperlink in a webpage network. Furthermore, the rapid democratization of digital technology in our societies, with internet in particular, leads to create new systems which can be seen as networks. Finally, all these networks depict very specific features : they come from pratical contexts, most of the time they are big (they may be comprised of several billion of nodes and links, containing a large amount of information), they share statistical properties. In this regard, they are called real-world networks or complex networks. Nowaday, network science is a research area in its own right focusing on describing and modeling these networks in order to reveal their main features and improve our understanding of their mecanisms. Most of the works in this area use graphs formalism which provides a set of mathematical tools well suited for analyzing the topology of these networks. It exists many applications, for instance applications in spread of epidemy or computer viruses, weakness of networks in case of a breakdown, attack resilience, study for link prediction, recommandation, etc. One of the major issue is the identification of community structure. The large majority of real-world networks depicts several levels of organization in their structure. Because of there is a weak global density coupled with a strong local density, we observe that nodes are usually organized into groups, called communities, which are more internally connected than they are to the rest of the network. Moreover, these structures have a meaning in the network itself, for example communities of a social network may correspond to social groups (friends, families, etc.), communities of a protein-protein network may translate fonctions of a cell, communities may be also related to similar subjects in a webpage network [...]

Cette thèse traite de différents problèmes liés à la théorie des graphes. La plupart des résultats sont liés à l’existence de circuits et de chemins, le reste est consacré à l’étude du diamètre et du routage. Le premier chapitre est consacré à l’étude du pancyclisme dans les graphes vérifiant une condition du type de celle de V. Chvatal et P. Erdos : la connectivité du graphe est supérieure ou égale à sa stabilité. Dans le deuxième chapitre nous nous intéressons aux graphes antisymétriques dont les degrés sont minorés. On y traite principalement des liens existants entre degrés et diamètre dans les graphes antisymétriques. Le troisième chapitre est axé sur la recherche de chemins et circuits dans les graphes bipartis orientés dont le nombre d’arcs ou les degrés sont minorés. Dans le quatrième chapitre, nous précisions la structure des graphes fortement connexes sans C≥₄. Le cinquième chapitre est la synthèse d’une étude sur le routage dans les réseaux d’interconnexion effectuée chez Thomson-C. S. F dans le cadre d’un projet de Réseau Numérique à Intégration de Service (RNIS), permettant de commuter des signaux à débits variables.

Dans cette thèse, nous étudions le problème de la prévision d'apparition de nouveaux liens dans les réseaux d'interactions. Nous nous intéressons en particulier aux réseaux dynamiques ayant une structure bipartite. Nous proposons un modèle de prévision de liens utilisant les techniques d'apprentissage automatique supervisé. Le problème de prévision de liens est considéré dans ce cas comme un problème de classification binaire. Notre approche applique un schéma de propositionnalisation où chaque paire de noeuds est décrite par un ensemble d'attributs représentant des mesures topologiques. Ces mesures sont calculées dans le graphe biparti et dans les graphes projetés qui en découlent. Nous montrons que ces nouvelles similarités dites " indirectes " apportent un gain d'information bénéfique par rapport aux seules similarités directes. Cette thèse apporte aussi de nouvelles solutions au problème de déséquilibre des données dû à la disproportion inhérente entre le nombre de liens qui peuvent se former et le nombre de liens qui se forment réellement. Nous proposons tout d'abord d'utiliser des méthodes de sous-échantillonnage informé pour réduire le déséquilibre. Une deuxième solution au niveau algorithmique consiste en une approche d'apprentissage semi-supervisé. Dans ce cas, le problème de prévision de liens est vu comme un problème d'apprentissage à partir d'un ensemble d'instances étiquetées (classe minoritaire) et un ensemble d'instances non-étiquetées (classe majoritaire). Nous montrons que cette nouvelle approche permet d'améliorer les performances du classifieur sur la classe minoritaire. Les différentes approches proposées sont appliquées sur les données réelles dans le cadre de deux applications : recommandation de collaborations académiques et recommandation de produits dans un site de vente de musique en ligne
In this work, we handle the problem of new link prediction in dynamic complex networks. We mainly focus on studying networks having a bipartite underlaying structure. We propose to apply a propositionnalization approach where each couple of nodes in the network is described by a set of topological measures. One first contribution in this thesis is to consider measures computed in the bipartite graph and also in the associated projected graphs. A supervised machine learning approach is applied. This approach though it gives some good results, suffers from the obvious problem of class skewness. We hence focus on handling this problem. Informed sub-sampling approaches are first proposed. A semi-supervised machine learning approach is also applied. All proposed approaches are applied and evaluated on real datasets used in real application of academic collaboration recommendation and product recommendation in an e-commerce site

Les systèmes de détection d’intrusions (IDS) sont couramment employés pour détecter des attaques sur des réseaux informatiques. Ces appareils analysent le trafic entrant et sortant à la recherche d’anomalies ou d’activités suspectes. Malheureusement, ces appareils génèrent une quantité importante de bruit (ex. : faux positifs, alertes redondantes, etc.), complexifiant grandement l’analyse des données. Ce mémoire présente AlertWheel, une nouvelle application logicielle visant à faciliter l’analyse des alertes sur des grands réseaux. L’application intègre une visualisation radiale affichant simultanément plusieurs milliers d’alertes et permettant de percevoir rapidement les patrons d’attaques importants. AlertWheel propose, entre autres, une nouvelle façon de représenter un graphe biparti. Les liens sont conçus et positionnés de façon à réduire l’occlusion sur le graphique. Contrairement aux travaux antérieurs, AlertWheel combine l’utilisation simultanée de trois techniques de regroupement des liens afin d’améliorer la lisibilité sur la représentation. L’application intègre également des fonctionnalités de filtrage, d’annotation, de journalisation et de « détails sur demande », de façon à supporter les processus d’analyse des spécialistes en sécurité informatique. L’application se décompose essentiellement en trois niveaux : vue globale (roue), vue intermédiaire (matrice d’alertes) et vue détails (une seule alerte). L’application supporte plusieurs combinaisons et dispositions de vues, de façon à s’adapter facilement à la plupart des types d’analyse. AlertWheel a été développé principalement dans le but d’étudier le trafic sur des pots de miel (honeypots). Dans la mesure où tout le trafic sur un honeypot est nécessairement malveillant, ces derniers permettent d’isoler plus facilement les attaques. AlertWheel a été évalué à partir de données provenant du réseau international de honeypots WOMBAT. Grâce à l’application, il a été possible d’isoler rapidement des attaques concrètes et de cibler des patrons d’attaques globaux.

De nombreux systèmes réels et applications, tels que les ateliers flexibles et systèmes embarqués, sont formés de tâches communicantes et sont modélisables par des réseaux de Petri pondérés. Le comportement de ces systèmes peut être vérifié sur leur modèle dès la phase de conception afin d'éviter les simulations post-conception coûteuses. Ces systèmes doivent satisfaire trois propriétés : vivacité, capacité bornée et réversibilité. La vivacité préserve la possibilité d'exécuter chaque tâche. La capacité bornée assure une quantité limitée de ressources. La réversibilité évite une initialisation coûteuse et permet de réinitialiser le système. Les méthodes d'analyse de ces propriétés ont généralement une complexité exponentielle. Dans cette thèse, nous étudions plusieurs sous-classes expressives des réseaux de Petri pondérés, soient les classes Fork-Attribution, Choice-Free, Join-Free et Equal-Conflict, pour lesquelles nous développons les premiers algorithmes polynomiaux garantissant vivacité, capacité bornée et réversibilité. Premièrement, nous apportons des transformations polynomiales qui préservent de nombreuses propriétés des réseaux de Petri pondérés et facilitent l'étude de leur comportement. Deuxièmement, nous utilisons ces transformations pour obtenir plusieurs conditions polynomiales suffisantes de vivacité pour les sous-classes considérées. Enfin, ces transformations simplifient l'étude de la réversibilité sous hypothèse de vivacité. Nous donnons plusieurs caractérisations et conditions polynomiales suffisantes de réversibilité pour les sous-classes étudiées. Nos conditions passent à l'échelle et sont aisément implémentables dans les systèmes réels
Many real systems and applications, including flexible manufacturing systems and embedded systems, are composed of communicating tasks and may be modeled by weighted Petri nets. The behavior of these systems can be checked on their model early on at the design phase, thus avoiding costly simulations on the designed systems. Usually, the models should exhibit three basic properties: liveness, boundedness and reversibility.Liveness preserves the possibility of executing every task, while boundedness ensures that the operations can be performed with a bounded amount ofresources. Reversibility avoids a costly initialization phase and allows resets of the system.Most existing methods to analyse these properties have exponential time complexity.By focusing on several expressive subclasses of weighted Petri nets, namely Fork-Attribution, Choice-Free, Join-Free and Equal-Conflict nets,the first polynomial algorithms that ensure liveness, boundednessand reversibility for these classes have been developed in this thesis.First, we provide several polynomial time transformations that preserve structural andbehavioral properties of weighted Petri nets, while simplifying the study of their behavior.Second, we use these transformations to obtain several polynomial sufficient conditions of livenessfor the subclasses considered. Finally, the transformations also prove useful for the study of the reversibility propertyunder the liveness assumption. We provide several characterizations and polynomial sufficient conditionsof reversibility for the same subclasses. All our conditions are scalable and can be easily implemented in real systems

De nombreux ensembles de données peuvent être représentés sous forme d'une matrice dont les entrées représentent les interactions entre deux entités de natures différentes. Ces matrices sont appelées matrices d'adjacence de graphes bipartites. Dans notre travail, nous faisons l'hypothèse que ces interactions sont déterminées par des variables latentes non observables.Dans un premier temps, notre objectif est d'estimer l'espérance conditionnelle de la matrice de données sachant les variables non observables, en supposant que les entrées de la matrice sont i.i.d. Ce problème peut être formulé comme l'estimation d'une fonction bivariée appelée graphon. Dans notre étude, nous nous concentrons sur deux cas, les graphons constants par morceaux et les graphons Hölder.Nous démontrons des bornes de risque pour l'estimateur des moindres carrés, et nous proposons une adaptation de l'algorithme de Lloyd pour calculer une approximation de cet estimateur et nous présentons les résultats d'expériences numériques pour évaluer les performances de ces méthodes.Dans un deuxième temps, nous abordons les limites du cadre précédent, qui peut ne pas être adapté pour modéliser des situations avec des degrés de sommet bornés. Par conséquent, nous étendons notre étude à l'hypothèse de l'indépendance relaxée, où seules les lignes de la matrice d'adjacence sont supposées indépendantes. Dans ce contexte, nous nous concentrons spécifiquement sur les graphons constants par morceaux
Many real-world datasets can be represented as matrices where the entries represent interactions between two entities of different natures. These matrices are commonly known as adjacency matrices of bipartite graphs. In our work, we make the assumption that these interactions are determined by unobservable latent variables.Firstly, our main objective is to estimate the conditional expectation of the data matrix given the unobservable variables under the assumption that matrix entries are i.i.d. This estimation problem can be framed as estimating a bivariate function known as a graphon. In our study, we focus on two cases: piecewise constant graphons and Hölder-continuous graphons.We derive finite sample risk bounds for the least squares estimator. Additionally, we propose an adaptation of Lloyd's algorithm to compute an approximation this estimator and provide results from numerical experiments to evaluate the performance of these methods.Secondly, we address the limitations of the previous framework, which may not be suitable for modeling situations with bounded degrees of vertices, among other scenarios. Therefore, we extend our study to the relaxed independence assumption, where only the rows of the adjacency matrix are assumed to be independent. In this context, we specifically focus on piecewise constant graphons

De nombreux systèmes réels et applications, tels que les ateliers flexibles et systèmes embarqués, sont formés de tâches communicantes et sont modélisables par des réseaux de Petri pondérés. Le comportement de ces systèmes peut être vérifié sur leur modèle dès la phase de conception afin d'éviter les simulations post-conception coûteuses. Ces systèmes doivent satisfaire trois propriétés : vivacité, capacité bornée et réversibilité. La vivacité préserve la possibilité d'exécuter chaque tâche. La capacité bornée assure une quantité limitée de ressources. La réversibilité évite une initialisation coûteuse et permet de réinitialiser le système. Les méthodes d'analyse de ces propriétés ont généralement une complexité exponentielle. Dans cette thèse, nous étudions plusieurs sous-classes expressives des réseaux de Petri pondérés, soient les classes Fork-Attribution, Choice-Free, Join-Free et Equal-Conflict, pour lesquelles nous développons les premiers algorithmes polynomiaux garantissant vivacité, capacité bornée et réversibilité. Premièrement, nous apportons des transformations polynomiales qui préservent de nombreuses propriétés des réseaux de Petri pondérés et facilitent l'étude de leur comportement. Deuxièmement, nous utilisons ces transformations pour obtenir plusieurs conditions polynomiales suffisantes de vivacité pour les sous-classes considérées. Enfin, ces transformations simplifient l'étude de la réversibilité sous hypothèse de vivacité. Nous donnons plusieurs caractérisations et conditions polynomiales suffisantes de réversibilité pour les sous-classes étudiées. Nos conditions passent à l'échelle et sont aisément implémentables dans les systèmes réels
Many real systems and applications, including flexible manufacturing systems and embedded systems, are composed of communicating tasks and may be modeled by weighted Petri nets. The behavior of these systems can be checked on their model early on at the design phase, thus avoiding costly simulations on the designed systems. Usually, the models should exhibit three basic properties: liveness, boundedness and reversibility.Liveness preserves the possibility of executing every task, while boundedness ensures that the operations can be performed with a bounded amount ofresources. Reversibility avoids a costly initialization phase and allows resets of the system.Most existing methods to analyse these properties have exponential time complexity.By focusing on several expressive subclasses of weighted Petri nets, namely Fork-Attribution, Choice-Free, Join-Free and Equal-Conflict nets,the first polynomial algorithms that ensure liveness, boundednessand reversibility for these classes have been developed in this thesis.First, we provide several polynomial time transformations that preserve structural andbehavioral properties of weighted Petri nets, while simplifying the study of their behavior.Second, we use these transformations to obtain several polynomial sufficient conditions of livenessfor the subclasses considered. Finally, the transformations also prove useful for the study of the reversibility propertyunder the liveness assumption. We provide several characterizations and polynomial sufficient conditionsof reversibility for the same subclasses. All our conditions are scalable and can be easily implemented in real systems

De nombreux problèmes réels relèvent d’une structure bi-relationnelle et peuvent être modélisés suivant des réseaux bipartis. Une telle modélisation permet l'utilisation de solutions standards pour la prédiction et/ou la recommandation de nouvelles relations entre objets de ces réseaux. La tâche de prédiction de liens est un problème largement étudié dans les réseaux simples, c’est-à-dire les réseaux avec un seul type d'interaction entre sommets. Cependant, pour les réseaux multicouche (i.e. réseaux avec plusieurs types d'arêtes entre sommets), ce problème n'est pas encore entièrement résolu.Cette thèse est motivée par l'importance d'une tâche réelle, à savoir la prédiction d'interaction entre un médicament et une cible thérapeutique. La recherche de candidats médicaments prometteurs pour une cible thérapeutique biologique donnée est une partie essentielle de la conception d’un médicament moderne. Dans cette thèse, nous modélisons ce problème comme une tâche de prédiction de lien dans un réseau multicouche biparti. Cette modélisation du problème permet de rassembler différentes sources d'information en une seule structure et ainsi d'améliorer la qualité de la prédiction d’un lien.Cette thèse se concentre sur le problème de la prédiction de liens dans les réseaux multicouches bipartis et apporte deux contributions principales à ce sujet. La première contribution est une solution pour résoudre la prédiction de liens sans limiter le nombre et le type de réseaux, ce qui est le principal défaut des méthodes de l'état de l'art. L'algorithme que nous avons développé modélise une marche aléatoire à la manière du PageRank et est capable de prédire de nouvelles interactions dans le réseau que nous construisons à partir de différentes sources d'information. La deuxième contribution, qui porte aussi sur ce problème, s’appuie sur les méthodes de détection de communautés. Cette solution, moins immédiate et plus dépendante du choix des valeurs des paramètres, donne de meilleurs résultats. Pour cela, nous adaptons des mesures utilisées pour la détection de communautés à la problématique de la prédiction de liens dans les réseaux multicouche bipartis et nous développons de nouvelles méthodes associant des communautés pour la prédiction de liens. Nous évaluons aussi nos méthodes sur des données autres que celles des interactions entre médicaments et cibles thérapeutiques montrant ainsi le caractère générique de notre approche.D’autre part, nous proposons un protocole expérimental de validation des interactions prédites reposant sur l’exploitation de ressources externes. Fondé sur une collection de concepts biomédicaux utilisés comme source de connaissances, ce protocole effectue une validation des paires de médicaments-cibles thérapeutiques qui sont prédites à partir de scores de confiance que nous avons définis. Une évaluation des interactions prédites sur des données tests montre l'efficacité de ce protocole.Enfin, nous nous intéressons au problème de l'identification et de la caractérisation de composés promiscues qui existe dans le processus de développement de médicaments. Nous modélisons ce problème comme une tâche de classification et le résolvons par l'apprentissage automatique. Notre contribution repose sur une approche d'exploration de graphes et d'échantillonnage. De plus, nous avons développé une interface graphique pour fournir un retour d'information aux experts sur les résultats
Many aspects from real life with bi-relational structure can be modeled as bipartite networks. This modeling allows the use of some standard solutions for prediction and/or recommendation of new relations between these objects in such networks. Known as the link prediction task, it is a widely studied problem in network science for single graphs, networks assuming one type of interaction between vertices. For multi-layer networks, allowing more than one type of edges between vertices, the problem is not yet fully solved.The motivation of this thesis comes from the importance of an application task, drug-target interaction prediction. Searching valid drug candidates for a given biological target is an essential part of modern drug development. In this thesis, the problem is modeled as link prediction in a bipartite multi-layer network. Modeling the problem in this setting helps to aggregate different sources of information into one single structure and as a result to improve the quality of link prediction.The thesis mostly focuses on the problem of link prediction in bipartite multi-layer networks and makes two main contributions on this topic.The first contribution provides a solution for solving link prediction in the given setting without limiting the number and type of networks, the main constrains of the state of the art methods. Modeling random walk in the fashion of PageRank, the algorithm that we developed is able to predict new interactions in the network constructed from different sources of information. The second contribution, which solves link prediction using community information, is less straight-forward and more dependent on fixing the parameters, but provides better results. Adopting existing community measures for link prediction to the case of bipartite multi-layer networks and proposing alternative ways for exploiting communities, the method offers better performance and efficiency. Additional evaluation on the data of a different origin than drug-target interactions demonstrate the genericness of proposed approach.In addition to the developed approaches, we propose a framework for validation of predicted interactions founded on an external resource. Based on a collection of biomedical concepts used as a knowledge source, the framework is able to perform validation of drug-target pairs using proposed confidence scores. An evaluation of predicted interactions performed on unseen data shows effectiveness of this framework.At the end, a problem of identification and characterization of promiscuous compounds existing in the drug development process is discussed. The problem is solved as a machine learning classification task. The contribution includes graph mining and sampling approaches. In addition, a graphical interface was developed to provide feedback of the result for experts

Dans cette thèse, nous définissons une nouvelle classe de graphes : les graphes hypotriangulés. Les graphes hypotriangulés vérifient que pour tout chemin de longueur deux, il existe une arête ou un autre chemin de longueur deux entre ses extrémités. Cette classe permet par exemple de modéliser des réseaux robustes. En effet, nous montrons que dans de tels graphes, la suppression d'une arête ou d'un sommet ne modifie pas la distance initiale entre toutes paires de sommets non adjacents. Ensuite, nous étudions et démontrons plusieurs propriétés pour cette classe de graphes. En particulier, après avoir introduit une famille de partitions spécifiques, nous montrons les relations entre certains éléments de cette famille et leur caractère hypotriangulé. De plus, grâce à ces partitions, nous caractérisons les graphes hypotriangulés minimum, qui, parmi les graphes hypotriangulés connexes, minimisent le nombre d'arêtes pour un nombre de sommets fixés.Dans une deuxième partie, nous étudions la complexité, pour la classe des graphes hypotriangulés, de problèmes difficiles dans le cas général. Nous montrons d'abord que les problèmes classiques de cycle hamiltonien, coloration, clique maximum et stable maximum restent NP-difficiles pour cette classe de graphes. Ensuite, nous nous intéressons à des problèmes de modification de graphes, pour lesquels il s'agit de déterminer le nombre minimal d'arêtes à ajouter ou supprimer à un graphe pour obtenir un graphe hypotriangulé : nous montrons la complexité de ces problèmes pour plusieurs classes de graphes
In this thesis, we define a new class of graphs : the hypochordal graphs. These graphs satisfy that for any path of length two, there exists a chord or another path of length two between its two endpoints. This class can represent robust networks. Indeed, we show that in such graphs, in the case of an edge or a vertex deletion, the distance beween any pair of nonadjacent vertices remains unchanged. Then, we study several properties for this class of graphs. Especially, after introducing a family of specific partitions, we show the relations between some of these partitions and hypochordality. Moreover, thanks to these partitions, we characterise minimum hypochordal graph, that are, among connected hypochordal graphs, those that minimise the number of edges for a given number of vertices. In a second part, we study the complexity, for hypochordal graphs, of problems that are NP-hard in the general case. We first show that the classical problems of hamiltonian cycle, colouring, maximum clique and maximum stable set remain NP-hard for this class of graphs. Then, we analyse graph modification problems : deciding the minimal number of edges to add or delete from a graph, in order to obtain an hypochordal graph. We study the complexity of these problems for sevaral classes of graphs