Graphs are used to model a wide range of systems from different disciplines including social network analysis, biology, and big data processing. When analyzing these constantly changing dynamic graphs at a high frequency, performance is the main concern. Depending on the graph size and structure, update frequency, and read accesses of the analysis, the use of different data structures can yield great performance variations. Even for expert programmers, it is not always obvious, which data structure is the best choice for a given scenario. In previous work, we presented an approach for handling the selection of the most efficient data structures automatically using a compile-time approach well-suited for constant workloads. We extend this work with a measurement study of seven data structures and use the results to fit actual cost estimation functions. In addition, we evaluate our approach for the computations of seven different graph metrics. In analyses of real-world dynamic graphs with a constant workload, our approach achieves a speedup of up to 5.4× compared to basic data structure configurations. Such a compile-time based approach cannot yield optimal results when the behavior of the system changes later and the workload becomes non-constant. To close this gap we present a run-time approach which provides live profiling and facilitates automatic exchanges of data structures during execution. We analyze the performance of this approach using an artificial, non-constant workload where our approach achieves speedups of up to 7.3× compared to basic configurations.

Eine Graph-Visualisierung von Daten findet Einsatz in verschiedenen Domänen und erleichtert die Gewinnung von Erkenntnissen über Relationen. Viele Datensätze haben eine dynamische Natur und verändern sich über die Zeit. Dynamische Graphen kodieren die temporalen Änderungen der Objekte und ihrer Relationen. Der Vorteil der hochauflösenden Displaywand besteht darin, dass durch einen vergrößerten Darstellungsraum ein guter Überblick über die strukturellen Zusammenhänge entsteht. Der Einsatz der heutzutage sehr verbreiteten mobilen Endgeräte bietet eine lokale nutzerspezifische Darstellung für die Exploration und Manipulation der Graphen einschließlich ihrer dynamischen Komponente. Während sich viele Arbeiten auf die Analyse statischer Strukturen fokussieren, wird das Problem der Exploration und Visualisierung dynamischer Graphen vergleichsweise wenig adressiert. In der vorliegenden Arbeit werden die grundlegenden Aufgaben für die dynamischen Graphen sowie der Stand der Forschung über den interaktiven Raum der kombinierten Anwendung Displaywand und Mobilgerät untersucht. Auf dieser Basis werden die Interaktionskonzepte für die Exploration dynamischer Graphen und die Visualisierung der Änderungen erarbeitet. Der interaktive Raum bietet dabei die räumlichen Freiheitsgrade für die Gestaltung der Interaktionen. Die entstandene Konzeption dient abschließend als Grundlage für die prototypische Umsetzung in einem existierenden Projekt zur Exploration von Graphen mithilfe mobiler Endgeräte.:- Einleitung - Grundlagen und verwandte Arbeiten - Konzeption - Umsetzung - Zusammenfassung, Bewertung und Ausblick - Literaturverzeichnis / Graph visualization for data is used in various domains. It facilitates the extraction of knowledges about the relationships. Many datasets have a dynamic nature and change over time. Dynamic graphs ecode the temporal changes of objects and their relations. The advantage of the high-resolution displaywall is providing a good overview of the structural relations caused by an enlarged representation space. The use of nowadays widespread mobile devices provides a local user-specific view for the exploration of the graphs including their dynamic component. While many studies focuse on the analysis of static data structures, the issue of exploration and visualization of dynamic graphs is adressed by only a few works. This thesis investigates the basic tasks for dynamic graphs and state of research into the interaction space of combined applications of displaywall and mobile device. On this basis the interaction concepts for the exploration of dynamic graphs and the visualization of the changes are developed. The interaction space provides the spatial degrees of freedom for the design of interactions. The resulting set of concepts is the basis for the prototypical implementation in the existing project for the exploration of graphs using the mobile devices.:- Einleitung - Grundlagen und verwandte Arbeiten - Konzeption - Umsetzung - Zusammenfassung, Bewertung und Ausblick - Literaturverzeichnis

