Nous introduisons d'abord la classe des graphes $k$-dégénérés qui est souvent utilisée pour modéliser des grands graphes épars issus du monde réel. Nous proposons de nouveaux algorithmes d'énumération pour ces graphes. En particulier, nous construisons un algorithme énumérant tous les cycles simples de tailles fixés dans ces graphes, en temps optimal.Nous proposons aussi un algorithme dont la complexité dépend de la taille de la solution pour le problème d'énumération des cliques maximales de ces graphes. Dans un second temps nous considérons les graphes en tant que systèmes distribués et nous nous intéressons à des questions liées à la notion de couplage lorsqu’aucune supposition n’est faite sur l'état initial du système, qui peut donc être correct ou incorrect. Dans ce cadre nous proposons un algorithme retournant une deux tiers approximation du couplage maximum.Nous proposons aussi un algorithme retournant un couplage maximal quand les communications sont restreintes de telle manière à simuler le paradigme du passage de message. Le troisième objet d'étude n'est pas directement lié à l'algorithmique de graphe, bien que quelques techniques classiques de ce domaine soient utilisées pour obtenir certains de nos résultats.Nous introduisons et étudions certaines familles de polytopes, appelées Zonotopes Primitifs, qui peuvent être décrits comme la somme de Minkowski de vecteurs primitifs. Nous prouvons certaines propriétés combinatoires de ces polytopes et illustrons la connexion avec le plus grand diamètre possible de l'enveloppe convexe de points à coordonnées entières à valeurs dans$[k]$, en dimension $d$. Dans un second temps,nous étudions des paramètres de petites instances de Zonotopes Primitifs, tels que leur nombre de sommets, entre autres. / We start by studying the class of $k$-degenerate graphs which are often used to model sparse real-world graphs. We focus one numeration questions for these graphs. That is,we try and provide algorithms which must output, without duplication, all the occurrences of some input subgraph. We investigate the questions of finding all cycles of some givensize and all maximal cliques in the graph. Ourtwo contributions are a worst-case output sizeoptimal algorithm for fixed-size cycleenumeration and an output sensitive algorithmfor maximal clique enumeration for this restricted class of graphs. In a second part weconsider graphs in a distributed manner. Weinvestigate questions related to finding matchings of the network, when no assumptionis made on the initial state of the system. Thesealgorithms are often referred to as selfstabilizing.Our two main contributions are analgorithm returning an approximation of themaximum matching and a new algorithm formaximal matching when communication simulates message passing. Finally, weintroduce and investigate some special families of polytopes, namely primitive zonotopes,which can be described as the Minkowski sumof short primitive vectors. We highlight connections with the largest possible diameter ofthe convex hull of a set of points in dimension d whose coordinates are integers between 0 and k.Our main contributions are new lower bounds for this diameter question as well as descriptions of small instances of these objects.

Cette thèse étudie la détection de communautés dans le contexte des réseaux sociaux. Un réseau social peut être modélisé par un graphe dans lequel les sommets représentent les membres et les arêtes représentent les relations entre les membres. En particulier, j'étudie quatre différentes définitions de communauté. D'abord, une structure en communautés peut être définie par une partition des sommets telle que tout sommet a une plus grande proportion de voisins dans sa partie que dans toute autre partie. Cette définition peut être adaptée pour l'étude d'une seule communauté. Ensuite, une communauté peut être vue comme un sous graphe tel que tout couple de sommets sont à distance 2 dans ce sous graphe. Enfin, dans le contexte des sites de rencontre, je propose d'étudier une définition de communauté potentielle dans le sens où les membres de la communauté ne se connaissent pas, mais sont liés par des connaissances communes. Pour ces trois définitions, j'étudie la complexité computationnelle et l'approximation de problèmes liés à l'existence ou la recherche de telles communautés dans les graphes. / This thesis deals with community detection in the context of social networks. A social network can be modeled by a graph in which vertices represent members, and edges represent relationships. In particular, I study four different definitions of a community. First, a community structure can be defined as a partition of the vertices such that each vertex has a greater proportion of neighbors in its part than in any other part. This definition can be adapted in order to study only one community. Then, a community can be viewed as a subgraph in which every two vertices are at distance 2 in this subgraph. Finally, in the context of online meetup services, I investigate a definition for potential communities in which members do not know each other but are related by their common neighbors. In regard to these proposed definitions, I study computational complexity and approximation within problems that either relate to the existence of such communities or to finding them in graphs.

