Les réseaux complexes sont un paradigme de plus en plus utilisé pour modéliser la structure des systèmes complexes. Les connexions neuronales ou la transmission de maladies entre différents humains sont des exemples typiques de ce genre de structure. L'un des défis de la science des réseaux est de fournir des outils permettant de les analyser, notamment par le développement de modèles aléatoires de réseaux. Ces modèles permettent de supposer un hasard sous-jacent dans la construction d'un ensemble de réseaux, tout en conservant certaines propriétés importantes. En comparant un réseau mesuré dans un système réel à ceux issus d'un ensemble généré à l'aide d'un modèle aléatoire, il est possible d'identifier des propriétés ne pouvant pas s'expliquer par le hasard et ainsi mettre en évidence la présence de processus de formation cachés. Ce projet de maîtrise vise à développer une famille de modèles aléatoires qui se base sur une propriété de centralité des nœuds nommée la décomposition en oignon. Des algorithmes sont développés afin d'échantillonner des réseaux issus de différents ensembles. On montre que ces algorithmes peuvent construire les échantillons sans aucun biais dans le cas où les contraintes sont conservées exactement, et que les échantillons construits sont représentatifs des ensembles dans le cas où les contraintes sont conservées en moyenne sur l'ensemble. Finalement, on compare les nouveaux ensembles développés avec des ensembles déjà existants afin d'obtenir une nouvelle intuition sur le rôle que joue l'organisation à moyenne échelle sur les propriétés des réseaux complexes réels. / Complex networks are recent tools with a growing popularity that are used to study the structure of complex systems. Examples of these structures are the connections between neurons or the transmission of diseases along social ties in a population, both represented as links between nodes. A major challenge in network science is to develop tools that allow to understand these complex structures. Among these tools is the use of random graph models, which allow us to build ensembles of networks that share a common property while also having an underlying randomness. By comparing a network obtained from real data to a random graph model, it is possible to identify certain properties that cannot be explained by randomness, thereby highlighting the existence of some hidden formation process. This project aims to develop a family of random graph models that are based on a centrality property called the Onion Decomposition. Algorithms to create representative samples of these models are proposed. We show that the algorithms build the sample with no bias in the case of exact constraints, or with the proper bias in the case where the constraints are kept on average. Finally, we compare the new ensembles to ensembles in the literature to obtain a better intuition on the role of meso-scale organization in real complex networks.

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.

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.

Cabri-graphes est un environnement logiciel, destine aux chercheurs, étudiants et enseignants en théorie des graphes. La pratique de cette discipline amené a recourir a des représentations graphiques, afin de visualiser les structures mathématiques mises en œuvre; ceci dans le but de les manipuler, de leur appliquer concrètement certaines transformations, afin de vérifier une propriété, conforter ou infirmer une idée, une conjecture. Cette pratique, menée sur un cahier de brouillon traditionnel, souffre de limitations et les résultats ne sont que faiblement garantis. C'est pourquoi nous avons étudié et réalisé un logiciel, alliant la simplicité d'usage d'un environnement interactif à la puissance de l'ordinateur. Cette thèse présente l'ensemble des concepts mathématiques et de génie logiciel ayant servi a la réalisation de ce projet. Nous donnons en particulier l'implémentation d'un générateur de graphes aléatoires, ainsi que quelques applications motivées et réalisées grâce à cet environnement logiciel

