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.

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.

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.

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.

Thèse ou mémoire avec insertion d'articles. / Le but de la science des réseaux est de modéliser les systèmes complexes et d'expliquer leurs propriétés émergentes, telles que la propagation d'épidémies ou la formation de la mémoire dans le cerveau. Cependant, ces systèmes complexes peuvent parfois atteindre des tailles immenses, rendant leur étude difficile. La théorie spectrale des graphes est un outil majeur dans l'étude de tels réseaux, car les valeurs propres d'un réseau sont relativement faciles à calculer en plus de nous renseigner sur sa structure globale et sa dynamique à grande échelle. L'objectif de ce projet de maîtrise était d'analyser l'effet de propriétés structurelles, souvent négligées, présentes dans les réseaux de neurones sur le spectre des graphes qui leur sont associés. Plus spécifiquement, les propriétés étudiées sont la directionnalité, l'inhibition, le principe de Dale et la densité. Pour cela, différentes techniques de théorie des graphes ont été utilisées afin de créer des graphes aléatoires respectant les propriétés étudiées. Ensuite, une analyse spectrale approfondie de ces graphes aléatoires a été réalisée afin de déterminer l'effet des propriétés structurelles des réseaux de neurones sur leur spectre. On a d'abord abordé le problème à l'aide des théories mathématiques existantes, mais les calculs analytiques se sont avérés ardus et moins instructifs que prévu. Afin de combler ces lacunes, une analyse numérique a été réalisée. L'effet majeur provoqué par les propriétés structurelles étudiées est la présence d'une transition dans le spectre. La distribution de la valeur propre ayant la plus grande norme passe d'une distribution réelle à une distribution complexe pour ensuite revenir à une distribution réelle en fonction de la fraction d'inhibiteurs dans le réseau. La distribution changeante de la valeur propre dominante a alors été caractérisée numériquement, ce qui a permis l'identification et l'analyse de nombreuses autres propriétés empiriques. La transition dans le spectre, étant particulièrement significative dans les réseaux de taille finie, a donc une grande influence sur le comportement des réseaux de neurones et est directement influencée par les propriétés structurelles introduites. / The goal of network science is to model complex systems and explain their emergent properties, such as epidemic spreading or memory formation in the brain. However, these complex systems can sometimes reach immense sizes, making their study challenging. Graph spectral theory is a significant tool in the investigation of such networks, as the eigenvalues of a network are relatively easy to compute and provide insights into its overall structure and large-scale dynamics. The objective of this master's project was to analyze the effect of often overlooked structural properties present in neural networks on the spectrum of the associated graphs. More specifically, the studied properties include directionality, inhibition, Dale's principle, and density. To achieve this, various graph theory techniques were employed to generate random graphs that adhere to the studied properties. Subsequently, an in-depth spectral analysis of these random graphs was conducted to determine the impact of the structural properties of neural networks on their spectrum. Initially, the problem was approached using existing mathematical theories, but the analytical calculations proved to be challenging and less informative than anticipated. To address these gaps, a numerical analysis was performed. The major effect induced by the studied structural properties is the presence of a transition in the spectrum. The distribution of the eigenvalue with the largest norm transitions from a real distribution to a complex distribution, and then returns to a real distribution based on the fraction of inhibitors in the network. The changing distribution of the dominant eigenvalue was numerically characterized, wich enabled the empirical observation and analysis of many other properties. The spectrum transition, particularly significant in networks of finite size, thus has a substantial influence on the behavior of neural networks and is directly influenced by the introduced structural properties.

.