Le but principal de cette thèse est de présenter des conditions suffisantes pour garantir l'existence de subdivisions dans les graphes dirigés. Bien que ce genre de questions soit assez bien maitrisé dans le cas des graphes non orientés, très peu de résultats sont connus sur le sujet des graphes dirigés. La conjecture la plus célèbre du domaine est sans doute celle attribuée à Mader en 1985 qui dit qu'il existe une fonction f tel que tout graphe dirigé de degré sortant minimal supérieur à f(k) contient le tournoi transitif sur k sommets comme subdivision. Cette question est toujours ouverte pour k=5. Cette thèse présente quelques résultats intermédiaires tendant vers cette conjecture. Il y est d'abords question de montrer l'existence de subdivisions de graphes dirigés autre que les tournois, en particulier les arborescences entrantes. Il y a aussi la preuve que les graphes dirigés de grand degré sortant contiennent des immersions de grand tournois transitifs, question qui avait été posée en 2011 par DeVos et al. En regardant un autre paramètre, on montre aussi qu'un grand nombre chromatique permet de forcer des subdivisions de certains cycles orientés, ainsi que d'autre structures, pour des graphes dirigés fortement connexes. Cette thèse présente également la preuve de la conjecture de Erd\H{o}s-Sands-Sauer-Woodrow qui dit que les tournois dont les arcs peuvent être partitionnés en k graphes dirigés transitifs peuvent être dominé par un ensemble de sommet dont la taille dépend uniquement de k. Pour finir, cette thèse présente la preuve de deux résultats, un sur l'orientation des hypergraphes et l'autre sur la coloration AVD,utilisant la technique de compression d'entropie. / The main purpose of the thesis was to exhibit sufficient conditions on digraphs to find subdivisions of complex structures. While this type of question is pretty well understood in the case of (undirected) graphs, few things are known for the case of directed graphs (also called digraphs). The most notorious conjecture is probably the one due to Mader in 1985. He asked if there exists a function f such that every digraph with minimum outdegree at least f(k) contains a subdivision of the transitive tournament on k vertices. The conjecture is still wide open as even the existence of f(5) remains open. This thesis presents some weakening of this conjecture. Among other results, we prove that digraphs with large minimum outdegree contain large in-arborescences. We also prove that digraphs with large minimum outdegree contain large transitive tournaments as immersions, which was conjectured by DeVos et al. in 2011. Changing the parameter, we also prove that large chromatic number can force subdivision of cycles and other structures in strongly connected digraphs. This thesis also presents the proof of the Erd\H{o}s-Sands-Sauer-Woodrow conjecture that states that the domination number of tournaments whose arc set can be partitioned into k transitive digraphs only depends on k. The conjecture, asked in 1982, was still open for k=3. Finally this thesis presents proofs for two results, one about orientation of hypergraphs and the other about AVD colouring using the recently developed probabilistic technique of entropy compression.