Cette thèse porte sur la modélisation mathématique de la contagion de défaut. Une première approche est donnée par les modèles à forme réduite, dans laquelles les occurrences de défaut son modelises par des instants d'arrivée d'un processus ponctuel marqué. On propose une approche rigoureuse de la calibration de ces modeles a partir de prix de produits dérivés de crédit, en utilisant des méthodes de projection Markovienne et de contrôle d'intensité. Une deuxième approche est celle des modèles structurels de risque de défaut: on modélis les liens économiques entre bilans des differentes entreprises comme un réseau de contreparties. Dans de tel réseau, un choc macroéconomique, qui induit des pertes initiales et le défaut de quelques institutions, peut etre amplifié par une contagion, via des cascades d'illiquidité ou d'insolvabilité, qui engendrent alors des défauts à grande échelle. Les principaux types de contagion sont l'illiquidité et l'insolvabilité. En modélisant le réseau financier par un graphe aléatoire pondéré et orienté on obtient des résultats asymptotiques pour l'amplitude de la contagion dans un grand réseau financier. On aboutit en particulier à une expression analytique pour la fraction finale de défauts en fonction des caractéristiques du réseau. Ces résultats donnent un critère de robustesse d'un grand réseau financier et peuvent s'appliquer dans le cadre des stress tests effectués par les régulateurs. Enfin, on étudie la taille et la dynamique des cascades d'illiquidité dans les marchés de gré a gré et l'impact, en terme de risque systémique, dû à l'introduction d'une chambre de compensation pour les Credit default swaps (CDS).

Dans la limite "diluée" où les nombres d'arêtes et de sommets divergent de manière comparable, il est naturel d'espérer que divers invariants classiques en théorie des graphes seront essentiellement déterminés par la seule "géométrie locale" du graphe -- c'est à dire, informellement, par l'aspect d'une boule de petit rayon autour d'un "sommet typique". Cette heuristique a pour origine l'étude des systèmes de particules en physique statistique, où sous certaines conditions, les contributions microscopiques provenant de sites suffisamment éloignés peuvent être considérées comme mutuellement indépendantes dans le calcul des grandeurs macroscopiques fondamentales du système. Mathématiquement, cette précieuse absence d'intéractions à longue portée peut se décrire rigoureusement à l'aide d'une propriété topologique : la continuité de l'invariant considéré vis-à-vis de la convergence locale faible des graphes. Tout invariant pour lequel on peut établir une telle continuité admettra aussitôt une limite déterministe le long de la plupart des suites de graphes aléatoires classiques, et pourra être efficacement approximé par des algorithmes locaux et distribués, indépendamment de la taille totale du système. Dans cette thèse, nous établissons la continuité de quatre invariants de graphes qui jouent un rôle essentiel en théorie comme dans les applications : la distribution spectrale empirique, la dimension du noyau de la matrice d'adjacence, la taille d'un couplage maximum, et le polynôme énumérant certaines familles de sous-graphes couvrants. Plus précisément, nous montrons qu'il existe une unique manière localement cohérente d'étendre chacune de ces notions aux limites locales faibles de graphes finis, et que ce prolongement est continu. Pour les modèles de graphes aléatoires classiques, les équations de cohérence locale se simplifient en une équation aux distributions que nous résolvons explicitement. Cela conduit à de nouvelles formules asymptotiques, ainsi qu'à la simplification, l'unification et la généralisation de divers résultats jusqu'alors isolés.

Cette thèse est consacrée à l'étude de trois modèles combinatoires intervenant dans la théorie des probabilités. Nous nous intéressons tout d'abord à la hauteur d'arbres de fragmentation. À mesure de dislocation fixée, deux régimes bien différents peuvent apparaître selon la capacité des sommets : au-delà d'une capacité critique, les hauteurs ont même asymptotique tandis que, en deçà de ce paramètre critique, les arbres sont de plus en plus hauts à mesure que le seuil de rupture diminue. Nous présentons ensuite des résultats obtenus avec Nicolas Curien sur le quadtree. Nous explicitons les comportements asymptotiques des coûts moyens des requêtes partielles. La théorie des fragmentations joue encore un rôle clé. Nous étudions enfin les grands graphes aléatoires, critiques pour le modèle de configuration. Sous certaines hypothèses, nous prouvons que, correctement remises à l'échelle, les suites des tailles des composantes connexes de ces graphes convergent en un certain sens vers une suite aléatoire non triviale que nous caractérisons. La situation est bien différente selon que la loi des degrés d'un sommet a un moment d'ordre 3 fini ou est une loi de puissance d'exposant compris entre 3 et 4.