Les travaux présentés dans la thèse s'inscrivent dans le cadre de l'analyse des graphes de terrain (complex networks) et plus précisément de la tâche de détection de communautés, c'est-à-dire la reconnaissance algorithmique de sous-graphes particulièrement denses. Nous nous intéressons spécifiquement à l'implémentation d'une telle méthode dans un contexte fortement décentralisé et distribué : des réseaux MANET opportunistes formés par de petits objets connectés communiquant en pair-à-pair. Afin de tenir compte des contraintes d'exécution d'algorithme dans de tels réseaux, les travaux présentés dans la thèse proposent des méthodes conçues selon le paradigme récent et actif nommé orienté sommet, en alliant le traitement de graphes Think-Like-a-Vertex aux méthodes de détection de communautés basées sur des leaders ou des graines : celles-ci présentent en effet des propriétés de décentralisation qui autorisent des implémentations parallèles et distribuées appropriées au cadre applicatif considéré. Dans ce contexte, nous proposons d'une part un principe global de fonctionnement original que nous mettons en oeuvre et déclinons dans trois algorithmes dédiés à trois configurations différentes de la tâche de détection de communautés : l'algorithme VOLCAN considère le cas de référence des communautés disjointes dans un graphe statique. Nous l'étendons ensuite avec l'algorithme LOCNeSs au cas des communautés recouvrantes, qui autorisent un sommet à appartenir à plusieurs communautés simultanément : cette généralisation donne plus de flexibilité à la détection et la rend plus appropriée au cadre applicatif considéré. Nous examinons également le cas des graphes dynamiques, c'est-à-dire dont les sommets et les arêtes évoluent au cours du temps, auquel est consacré l'algorithme DynLOCNeSs. Chacun des algorithmes est associé à une implémentation décentralisée et fait l'objet d'une étude théorique ainsi qu'expérimentale sur des données artificielles et réelles permettant d'évaluer la qualité des résultats fournis et de les comparer aux méthodes de l'état de l'art. Nous considérons également, dans un cas particulier de réseau mobile ad-hoc spontané et décentralisé issu d'une application réelle de vêtements intelligents et communicants, une tâche de cheminement permettant d'identifier des interlocuteurs. Nous proposons une stratégie de recommandation utilisant la structure communautaire, modélisée et évaluée à travers un algorithme nommé SWAGG. / Our research is in the field of complex network analysis and mining, specifically addressing the communit detection task, ie. algorithms aiming to uncover particularly dense subgraphs. We focus on the implementation of such an algorithm in a decentralised and distributed context : opportunistic MANET constituted of small wireless devices using peer-to-peer communication. To tackle the implementation constraints in such networks, we propose several methods designed according to the novel and trending vertex-centred paradigm, by combining Think-Like-a-Vertex graph processing with vertex-centred community detection methods based on leaders or seeds : they show specific properties allowing dsitributed implementations suiting the opportunistic MANET case. In this context, we first a global working principle and implement it in three different algorithms dedicated to three different configurations of community detection : the VOLCAN algorithm manages the classical disjoint community detection task in a static graph. We extend it with the LOCNeSs algorithm, that is dealing with overlapping communities which means that one vertex can belong to several communities. It adds more flexibility to the method and more significance to produced results. We also tackle the dynamic graphe case (graph evolving over time), addressed by the DynLOCNeSs algorithm.Each algorithm comes with a decentralised implementation and theoretical as well as experimental studies conducted both on real and synthetic benchmark data, allowing to evaluate the quality of the results and compare to existing state-of-the-art methods. Finally, we consider a special case of opportunistic decentralised MANET developped as a part of a research project about smart and communicating clothing. We formalise a task of path finding between smart t-shirts holders and propose a recommandation strategy using community structure, that we model and evaluate through an algorithm named SWAGG.