Ces dernières années ont connu un regain d'intérêt pour l'utilisation des graphes comme moyen fiable de représentation et de modélisation des données, et ce, dans divers domaines de l'informatique. En particulier, pour les grandes masses de données, les graphes apparaissent comme une alternative prometteuse aux bases de données relationnelles. Plus particulièrement, le recherche de sous-graphes s'avère être une tâche cruciale pour explorer ces grands jeux de données. Dans cette thèse, nous étudions deux problématiques principales. Dans un premier temps, nous abordons le problème de la détection de motifs dans les grands graphes. Ce problème vise à rechercher les k-meilleures correspondances (top-k) d'un graphe motif dans un graphe de données. Pour cette problématique, nous introduisons un nouveau modèle de détection de motifs de graphe nommé la Simulation Relaxée de Graphe (RGS), qui permet d’identifier des correspondances de graphes avec un certain écart (structurel) et ainsi éviter le problème de réponse vide. Ensuite, nous formalisons et étudions le problème de la recherche des k-meilleures réponses suivant deux critères, la pertinence (la meilleure similarité entre le motif et les réponses) et la diversité (la dissimilarité entre les réponses). Nous considérons également le problème des k-meilleures correspondances diversifiées et nous proposons une fonction de diversification pour équilibrer la pertinence et la diversité. En outre, nous développons des algorithmes efficaces basés sur des stratégies d’optimisation en respectant le modèle proposé. Notre approche est efficiente en terme de temps d’exécution et flexible en terme d'applicabilité. L’analyse de la complexité des algorithmes et les expérimentations menées sur des jeux de données réelles montrent l’efficacité des approches proposées. Dans un second temps, nous abordons le problème de recherche agrégative dans des documents XML. Pour un arbre requête, l'objectif est de trouver des motifs correspondants dans un ou plusieurs documents XML et de les agréger dans un seul agrégat. Dans un premier temps nous présentons la motivation derrière ce paradigme de recherche agrégative et nous expliquons les gains potentiels par rapport aux méthodes classiques de requêtage. Ensuite nous proposons une nouvelle approche qui a pour but de construire, dans la mesure du possible, une réponse cohérente et plus complète en agrégeant plusieurs résultats provenant de plusieurs sources de données. Les expérimentations réalisées sur plusieurs ensembles de données réelles montrent l’efficacité de cette approche en termes de pertinence et de qualité de résultat. / Recent years have witnessed a growing renewed interest in the use of graphs as a reliable means for representing and modeling data. Thereby, graphs enable to ensure efficiency in various fields of computer science, especially for massive data where graphs arise as a promising alternative to relational databases for big data modeling. In this regard, querying data graph proves to be a crucial task to explore the knowledge in these datasets. In this dissertation, we investigate two main problems. In the first part we address the problem of detecting patterns in larger graphs, called the top-k graph pattern matching problem. We introduce a new graph pattern matching model named Relaxed Graph Simulation (RGS), to identify significant matches and to avoid the empty-set answer problem. We formalize and study the top-k matching problem based on two classes of functions, relevance and diversity, for ranking the matches according to the RGS model. We also consider the diversified top-k matching problem, and we propose a diversification function to balance relevance and diversity. Moreover, we provide efficient algorithms based on optimization strategies to compute the top-k and the diversified top-k matches according to the proposed model. The proposed approach is optimal in terms of search time and flexible in terms of applicability. The analyze of the time complexity of the proposed algorithms and the extensive experiments on real-life datasets demonstrate both the effectiveness and the efficiency of these approaches. In the second part, we tackle the problem of graph querying using aggregated search paradigm. We consider this problem for particular types of graphs that are trees, and we deal with the query processing in XML documents. Firstly, we give the motivation behind the use of such a paradigm, and we explain the potential benefits compared to traditional querying approaches. Furthermore, we propose a new method for aggregated tree search, based on approximate tree matching algorithm on several tree fragments, that aims to build, the extent possible, a coherent and complete answer by combining several results. The proposed solutions are shown to be efficient in terms of relevance and quality on different real-life datasets

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Dans de multiples domaines, des structures qui semblent à première vue très simples sont très mal comprises. Un exemple qui nous vient vite à l'esprit, c'est la structure de l'ADN qui n'est qu'une suite d'un alphabet de quatre bases azotées, mais dont la combinaison cache encore de nombreux mystères. Dans ce mémoire nous nous sommes attardés à la rotation, la réflexion et à la permutation des lettres d'un mot. Si l'on ne prend que la rotation, l'ensemble de tous les mots que l'on peut fabriquer par rotation des lettres d'un mot donné est appelé collier. Cette notion mathématique bien connu revient, dans le concret, à écrire notre mot donné sur les perles d'un collier et à constater que le fait de tourner le collier autour de notre cou ne change pas l'objet lui-même. En ajoutant la réflexion à la rotation, on obtient les bracelets. Toutefois, lorsque l'on combine la permutation des lettres de l'alphabet aux bracelets ou aux colliers, on obtient des objets beaucoup moins connus et moins bien compris. Au cours de ce mémoire, nous nous sommes donc intéressés aux mots dont la permutation des lettres est combinée à d'autres actions. Deux principaux problèmes ont occupés nos recherches: le comptage de ces objets ainsi que l'énumération de ceux-ci. Ces deux avenues ont été fructueuses et nous ont donné de nouveaux résultats. Nous avons de plus trouvé divers domaines où ces objets semblent être un modèle pertinent et où nos résultats pourraient s'appliquer. / Simple structures seem to emerge from many different sciences. However, we still have a limited undertanding of those structures. A good exemple is DNA structure which is simply a series of nitrogenous bases taken from a four letter alphabet. Unfortunately, even if its structure is very simple, DNA still keeps many secrets to the scientific community. A better understanding of basic structures seems to be the basis to a better understanding of our environment. This is why we have focused on words under the action of rotation, reflexion and permutation of letters. Words under the action of rotation are called necklaces and are well studied. If the reflection is added to necklaces, bracelets are obtained. However, if we combine alphabet permutation with rotation and/or reflection, less understood objects are obtained. We focused on two major problems: counting objets and generating them. In both directions we have found interesting new results. We also found some fields in which our results could contribute.