La richesse de la programmation par contraintes repose sur la très large variété des algorithmes qu’elle utilise en puisant dans les grands domaines de l’Intelligence Artificielle, de la Programmation Logique et de la Recherche Opérationnelle. Cependant, cette richesse, qui offre aux spécialistes une palette quasi-illimitée de configurations possibles pour attaquer des problèmes combinatoires, devient une frein à la diffusion plus large du paradigme, car les outils actuels sont très loin d’une boîte noire, et leur utilisation suppose une bonne connaissance du domaine, notamment en ce qui concerne leur paramétrage. Dans cette thèse, nous proposons d’analyser le comportement des contraintes de cardinalité avec des modèles probabilistes et des outils de dénombrement, pour paramétrer automatiquement les solveurs de contraintes : heuristiques de choix de variables et de choix de valeurs et stratégies de recherche. / The main asset of constraint programming is its wide variety of algorithms that comes from the major areas of artificial intelligence, logic programming and operational research. It offers specialists a limitless range of possible configurations to tackle combinatorial problems, but it becomes an obstacle to the wider diffusion of the paradigm. The current tools are very far from being used as a black-box tool, and it assumes a good knowledge of the field, in particular regarding the parametrization of solvers.In this thesis, we propose to analyze the behavior of cardinality constraints with probabilistic models and counting tools, to automatically parameterize constraint solvers: heuristics of choice of variables and choice of values and search strategies.

Les réseaux sont très largement utilisés dans de nombreux domaines scientifiques afin de représenter les interactions entre objets d'intérêt. Ainsi, en Biologie, les réseaux de régulation s'appliquent à décrire les mécanismes de régulation des gènes, à partir de facteurs de transcription, tandis que les réseaux métaboliques permettent de représenter des voies de réactions biochimiques. En sciences sociales, ils sont couramment utilisés pour représenter les interactions entre individus. Dans le cadre de cette thèse, nous nous intéressons à des méthodes d'apprentissage non supervisé dont l'objectif est de classer les noeuds d'un réseau en fonction de leurs connexions. Il existe une vaste littérature se référant à ce sujet et un nombre important d'algorithmes ont été proposés depuis les premiers travaux de Moreno en 1934. Notre point de départ est le modèle à blocs stochastiques, Stochastic Block Model (SBM) (Nowicki et Snijders, 2001) en anglais, qui permet la recherche de classes topologiques hétérogènes. Nous considérons un contexte Bayésien et proposons un algorithme de type variational Bayes pour approcher la loi a posteriori des paramètres. Cette approche permet d'obtenir un nouveau critère de sélection de modèles afin d'estimer le nombre de composantes dans un réseau. Par ailleurs, il apparaît que SBM ainsi que la plupart des modèles existants de classification sont limités puisqu'ils partitionnent les noeuds dans des classes disjointes. Or, de nombreux objets d'étude dans le cadre d'applications réelles sont connus pour appartenir à plusieurs groupes en même temps. Par exemple, en Biologie, des protéines appelées moonlighting proteins en anglais ont plusieurs fonctions dans les cellules. Nous introduisons donc un nouveau modèle de graphe aléatoire que nous appelons modèle à blocs stochastiques chevauchants, Overlapping Stochastic Block Model (OSBM) en anglais. Il autorise les noeuds d'un réseau à appartenir à plusieurs groupes simultanément et peut prendre en compte des topologies de connexion très différentes. Deux algorithmes d'estimation sont proposés ainsi qu'un critère de sélection de modèles.

Cette thèse s'inscrit dans la théorie des matrices aléatoires, à l'intersection avec la théorie des probabilités libres et des algèbres d'opérateurs. Elle s'insère dans une démarche générale qui a fait ses preuves ces dernières décennies : importer les techniques et les concepts de la théorie des probabilités non commutatives pour l'étude du spectre de grandes matrices aléatoires. On s'intéresse ici à des généralisations du théorème de liberté asymptotique de Voiculescu. Dans les Chapitres 1 et 2, nous montrons des résultats de liberté asymptotique forte pour des matrices gaussiennes, unitaires aléatoires et déterministes. Dans les Chapitres 3 et 4, nous introduisons la notion de fausse liberté asymptotique pour des matrices déterministes et certaines matrices hermitiennes à entrées sous diagonales indépendantes, interpolant les modèles de matrices de Wigner et de Lévy.