Le calcul de motifs dans de grandes relations binaires a été très étudié. Un succès emblématique concerne la découverte d'ensembles fréquents et leurs post-traitements pour en dériver des règles d'association. Il s'agit de calculer des motifs dans des relations binaires qui enregistrent quelles sont les propriétés satisfaites par des objets. En fait, de nombreux jeux de données se présentent naturellement comme des relations n-aires (avec n > 2). Par exemple, avec l'ajout de dimensions spatiales et/ou temporelles (lieux et/ou temps où les propriétés sont enregistrées), la relation binaire Objets x Propriétés est étendue à une relation 4-aire Objets x Propriétés x Lieux x Temps. Nous avons généralisé le concept de règle d'association dans un tel contexte multi-dimensionnel. Contrairement aux règles usuelles qui n'impliquent que des sous-ensembles d'un seul domaine de la relation, les prémisses et les conclusions de nos règles peuvent impliquer des sous-ensembles arbitraires de certains domaines. Nous avons conçu des mesures de fréquence et de confiance pour définir la sémantique de telles règles et c'est une contribution significative de cette thèse. Le calcul exhaustif de toutes les règles qui ont des fréquences et confiances suffisantes et l'élimination des règles redondantes ont été étudiés. Nous proposons ensuite d'introduire des disjonctions dans les conclusions des règles, ce qui nécessite de retravailler les définitions des mesures d'intérêt et les questions de redondance. Pour ouvrir un champ d'application original, nous considérons la découverte de règles dans des graphes relationnels dynamiques qui peuvent être codés dans des relations n-aires (n ≥ 3). Une application à l'analyse des usages de bicyclettes dans le système Vélo'v (système de Vélos en libre-service du Grand Lyon) montre quelques usages possibles des règles que nous savons calculer avec nos prototypes logiciels. / Pattern discovery in large binary relations has been extensively studied. An emblematic success in this area concerns frequent itemset mining and its post-processing that derives association rules. In this case, we mine binary relations that encode whether some properties are satisfied or not by some objects. It is however clear that many datasets correspond to n-ary relations where n > 2. For example, adding spatial and/or temporal dimensions (location and/or time when the properties are satisfied by the objects) leads to the 4-ary relation Objects x Properties x Places x Times. Therefore, we study the generalization of association rule mining within arbitrary n-ary relations: the datasets are now Boolean tensors and not only Boolean matrices. Unlike standard rules that involve subsets of only one domain of the relation, in our setting, the head and the body of a rule can include arbitrary subsets of some selected domains. A significant contribution of this thesis concerns the design of interestingness measures for such generalized rules: besides a frequency measures, two different views on rule confidence are considered. The concept of non-redundant rules and the efficient extraction of the non-redundant rules satisfying the minimal frequency and minimal confidence constraints are also studied. To increase the subjective interestingness of rules, we then introduce disjunctions in their heads. It requires to redefine the interestingness measures again and to revisit the redundancy issues. Finally, we apply our new rule discovery techniques to dynamic relational graph analysis. Such graphs can be encoded into n-ary relations (n ≥ 3). Our use case concerns bicycle renting in the Vélo'v system (self-service bicycle renting in Lyon). It illustrates the added-value of some rules that can be computed thanks to our software prototypes.

Dans le but de remédier aux problèmes aujourd’hui omniprésents dans le secteur du transport, qu’ils soient financiers, environnementaux ou autres, nous nous intéressons à l’établissement d’un système de covoiturage dynamique optimisé. La voiture partagée est venue subvenir à des besoins restés insatisfaits en matière de déplacement (flexibilité spatiotemporelle…) encourageant l’émergence d’un mode de transport révolutionnaire qu’est la comodalité. Le focus est alors mis sur la complémentarité entre les modes collectifs et individuels et vient considérer la voiture partagée et plus particulièrement le covoiturage comme des modes de transport à part entière. Placés dans ce cadre, nous nous intéressons à l’aspect temps réel dans les systèmes de covoiturage et développons nos travaux dans ce sens. Ce problème ayant une complexité qui n’est pas des moindres, tous nos efforts sont dirigés dans le but de contrecarrer cet obstacle et mettre en œuvre une application logicielle compétitive à grande échelle offrant satisfaction et qualité de service. Pour ce faire, nous considérons une alliance des systèmes multi-agents et des techniques d’optimisation donnant lieu à des agents optimisateurs répartis selon une modélisation de graphe dynamique distribué. Celui-ci est établi sur la base d’un principe de décomposition du réseau géographique desservi inspiré des techniques de classification pour la mise en exergue des zones de concentration des abonnés. Cette modélisation favorise le traitement parallèle des requêtes de par la décentralisation et décomposition du processus initial sur une multitude d’agents optimisateurs chargés chacun d’une ou plusieurs tâches de moindre complexité / In an attempt to address the transportation problems now ubiquitous, may them be financial, environmental or any, we are mainly involved with the establishment of a dynamic optimized carpooling service. Shared cars came to remedy these problems and meet the longtime remained unsatisfied needs (spatiotemporal flexibility…) and so promote the comodal practice. The stress is then put on the complementarity between collective and individual means of transportation and comes to confirm the shared car and more particularly the carpooling as a transport mode as a whole. Based on this, we are mainly interested in setting up a real time ridesharing service providing the needed efficiency in such a context. In fact, the problem we tackle has a complexity of exponential order which must be wiped out preventing from adverse impacts. Blending the agent paradigm with the optimization technics helped reach our goals of implementing a large-scale competitive and fully automated support and providing the necessary efficiency and quality of service. The proposed alliance is realized through communicating optimizing agents spread according to a distributed dynamic graph modeling. The latter is established through a subdivision process of the served geographic network and has been inspired from clustering technics to put the stress on limited and intersecting areas of high density. This helps to promote the parallel requests treatment over a decentralized process. Thus, each optimizing agent firstly manage the requests parts included within the zone it is responsible for and then recompose global responses in coalition with concerned agents in a distributed artificial intelligence context

