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.

Pour une bonne modélisation mathématique de l'occurrence de phénomènes aléatoires, part fondamentale de la discipline actuarielle, il est nécessaire d'employer des distributions multivariées permettant de capturer adéquatement les relations de dépendance présentes entre les phénomènes. Celles qu'offrent les champs aléatoires markoviens, une famille de modèle probabilistes graphiques, répondent à ce besoin, les relations de dépendance qu'elles introduisent se calquant à un arbre ou à un graphe. Les champs aléatoires markoviens misent ainsi sur les riches possibilités de topologies d'arbres et de graphes pour offrir cette même richesse en termes de dépendance. Une nouvelle famille de champs aléatoires markoviens arborescents, c'est-à-dire se basant sur des arbres, est proposée. Les membres de cette famille se distinguent par le fait qu'ils ont des distributions marginales fixes de Poisson, « fixes » dans le sens que la dépendance introduite n'a pas d'impact sur elles. Des distribution marginales fixes sont inhabituelles pour un champ aléatoire markovien, bien que généralement désirables pour fins de modélisation. Cette caractéristique est possible par l'encapsulation, dans les arêtes de l'arbre, de la dynamique de propagation induite par l'opérateur d'amincissement binomial. Cela mène également à une représentation stochastique intuitive des champs aléatoires markoviens de la famille, à des méthodes simples de simulation et à des expressions analytiques pour leur fonction de masses de probabilités conjointe et leur fonction génératrice de probabilités conjointe, notamment. Quantités importantes dans un contexte actuariel, la somme des composantes du champ aléatoire markovien, interprétable comme le nombre total d'événement s'étant produits, et les contributions individuelles de ces composantes sont étudiées en profondeur. Cette analyse passe notamment par l'établissement d'ordres stochastiques. À cet effet, un nouvel ensemble partiellement ordonné est défini pour comparer des arbres aux topologies différentes selon la distribution qu'ils induisent pour la somme, ce qui est, à notre connaissance, novateur dans le contexte de modèles pobabilistes graphiques. Est offerte une comparaison de cet ensemble partiellement ordonné avec quelques autres en lien avec la théorie spectrale des graphes. / For adequate mathematical modeling of random phenomena's occurrences, it is necessary to employ multivariate distributions that appropriately capture the existing dependence relations between those phenomena. The multivariate distributions granted by Markov random fields, a family of probabilistic graphical models, answer to this need, by encrypting the dependence scheme they introduce on a tree or a graph. Markov random fields thus leverage on the rich possibilities of tree shapes and graph shapes to provide these possibilities in terms of dependence schemes. We propose a new family of tree-based Markov random fields, characterized by their Poisson marginal distributions. The marginal distributions are also fixed, meaning they are not affected by the introduced dependence. This fixedness is uncommon for Markov random fields, while being desirable for modeling purposes. It is obtained from the encapsulation, in the edges of the tree, of the propagation dynamic induced by the binomial thinning operator. This leads to an intuitive stochastic representation of Markov random fields from the proposed family, simple methods of simulation, and analytic expressions for their joint probability mass function and their joint probability generating function, notably. Important quantities in an actuarial context are the sum of the components of the Markov random field, interpreted as the total number of occurring phenomena, and the individual contributions of these components. They are thoroughly studied, notably via the use of stochastic order relations. We incidently design a new partially ordered set (poset) of trees, in order to compare trees of different shapes based on the distribution of the sum they respectively convey. To our knowledge, this approach is innovative in the context of probabilistic graphical models. We provide comparisons of the newly defined poset with some other posets of trees fetched from spectral graph theory.

.

Cette thèse d'informatique s'inscrit dans le domaine de la recherche d'information (RI). Elle a pour objet la création d'un modèle de recherche utilisant les graphes pour en exploiter la structure pour la détection de similarités entre les documents textuels d'une collection donnée et une requête utilisateur en vue d'améliorer le processus de recherche d'information. Ces similarités sont dites « structurelles » et nous montrons qu'elles apportent un gain d'information bénéfique par rapport aux seules similarités directes. Le rapport de thèse est structuré en cinq chapitres. Le premier chapitre présente un état de l'art sur la comparaison et les notions connexes que sont la distance et la similarité. Le deuxième chapitre présente les concepts clés de la RI, notamment l'indexation des documents, leur comparaison, et l'évaluation des classements retournés. Le troisième chapitre est consacré à la théorie des graphes et introduit les notations et notions liées à la représentation par graphe. Le quatrième chapitre présente pas à pas la construction de notre modèle pour la RI, puis, le cinquième chapitre décrit son application dans différents cas de figure, ainsi que son évaluation sur différentes collections et sa comparaison à d'autres approches.