Les problèmes de recherche sur un graphe peuvent être exprimés sous la forme d’un jeu où un ensemble de chercheurs tentent de capturer un ensemble de fugitifs. Lorsqu’un tel jeu est joué en alternance par les deux ensembles de joueurs, nous parlons alors de jeux des policiers et des voleurs (« Cops and Robbers games ») ou plus simplement de jeux policiers-voleurs. Nowakowski et Winkler [28], et indépendamment Quilliot [45], ont introduit la première version des jeux policiers-voleurs dans laquelle un seul policier tente de capturer un seul voleur, les deux se déplaçant à tour de rôle vers des sommets adjacents de leurs positions courantes. Ils ont notamment proposé une jolie caractérisation des graphes gagnants pour le policier qui est basée sur l’existence d’un démantèlement particulier des sommets du graphe ; un démantèlement consistant à retirer un à un les sommets du graphe suivant une certaine règle. Cette caractérisation par démantèlement est par ailleurs intéressante puisqu’elle donne directement un algorithme polynomial de type diminuer pour régner pour résoudre le problème du policier et du voleur. Dans ce mémoire, nous proposons une nouvelle version d’un jeu policier-voleur dans laquelle le voleur se déplace arbitrairement vite dans le graphe et dans laquelle le policier possède une zone de surveillance qui limite le voleur dans ses déplacements. Nous caractérisons les graphes gagnants pour le policier dans ce nouveau jeu en utilisant un concept de démantèlement d’un graphe, similaire à celui de Nowakowski et Winkler [28], Quilliot [45], mais adapté aux conditions de notre nouveau jeu. Nous devons notamment généraliser la définition d’un graphe classique à celle d’un graphe clandestin, qui possède un ensemble de sommets clairs et un ensemble de sommets sombres, afin d’obtenir notre caractérisation par démantèlement. Nous donnons par ailleurs un algorithme qui permet de bâtir une stratégie monotone gagnante pour le policier en nous assurant que le policier sécurise de plus en plus de sommets à chaque tour. / Graph searching problems can be expressed as a game where a group of searchers is trying to capture a group of fugitives on a graph. When players move alternately in such a game, we are then referring to games of Cops and Robbers. Nowakowski and Winkler [28], and independently Quilliot [45], introduced the very first version of cops and robbers games in which a single cop tries to capture a single robber, both players moving alternately from their current positions to neighboring vertices. They notably proposed a very nice characterization of graphs that are winning for the cop, which is based on a particular dismantling scheme of the graph’s vertices; a dismantling scheme consisting in removing one by one each vertex of the graph by following a given rule. This dismantling-like characterization is furthermore interesting since it directly yields a divide-and-conquer algorithm that is polynomial, to solve the cop and robber problem. In this master thesis, we propose a new version of cops and robbers games in which the robber is able to move arbitrarily fast in the graph and in which the cop has a watching area that limits the robber’s moving capabilities. We characterize the cop-winning graphs for this new game by using some dismantling scheme similar to the one given by Nowakowski and Winkler [28], Quilliot [45], but that better fits our new game’s conditions. To obtain this dismantling-like characterization, we particularly need to generalize the definition of a classical graph to an undergrounded graph, whose vertices are split in a set of light vertices and a set of dark vertices. We also give an algorithm that provides a monotonous cop-winning strategy by making sure the cop is securing more and more vertices at each turn.