Graphs are used to model a wide range of systems from different disciplines including social network analysis, biology, and big data processing. When analyzing these constantly changing dynamic graphs at a high frequency, performance is the main concern. Depending on the graph size and structure, update frequency, and read accesses of the analysis, the use of different data structures can yield great performance variations. Even for expert programmers, it is not always obvious, which data structure is the best choice for a given scenario. In previous work, we presented an approach for handling the selection of the most efficient data structures automatically using a compile-time approach well-suited for constant workloads. We extend this work with a measurement study of seven data structures and use the results to fit actual cost estimation functions. In addition, we evaluate our approach for the computations of seven different graph metrics. In analyses of real-world dynamic graphs with a constant workload, our approach achieves a speedup of up to 5.4× compared to basic data structure configurations. Such a compile-time based approach cannot yield optimal results when the behavior of the system changes later and the workload becomes non-constant. To close this gap we present a run-time approach which provides live profiling and facilitates automatic exchanges of data structures during execution. We analyze the performance of this approach using an artificial, non-constant workload where our approach achieves speedups of up to 7.3× compared to basic configurations.

Avec l’arrivée massive des technologies sans fil, le nombre de terminaux mobiles n’a cessé de croître, pour des usages et des ressources de communication diversifiés. En intégrant les objets du quotidien, nos réseaux de communications sont devenus dynamiques aussi bien en termes de ressources que de topologie physique, offrant accès à des informations de plus en plus riches. La tâche de gestion s’est ainsi complexifiée et requiert des temps de réponse de plus en plus courts difficilement réalisables par un administrateur humain. Il devient indispensable de mettre en œuvre des capacités de gestion autonomes pour les nouveaux réseaux. Dans tous les cas, la gestion d’un système implique une étape essentielle : sa mesure et sa supervision. Peu importe sa nature, c’est cette étape de prise d’information qui permet sa caractérisation, son analyse et son contrôle. Le domaine des réseaux n’échappe pas à cette règle et les objets qui le composent auront besoin d’acquérir des informations sur leur environnement pour mieux s’y adapter. Dans cette thèse, nous nous intéressons au partage efficace de ces informations de mesures à des fins d’auto-analyse et d’évaluation distribuée de la performance. Après avoir formalisé le problème de la mesure distribuée, nous nous consacrons dans un premier temps à l’organisation des échanges de mesures dans les graphes dynamiques. Nous proposons une nouvelle heuristique pour le consensus de la moyenne qui converge plus rapidement que celles de l’état de l’art. Dans un second temps, nous considérons des topologies plus stables pouvant utiliser des flux TCP comme moyen d’échange. Nous proposons un mécanisme d’ordonnancement de ces flux qui conserve le même comportement face à la congestion, tout en réduisant leur latence moyenne. Enfin, nous nous intéressons à l’information de mesure échangée. Nous montrons comment les nœuds peuvent superviser diverses métriques telles que la performance d’un système en se basant sur l’utilité de ses agents, et proposons une méthode pour qu’ils puissent analyser l’évolution de cette performance / With the massive rise of wireless technologies, the number of mobile stations is constantly growing. Both their uses and their communication resources are diversified. By integrating our daily life objects, our communication networks become dynamic in terms of physical topology but also in term of resources. Furthermore, they give access to a richer information. As a result, the management task has become complex and requires shorter response time that a human administrator can not respect. It becomes necessary to develop an autonomic management behavior in next generation networks. In any manner, managing a system requires essential steps which are : its measurement and its supervision. Whatever the nature of a system, this stage of information gathering, allows its characterization and its control. The field of networks is not the exception to the rule and objects that compose them will need to acquire information on their environment for a better adaptation. In this thesis, we focus on the efficient sharing of this information, for self-analysis and distributed performance evaluation purposes. After having formalized the problem of the distributed measurement, we address in a first part the fusion and the diffusion of measures in dynamic graphs. We develop a new heuristic for the average consensus problem offering a better contraction rate than the ones of the state of the art. In a second part, we consider more stable topologies where TCP is used to convey measures. We offer a scheduling mechanism for TCP flows that guaranty the same impact on the network congestion, while reducing the average latency. Finally, we show how nodes can supervise various metrics such as the system performance based on their utilities and suggest a method to allow them to analyze the evolution of this performance