Dans ce travail de thèse, nous nous intéressons à plusieurs problèmes de théorie des graphes. Dans un premier temps, nous étudions différents problèmes de coupes et de multicoupes puis, dans un second temps, nous nous focalisons sur des problèmes de recherche de sous-graphes induits. Néanmoins, ces deux parties suivent la même ligne directrice : donner une vue d'ensemble de la complexité des problèmes en établissant leur NP-complétude ou en déterminant un algorithme polynomial de moindre complexité. Dans la première partie de la thèse, nous abordons les problèmes de coupes et de multicoupes. Tout d'abord, nous étudions la conséquence de l'ajout d'une contrainte de cardinalité à ces deux types de problèmes et démontrons leur NP- complétude dans le cas général. Puis, nous déterminons leur complexité dans plusieurs classes de graphes particuliers telles que les étoiles orientées et les chaînes en élaborant, pour les cas polynomiaux, différents algorithmes reposant principalement sur la programmation dynamique et l'utilisation de relaxations lagrangiennes. Nous généralisons ensuite cette approche en considérant les versions multicritères des problèmes de coupes et de multicoupes. Nous prouvons que ces derniers sont NP-complets même dans des topologies très simples comme les chaînes ou les cycles. Dans la seconde partie de ce mémoire, nous abordons des problèmes de recherche de sous-graphes induits. Nous nous intéressons principalement à la recherche d'arbres, de chaînes et de cycles induits couvrant un ensemble T de sommets donnés. Après avoir prouvé la NP-complétude des cas généraux, nous nous focalisons davantage sur les cas où la cardinalité de T est fixée. Nous donnons également plusieurs résultats structurels pour les graphes de maille suffisamment large.

En génie logiciel, les méthodes modernes de développement (ex. le MDA) s'appuient de manière cruciale sur les notions de modélisation et de transformation. Ces méthodes peuvent s'interpréter à l'aide de la théorie des graphes. La difficulté théorique réside aujourd'hui dans l'ajout sur ces graphes de données supplémentaires sur lesquelles il est nécessaire de pouvoir effectuer des calculs. Notre travail s'est focalisé sur le développement d'un cadre mathématique sûr afin d'appliquer ces transformations. Les théories des catégories (à travers le double pushout) et des types inductifs (fonctions de calcul très expressives) nous ont permis de donner une solution unifiée à ce problème dans laquelle une seule opération permet de travailler sur la structure et de calculer avec les attributs en définissant des fonctions entre graphes possédant une partie contravariante pour le travail sur les attributs. De plus, les propriétés usuelles des systèmes de récriture sont vérifiées.

L'objectif de cette thèse est le développement d'algorithmes et de modèles permettant l'optimisation d'itinéraires dans les réseaux routiers. Dans un premier temps, ce travail de recherche étudie le problème de l'interception d'un mobile dans un graphe. Dans ce contexte, l'objectif est de calculer un itinéraire optimal permettant de rejoindre une cible mobile dont la trajectoire est connue. Cette problématique est traitée pour plusieurs situations (un poursuivant/un objectif et plusieurs poursuivants/plusieurs objectifs) et pour plusieurs types de graphes (graphes statiques et graphes FIFO). Pour chaque cas, un algorithme de résolution est proposé et l'optimalité du résultat qu'il retourne est démontrée. De plus, un ensemble de simulations est réalisé afin de vérifier l'efficacité des algorithmes en termes de temps de calcul. Dans un deuxième temps, une nouvelle classe de graphes dynamiques est définie : les graphes dynamiques avec intervalles. La particularité de ces graphes est que le poids de chaque arc dépende du temps et qu'il est représenté par un intervalle. Pour ce nouveau type de graphes, le problème du plus court chemin est étudié. Ce problème peut être vu soit en tant que problème d'optimisation monocritère soit en tant que problème d'optimisation multicritère. Pour chaque cas, le problème est formulé et des approches pour la résolution sont proposées.

Cette thèse s'intéresse au probleme de la reconnaissance d'objets en présence d'une vaste base de modèles. L'indexation de modèles peut être décrite comme suit: étant donne un groupe d'indices image, extraire rapidement de la base de modèles, les modèles contenant le groupe d'indices. La combinatoire du paradigme classique d'appariement indices-modèles étant prohibitive dans ce cas, nous proposons une methode d'indexation par une technique de hachage de graphes. Nous décrivons d'abord les principes: codage d'image et des modelés sous une forme de graphes, gestion d'une base de modèles par tables hash-codees, comparaison de graphes sur la base de leur caractérisation polynomiale, accès a la base de modèles. Ensuite, nous décrivons le système mis en œuvre selon ces principes, et nous présentons quelques résultats d'expérimentation