La modélisation de phénomènes biologiques qui impliquent un très grand nombre d'unités pose toujours un défi. De nombreux modèles présentent une vision globale de la dynamique moyenne du phénomène sous la forme d'un système d'équations différentielles ordinaires. C'est le cas notamment du modèle de Wilson-Cowan, qui décrit l'activité qui se propage dans un réseau de neurones biologiques. Une limite importante de ce modèle est qu'il néglige d'éventuelles corrélations entre les états de différents neurones. L'objectif premier de ce mémoire est ainsi de le généraliser afin de décrire de telles corrélations. On veut aussi mieux en comprendre les fondements mathématiques et les liens qu'il a avec des modèles semblables utilisés en épidémiologie et en écologie. Pour s'attaquer à ce problème, on construit une chaîne de Markov en temps continu qui décrit l'évolution des états des nœuds d'un graphe, et qui peut ainsi modéliser un phénomène biologique d'un point de vue microscopique. Étant donné le très grand nombre de nœuds que comporte le graphe, ce modèle microscopique est difficile à analyser. À partir du processus stochastique, on obtient alors par un moyennage un système d'équations différentielles ordinaires afin de décrire la dynamique sur le graphe d'un point de vue macroscopique. Deux applications de cette méthode sont alors présentées : l'une en épidémiologie et l'autre en neurosciences. On se concentre particulièrement sur l'application en neurosciences, qui permet de décrire la dynamique d'un réseau de neurones biologiques et de généraliser le modèle de Wilson-Cowan. En effet, on arrive à proposer deux nouveaux systèmes qui sont des extensions de ce modèle, puisqu'elles permettent de considérer des corrélations entre les états de différents neurones. On présente finalement un exemple dans lequel le comportement dynamique de l'une de ces extensions est plus près du comportement du processus stochastique que celui du modèle de Wilson-Cowan. / Modeling biological phenomena that involve a very large number of individual units is always a challenge. In this context, many models consist in a system of ordinary differential equations that gives an overview of the mean dynamics of a phenomenon. Among these is the Wilson-Cowan model, which describes the activity of a biological neural network. An important weakness of this model is that it neglects all possible correlations between the states of different neurons. The main goal of this thesis is to generalize Wilson-Cowan's model to describe such correlations. We also seek to get a better understanding of its mathematical foundations, as well as its links with other models used in epidemiology and ecology. To tackle this problem, we construct a continuous-time Markov chain to describe the evolution of the states of the nodes of a large graph. Such a process can then model a biological phenomenon from a microscopic point of view. Since the size of the graph is very large, this microscopic model is hard to analyze. Hence, from the stochastic process, we use an averaging method to obtain a system of ordinary differential equations which describes the dynamics on the graph from a macroscopic point of view. We show two applications of this method : one in epidemiology and the other in neuroscience. We focus on the application in neuroscience, which leads to a description of the dynamics a biological neural network and generalizes Wilson-Cowan's model. Indeed, we introduce two new systems which are extensions of this model since they can describe correlations between the states of different neurons. Finally, we present an example where the behavior of the stochastic process is closer to the dynamical behavior of one of the extensions than that of Wilson-Cowan's model.