Garg and Könemann developed a framework for computing multi-commodity maximum flow in a graph, later called a multiplicative weight update framework. Madry used this framework and exchanged Dijkstra’s algorithm to a dynamic graph algorithm for approximating the shortest paths through the graph. With this approachhe developed the fastest algorithm to date for calculating the multi-commodity maximum flow, with a running time of Õ(mnϵ2). This project have implemented the algorithm and compared it with a slightly modified version of the former fastest algorithm by Fleischer with a time complexity of Õ(m2ϵ2). The results show that Madry’s algorithms is slower than Fleischer’s algorithm in practice for graph with less than 100 million edges. This project also computed the space needed for the dynamic algorithms used in Madry’s algorithm and can show a resulting space complexity of O(n(n+m)log2n), compared to the space complexity of Fleischer’s algorithm of O(n). For a graph with 100 million edges, 50 million Gb of space is needed to use Madry’s algorithm, which is more than our test computers had. We can therefore conclude that Madry’s algorithm is not usable in real life today, both in terms of memory usage and time consumption. / Garg and Könemann utvecklade ett framework för att beräkna multi-commodity maximum flöde i en graf sedan kallat ett multiplicative weight update framework. Madry använde detta framework och bytte ut Dijkstra’s algoritm mot en dynamisk grafalgoritm för att kunna approximera kortaste vägen i grafen. Med detta angeppssätt utvecklade han den idag snabbaste algoritmen för beräkning av multicommodity maximum flöde med en tids komplexitet på Õ(mnϵ2). Det här projektet har implementerat hans algoritm och jämfört den med den tidigare snabbaste algoritmen skapad av Fleischer med en tidskomplexitet på Õ(m2ϵ2). Resultatet visar att Madrys algoritm är långsammare än Fleischers algoritm i praktiken för grafer med färre än 100 miljoner kanter. Detta projekt beräknade också minnesåtgången för de dynamiska algoritmerna i Madrys algorithm och kan visa en resulterade minneskomplexitet på O(n(n+m)log2n), jämfört med Fleischers algoritm på O(n). För en graf med 100 miljoner kanter så behövs 50 miljoner Gb av minne för att kunna använda Madrys algoritm, vilket var mer än våra testdatorer hade. Vi kan därför konstatera att Madrys algoritm inte är användbar i praktiken idag, både när det kommer till minnesanvändning och till tidsåtgång.