Le travail de thèse présenté dans ce document traite de l'analyse de différentes propriétés liées à l'observabilité des systèmes à entrée inconnue par approche graphique. La simplicité de mise en œuvre de l'approche graphique permet de se défaire des difficultés numériques inhérentes aux approches géométrique et algébrique. Ce constat a conduit ces dernières décennies, à une série d'études structurelles basées sur l'approche graphique. <br />Parmi les propriétés encore non abordées graphiquement, l'observabilité forte traduit l'observabilité des variables d'état d'un système pour toute valeur d'entrée ainsi que l'observabilité conjointe de l'état et de l'entrée. Ces propriétés plus fortes que l'observabilité simple et le diagnostic nous ont paru utiles et pertinentes à étudier. En effet, les outils d'analyse développés peuvent s'avérer importants dans le cadre de la synthèse d'observateurs ou d'estimateurs d'entrées utile à la synthèse de lois de commandes tolérantes aux défauts ou robustes aux perturbations, ou encore quand il s'agit de vérifier si la propriété d'observabilité d'un système n'est pas altérée lorsqu'il est soumis à des perturbations, voire à des défauts d'amplitude trop importante pour être négligés. <br />Le manuscrit est structuré en trois parties. Dans la première, nous avons abordé l'analyse de différentes propriétés d'observabilité. Plus précisément, nous avons tout d'abord donné des conditions nécessaires et suffisantes d'observabilité de l'entrée et de l'état d'un système. Des conditions nécessaires et suffisantes pour l'observabilité forte d'une partie donnée des composantes de l'entrée et de l'état ont ensuite été établies. Le dernier résultat de cette partie concerne l'observabilité forte de tout l'état d'un système à entrée inconnue. Des conditions nécessaires et suffisantes ont été démontrées. <br />La seconde partie de cette thèse a consisté à étudier le problème du placement des capteurs afin de recouvrer des propriétés d'observabilité forte lorsque les conditions de la première partie ne sont pas vérifiées. Deux cas ont été traités. Le premier concerne la propriété d'observabilité forte d'une partie donnée de l'état. La stratégie de placement de capteurs consiste alors en une condition nécessaire permettant d'imposer qu'au moins une sortie du système soit sensible à chacune des composantes de l'état devant être fortement observables, puis en un système de relations graphiques, utilisé comme condition suffisante à ce qu'une configuration de capteurs assure l'observabilité forte des composantes de l'état choisies. Le second problème de placement de capteurs a pour objectif de rendre observables toutes les composantes de l'état. Le problème a été traité en trois étapes. Pour chacune d'elles, des conditions nécessaires et suffisantes sur le placement de capteurs ont été trouvées. Le nombre minimal de capteurs nécessaire et suffisant a aussi été déterminé. Les conditions trouvées sont fondées essentiellement sur des algorithmes classiques de la théorie des graphes.<br />La troisième partie traite de l'implémentation des résultats établis dans une boîte à outils dédiée à l'analyse structurelle (lisa) des systèmes linéaires et bilinéaires structurés. En premier lieu, les motivations qui ont conduit à la conception de cette boîte à outils sont exposées. La structure de lisa est ensuite présentée. Elle repose entièrement sur des algorithmes de base tels que la détermination des ensembles de successeurs et de prédécesseurs, le calcul des tailles de lien et de couplages maximaux entre deux ensembles de sommets et la caractérisation des ensembles de sommets essentiels dans des liens de taille maximale ou encore des séparateurs d'entrée et de sortie. Tous ces algorithmes ont des ordres de complexité polynomiaux. Nous avons montré comment en associant certains algorithmes de base, nous sommes arrivés à analyser l'observabilité de l'état et de l'entrée et à établir des conditions de détection et de localisation de défauts. Enfin, il est présenté des fonctions pouvant être rajoutées à lisa concernant différentes propriétés structurelles pour en faire un outil d'analyse plus complet.

On étudie divers problèmes concernant le n-cube. On décrit les exemples connus de (0,2) graphes (bipartis de diamètre 2 ou 3). On présente des constructions de (0,2) graphes. On étudie les (0,2) graphes avec des triangles. On montre comment construire certains des (0,2) graphes comme graphes de Cayley de groupes. On étudie les invariants immédiats du n-cube.