L'étude du spectre des réseaux complexes est un problème riche, ayant une longue histoire et des applications dans de nombreux domaines. La densité spectrale limite d'ensembles de graphes aléatoires, en particulier, fournit une information globale importante pour la compréhension de la topologie et du comportement des modèles de réseaux souvent utilisés comme version jouet des réseaux réels. Si la densité spectrale des réseaux denses et non corrélés est en général bien comprise, celle des réseaux extrêmement creux reste un problème difficile. Bien que plusieurs propriétés de la densité spectrale des réseaux extrêmement creux aient pu être établies, une forme fermée pour celle-ci échappe toujours aux chercheurs et chercheuses. C'est à ce problème que s'attaque ce mémoire. Dans un premier temps, une méthode combinatoire pour le calcul de la densité spectrale et de ses moments est développée. Elle est ensuite appliquée au modèle d'Erdős-Rényi dense avec succès, reproduisant le résultat classique qu'est la loi du demi-cercle de Wigner. Finalement, la méthode est utilisée pour l'étude de la densité spectrale des réseaux extrêmement creux. Sont obtenus ainsi une forme fermée pour la densité spectrale des graphes réguliers aléatoires, la preuve de propriétés importantes de la densité spectrale du modèle d'Erdős-Rényi extrêmement creux, une explication de la présence de pics discontinus dans la densité, une correction pour le cœur de celle-ci, ainsi qu'une forme asymptotique pour ses extrémités conjecturée comme vraie pour tous les modèles de réseaux creux et non corrélés. Malgré tout, une forme fermée est toujours inconnue. / The study of the spectra of complex networks is a rich problem with a long history and varied applications. In particular, the limiting spectral density of random graph ensembles provides important global information on the topology and behavior of the network models often used as toy versions of real networks. Though the spectral density of dense, uncorrelated networks is generally well understood, that of extremely sparse networks remains a difficult problem. Despite the fact that many properties of the spectral density of extremely sparse networks have been established, a closed form still evades researchers. It is that problem which this thesis tackles. First, a combinatorial approach to the calculation of the spectral density and its moments is developed. It is then successfully applied to the dense Erdős-Rényi model, reproducing the classical Wigner semicircle law. Finally, the approach is employed to study the spectral density of extremely sparse networks. Results obtained this way include a closed form for the spectral density of random regular graphs, proofs of important properties of the spectral density of extremely sparse Erdős-Rényi random graphs, an explanation of the presence of discontinuous peaks in the density, a correction for its bulk and an asymptotic form for its extremities, which is conjectured to hold for all models of sparse, uncorrelated networks. However, a closed form remains unknown.

En développant des outils pour étudier les chaînes de Markov réversibles ainsi qu’une classification des arbres par leur constante de branchement, on pourra traiter du problème du retour à l’origine d’une marche aléatoire sur un arbre. Ces mêmes outils nous permettront d’étudier la percolation sur les arbres. En particulier, il sera possible de relier explicitement la constante de branchement d’un arbre à la valeur critique pour la marche aléatoire biaisée et à la valeur critique de percolation. Par la suite, on détaille comment en arriver à des bornes intéressantes pour deux valeurs critiques du processus de contact sur l’arbre homogène, un résultat de Pemantle. On généralise aussi un résultat de Schinazi qui nous permet de trouver une borne inférieure pour la valeur critique de survie du processus de contact sur le recouvrement universel d’un graphe fini.