Graphs are often considered an excellent way of modeling complex real-world problems since they allow to capture relationships between items. Because of their ubiquity, graph embedding techniques have occupied research groups, seeking how vertices can be encoded into a low-dimensional latent space, useful to then perform machine learning. Recently Graph Neural Networks (GNN) have dominated the space of embeddings generation due to their inherent ability to encode latent node dependencies. Moreover, the newly introduced Inductive Graph Neural Networks gained much popularity for inductively learning and representing node embeddings through neighborhood aggregate measures. Even when an entirely new node, unseen during training, appears in the graph, it can still be properly represented by its neighboring nodes. Although this approach appears suitable for dynamic graphs, available systems and training methodologies are agnostic of dynamicity and solely rely on re-processing full graph snapshots in batches, an approach that has been criticized for its high computational costs. This work provides a thorough solution to this particular problem via an efficient prioritybased method for selecting rehearsed samples that guarantees low complexity and high accuracy. Finally, a data-parallel inference method has been evaluated at scale using Apache Flink, a data stream processor for real-time predictions on high volume graph data streams. / Molti problemi nel mondo reale possono essere rappresentati come grafi poichè queste strutture dati consentono di modellare relazioni tra elementi. A causa del loro vasto uso, molti gruppi di ricerca hanno tentato di rappresentare i vertici in uno spazio a bassa dimensione, utile per poi poter utilizzare tecniche di apprendimento automatico. Le reti neurali per grafi sono state ampiamente utilizzate per via della loro capacità di codificare dipendenze tra vertici. Le reti neurali induttive recentemente introdotte, inoltre, hanno guadagnato popolarità poichè consentono di generare rappresentazioni di vertici aggregando altri vertici. In questo modo anche un nodo completamente nuovo può comunque essere rappresentato utilizzando i suoi nodi vicini. Sebbene questo approccio sia adatto per grafici dinamici, i sistemi ad oggi disponibili e gli algoritmi di addestramento si basano esclusivamente sulla continua elaborazione di grafi statici, un approccio che è stato criticato per i suoi elevati costi di calcolo. Questa tesi fornisce una soluzione a questo problema tramite un metodo efficiente per l’allenamento di reti neurali induttive basato su un’euristica per la selezione dei vertici. Viene inoltre descritto un metodo per eseguire predizioni in modo scalabile in tempo reale utilizzando Apache Flink, un sistema per l’elaborazione di grandi quantità di flussi di dati in tempo reale. / Grafer anses ofta vara ett utmärkt sätt att modellera komplexa problem i verkligheten eftersom de gör det möjligt att fånga relationer mellan objekt. På grund av deras allestädes närhet har grafinbäddningstekniker sysselsatt forskningsgrupper som undersöker hur hörn kan kodas in i ett lågdimensionellt latent utrymme, vilket är användbart för att sedan utföra maskininlärning. Nyligen har Graph Neural Networks (GNN) dominerat utrymmet för inbäddningsproduktion tack vare deras inneboende förmåga att koda latenta nodberoenden. Dessutom fick de nyinförda induktiva grafiska nervnäten stor popularitet för induktivt lärande och representerande nodbäddningar genom sammanlagda åtgärder i grannskapet. Även när en helt ny nod, osynlig under träning, visas i diagrammet, kan den fortfarande representeras ordentligt av dess angränsande noder. Även om detta tillvägagångssätt tycks vara lämpligt för dynamiska grafer, är tillgängliga system och träningsmetodologier agnostiska för dynamik och förlitar sig bara på att behandla fullständiga ögonblicksbilder i partier, en metod som har kritiserats för dess höga beräkningskostnader. Detta arbete ger en grundlig lösning på detta specifika problem via en effektiv prioriteringsbaserad metod för att välja repeterade prover som garanterar låg komplexitet och hög noggrannhet. Slutligen har en dataparallell inferensmetod utvärderats i skala med Apache Flink, en dataströmprocessor för realtidsprognoser för grafiska dataströmmar med hög volym.

Cette thèse réunit en trois articles mon intérêt éclectique pour la théorie des graphes. Le premier problème étudié est la conjecture de Erdos-Faber-Lovász: La réunion de k graphes complets distincts, ayant chacun k sommets, qui ont deux-à-deux au plus un sommet en commun peut être proprement coloriée en k couleurs. Cette conjecture se caractérise par le peu de résultats publiés. Nous prouvons qu’une nouvelle classe de graphes, construite de manière inductive, satisfait la conjecture. Le résultat consistera à présenter une classe qui ne présente pas les limitations courantes d’uniformité ou de régularité. Le deuxième problème considère une conjecture concernant la couverture des arêtes d’un graphe: Si G est un graphe simple avec alpha(G) = 2, alors le nombre minimum de cliques nécessaires pour couvrir l’ensemble des arêtes de G (noté ecc(G)) est au plus n, le nombre de sommets de G. La meilleure borne connue satisfaite par ecc(G) pour tous les graphes avec nombre d’indépendance de deux est le minimum de n + delta(G) et 2n − omega(racine (n log n)), où delta(G) est le plus petit nombre de voisins d’un sommet de G. Notre objectif a été d’obtenir la borne ecc(G) <= 3/2 n pour une classe de graphes la plus large possible. Un autre résultat associé à ce problème apporte la preuve de la conjecture pour une classe particulière de graphes: Soit G un graphe simple avec alpha(G) = 2. Si G a une arête dominante uv telle que G \ {u,v} est de diamètre 3, alors ecc(G) <= n. Le troisième problème étudie le jeu de policier et voleur sur un graphe. Presque toutes les études concernent les graphes statiques, et nous souhaitons explorer ce jeu sur les graphes dynamiques, dont les ensembles d’arêtes changent au cours du temps. Nowakowski et Winkler caractérisent les graphes statiques pour lesquels un unique policier peut toujours attraper le voleur, appellés cop-win, à l’aide d’une relation <= définie sur les sommets de ce graphe: Un graphe G est cop-win si et seulement si la relation <= définie sur ses sommets est triviale. Nous adaptons ce théorème aux graphes dynamiques. Notre démarche nous mène à une relation nous permettant de présenter une caractérisation des graphes dynamiques cop-win. Nous donnons ensuite des résultats plus spécifiques aux graphes périodiques. Nous indiquons aussi comment généraliser nos résultats pour k policiers et l voleurs en réduisant ce cas à celui d’un policier unique et un voleur unique. Un algorithme pour décider si, sur un graphe périodique donné, k policiers peuvent capturer l voleurs découle de notre caractérisation. / This thesis represents in three articles my eclectic interest for graph theory. The first problem is the conjecture of Erdos-Faber-Lovász: If k complete graphs, each having k vertices, have the property that every pair of distinct complete graphs have at most one vertex in common, then the vertices of the resulting graph can be properly coloured by using k colours. This conjecture is notable in that only a handful of classes of EFL graphs are proved to satisfy the conjecture. We prove that the Erdos-Faber-Lovász Conjecture holds for a new class of graphs, and we do so by an inductive argument. Furthermore, graphs in this class have no restrictions on the number of complete graphs to which a vertex belongs or on the number of vertices of a certain type that a complete graph must contain. The second problem addresses a conjecture concerning the covering of the edges of a graph: The minimal number of cliques necessary to cover all the edges of a simple graph G is denoted by ecc(G). If alpha(G) = 2, then ecc(G) <= n. The best known bound satisfied by ecc(G) for all the graphs with independence number two is the minimum of n + delta(G) and 2n − omega(square root (n log n)), where delta(G) is the smallest number of neighbours of a vertex in G. In this type of graph, all the vertices at distance two from a given vertex form a clique. Our approach is to extend all of these n cliques in order to cover the maximum possible number of edges. Unfortunately, there are graphs for which it’s impossible to cover all the edges with this method. However, we are able to use this approach to prove a bound of ecc(G) <= 3/2n for some newly studied infinite families of graphs. The third problem addresses the game of Cops and Robbers on a graph. Almost all the articles concern static graphs, and we would like to explore this game on dynamic graphs, the edge sets of which change as a function of time. Nowakowski and Winkler characterize static graphs for which a cop can always catch the robber, called cop-win graphs, by means of a relation <= defined on the vertices of such graphs: A graph G is cop-win if and only if the relation <= defined on its vertices is trivial. We adapt this theorem to dynamic graphs. Our approach leads to a relation, that allows us to present a characterization of cop-win dynamic graphs. We will then give more specific results for periodic graphs, and we will also indicate how to generalize our results to k cops and l robbers by reducing this case to one with a single cop and a single robber. An algorithm to decide whether on a given periodic graph k cops can catch l robbers follows from our characterization.