Cette thèse est consacrée à l'étude du comportement asymptotique de grands graphes et arbres aléatoires. Le premier modèle étudié est un modèle de graphe aléatoire inhomogène introduit par Bo Söderberg. Un chapitre de ce manuscrit est consacré à l'étude asymptotique de la taille des composantes connexes à proximité de la fenêtre critique, en le reliant à la longueur des excursions d'un mouvement brownien avec dérive parabolique, étendant les résultats obtenus par Aldous. Le chapitre suivant est consacré à un processus de graphes aléatoires proposé par Itai Benjamini, défini ainsi : les arêtes sont ajoutées indépendamment, à taux fixe. Lorsqu'un sommet atteint le degré k, toutes les arêtes adjacentes à ce sommet sont immédiatement supprimées. Ce processus n'est pas croissant, ce qui empêche d'utiliser directement certaines approches usuelles. L'utilisation de limites locales permet de montrer la présence (resp. l'absence) d'une composante géante à certaines étapes dans le cas k>=5 (resp. k<=3). Dans le cas k=4, ces résultats permettent de caractériser la présence d'une composante géante en fonction du caractère surcritique ou non d'un processus de branchement associé. Dans le dernier chapitre est étudiée la hauteur d'un arbre de Lyndon associé à un mot de Lyndon choisi uniformément parmi les mots de Lyndon de longueur n, prouvant que cette hauteur est approximativement c ln n, avec c=5,092... la solution d'un problème d'optimisation. Afin d'obtenir ce résultat, nous couplons d'abord l'arbre de Lyndon à un arbre de Yule, que nous étudions ensuite à l'aide de techniques provenant des théories des marches branchantes et des grandes déviations. / This thesis is dedicated to the study of the asymptotic behavior of some large random graphs and trees. First is studied a random graph model introduced by Bo Söderberg in 2002. One chapter of this manuscript is devoted to the study of the asymptotic behavior of the size of the connected components near the critical window, linking it to the lengths of excursion of a Brownian motion with parabolic drift. The next chapter talks about a random graph process suggested by Itai Benjamini, defined as follows: edges are independently added at a fixe rate. Whenever a vertex reaches degree k, all adjacent edges are removed. This process is non-increasing, preventing the use of some commonly used methods. By using local limits, in the spirit of the PWIT, we were able to prove the presence (resp. absence) of a giant component at some stages of the process when k>=5 (resp. k<=3). In the case k=4, these results allows to link the presence (resp. absence) of a giant component to the supercriticality (resp. criticality or subcriticality) of an associated branching process. In the last chapter, the height of random Lyndon tree is studied, and is proven to be approximately c ln n, in which c=5.092... the solution of an optimization problem. To obtain this result, we couple the Lyndon tree with a Yule tree, then studied with the help of branching walks and large deviations

Les problèmes d'optimisation combinatoires définis sur graphes aléatoires sont au coeur de la théorie de la complexité algorithmique. Ils sont également étroitement liés à une formulation champ moyen, dite approximation de Bethe, de modèles sur réseau de verres de spins et verres structuraux. Cette thèse s'appuie sur ce parallèle pour appliquer à des problèmes d'optimisation une approche issue de la physique statistique des systèmes désordonnés, la méthode de la cavité. Etant donné un ensemble d'entrées (instances) d'un problème d'optimisation, cette méthode permet de déterminer les propriétés des solutions des instances typiques, ainsi que celles des instances atypiques, dont les probabilités sont exponentiellement petites (grandes déviations sur la structure externe). Pour une instance donnée, la méthode de la cavité donne également accès à la thermodynamique des différentes solutions admissibles (grandes déviations sur la structure interne). D'un point de vue physique, de nombreux problèmes algorithmiquement difficiles se révèlent ainsi posséder une phase de type verre. Cette thèse est composée de trois parties destinées à exposer les principes, applications et limitations de la méthode de la cavité. La première partie rappelle, dans la perspective des grandes déviations, les liens entre physique statistique et optimisation combinatoire. La deuxième partie aborde les modèles définis sur graphes aléatoires et, pour différents ensembles de graphes, analyse les propriétés typiques et atypiques de ces modèles. La troisième partie est consacrée aux grandes déviations sur le "désordre interne", constitué par les solutions et quasi-solutions d'une instance donnée. Une attention particulière est dévolue au traitement des phases vitreuses où l'ensemble des solutions est fragmenté en un nombre exponentiel d'amas disjoints (structure dite à un pas de brisure de symétrie des répliques); il est montré comment la méthode de la cavité fournit dans de tels cas une description fine des propriétés géométriques de l'espace des solutions.

Dans cette thèse, nous étudions des modèles d'agrégation limitée, qui modélisent la coalescence de particules ayant des "bras", c'est-à-dire un nombre fixé de liens potentiels. Une particule ne peut donc créer plus de liens que son nombre de bras. On s'intéresse en particulier à une variante de l'équation de Smoluchowski introduite par Jean Bertoin. Ce document comprend, outre l'introduction, trois chapitres. Le premier est dévolu à l'étude d'un modèle sexué de coagulation, où les particules ont des bras mâles et femelles et seuls des bras de sexes opposés peuvent se joindre. Ce modèle généralise et unifie ceux de Bertoin, dont on peut en particulier retrouver les résultats. Le second chapitre comprend un travail en collaboration avec Lorenzo Zambotti. On s'y intéresse à l'unicité des solutions d'équations de coagulation après gélification, en particulier l'équation de Smoluchowski avec noyau multiplicatif et l'équation d'agrégation limitée. En particulier, on donne des preuves rigoureuses de certaines heuristiques de la littérature physique, par exemple en calculant précisément le temps de gélification. Dans le cas d'agrégation limitée, on obtient aussi des formules particulièrement simples pour les concentrations limites. Pour expliquer celles-ci, on étudie dans le dernier chapitre un modèle microscopique pour l'équation de Smoluchowski d'agrégation limitée. Ceci est un travail commun avec Mathieu Merle. On parvient à décrire précisément l'état microscopique du système à tout temps et ainsi à retrouver les formules du second chapitre. Une caractéristique frappante de ce modèle est qu'il possède une propriété de criticalité auto-organisée.

Dans cette thèse, nous étudions les propriétés de concentration des fonctions propres du laplacien discret sur des graphes réguliers de degré fixé dont le nombre de sommets tend vers l'infini. Cette étude s'inspire de la théorie de l'ergodicité quantique sur les variétés. Par analogie avec cette dernière, nous développons un calcul pseudo-différentiel sur les arbres réguliers : nous définissons des classes de symboles et des opérateurs associés, et nous prouvons un certain nombre de propriétés de ces classes de symboles et opérateurs. Nous montrons notamment que les opérateurs sont bornés dans L², et nous donnons des formules de l'adjoint et du produit. Nous nous servons ensuite de cette théorie pour montrer un théorème d'ergodicité quantique pour des suites de graphes réguliers dont le nombre de sommets tend vers l'infini. Il s'agit d'un résultat de délocalisation de la plupart des fonctions propres dans la limite des grands graphes réguliers. Les graphes vérifient une hypothèse d'expansion et ne comportent pas trop de cycles courts, deux hypothèses vérifiées presque sûrement par des suites de graphes réguliers aléatoires.

Le processus de contact est l'un des systèmes de particules en interaction les plus étudiés. Il peut s'interpréter comme un modèlepour la propagation d'un virus dans une population ou sur un réseau. L'objectif de cette thèse est d'étudier la relation entre la structure locale du réseau et le comportement global du processus sur le réseau tout entier.Le cadre typique dans lequel on se place est celui d’une suite de graphes aléatoires $(G_n)$ convergeant localement vers un graphe limite $G$.On étudie alors le comportement asymptotique du temps d’extinction $tau_n$ du processussur $G_n$; lorsqu’initialement tous les individus sont infectés. Nous montrons sur plusieurs exemples qu’il existe unetransition de phase lorsque $lambda$ - le taux d'infection du processus - traverse une valeur critique $ lambda_c (G)$, qui ne dépend que de $G$.Plus précisément, pour certains modèles de graphes aléatoires comme le modèle de configuration, le graphe d'attachement préférentiel, le graphe géométrique aléatoire, le graphe inhomogène, nous montrons que $ tau_n $ est d'ordre soit logarithmique soit exponentiel; selon que $ lambda$ est soit inférieur ou supérieur à $lambda_c (G) $.De plus, dans certains cas, nous montrons des résultats de métastablité: en régime sur-critique, $ tau_n $ divisé par son espérance converge en loi vers une variable aléatoire exponentielle de moyenne $1$, et la densité des sites infectés reste stable (et non nulle) sur une période de temps d’ordre typiquement $tau_n$. / The contact process is one of the most studied interacting particle systems and is also often interpreted as a model for the spread of a virus in a population or a network. The aim of this thesis is to study the relationship of the local structure of the network and the global behavior of the contact process (the virus) on the whole network. Let $(G_n)$ be a sequence of random graphs converging weakly to a graph $G$. Then we study $tau_n$, the extinction time of the contact process on $G_n$ starting from full occupancy. We prove in some examples that there is a phase transition of $tau_n$ when $lambda$ - the infection rate of the contact process crosses a critical value $lambda_c(G)$ depending only on $G$. More precisely, for some models of random graphs, such as the configuration model, preferential attachment graph, random geometric graph, inhomogeneous graph, we show that $tau_n$ is of logarithmic (resp. exponential) order when $lambda < lambda_c(G)$ (resp. $lambda < lambda_c(G)$). Moreover, in some cases we also prove metastable results: in the super-critical regime, $tau_n$ divided by its expectation converges in law to an exponential random variable with mean $1$, and the density of the infected sites is stable for a long time.

Nous étudions le problème de maintenir une distribution donnée de graphes aléatoires après une séquence arbitraire d’insertions et de suppressions de sommets. Dans l’objectif de modéliser l’évolution de réseaux logiques dynamiques,nous travaillons dans un modèle local où l’accès à la liste des sommets est restreint. À la place, nous faisons l’hypothèse d’un accès à une primitive globale qui retourne un sommet aléatoire, choisi uniformément dans l’ensemble total des sommets. Le problème de maintenance a été exploré sur plusieurs modèles simples de graphes aléatoires (graphes d’Erdos–Rényi, graphes basés sur le modèle par paires, graphes k-sortants uniformes). Pour chacun des modèles, un ou plusieurs algorithmes pour la tâche de maintenance ont été décris et analysés ; les plus élaborés de ces algorithmes sont asymptotiquement optimaux. Le problème de maintenance soulève plusieurs problèmes de simulation liés à notre contexte distribué. Nous nous sommes intéressé en particulier à la maintenabilité de distributions de graphes et à la simulabilité de familles de distributions de probabilité sur les entiers, dans le modèle d’aléa présenté.Une attention particulière a été portée sur la simulation efficace de lois spécifiques nous intéressant (certaines lois binomiales). Cette dernière a pu être obtenue en exploitant les propriétés d’un nouvel arbre de génération pour les permutations, que nous avons introduit. / We study the problem of maintaining a given distribution of randomgraphs under an arbitrary sequence of vertex insertions and deletions. Keeping inmind our objective to model the evolution of dynamic logical networks, we work ina local model where we do not have direct access to the list of all vertices. Instead,we assume access to a global primitive that returns a random vertex, chosen uniformlyfrom the whole vertex set. The maintenance problem has been explored onseveral simple random graph models (Erdos–Rényi random graphs, pairing modelbased random graphs, uniform k-out graphs). For each model, one or several updatealgorithms for the maintenance task have been described and analyzed ; the mostelaborate of them are asymptically optimal. The maintenance task rise several simulationissues linked to our distributed context. In particular, we have focused onmaintenability of random graph distributions and simulability of families of probabilitydistributions over integers in our local random model. Special attention hasbeen paid to efficient simulation of particular distributions we were interested in(certain binomial distributions). The latter has been obtained through the use ofproperties of a new generation tree for permutations, which has been introducedalong the way

Dans cette thèse, nous étudions les graphes aléatoires en utilisant des outils de la théorie des matrices aléatoires et l’analyse probabilistique afin de résoudre des problèmes clefs dans le domaine des réseaux complexes et Big Data. Le premier problème qu’on considère est de détecter un sous graphe Erdős–Rényi G(m,p) plante dans un graphe Erdős–Rényi G(n,q). Nous dérivons les distributions d’une statistique basée sur les propriétés spectrales d’une matrice définie du graphe. Ensuite, nous considérons le problème de la récupération des sommets du sous graphe en présence de l’information supplémentaire. Pour cela nous utilisons l’algorithme «Belief Propagation». Le BP sans informations supplémentaires ne réussit à la récupération qu’avec un SNR effectif lambda au-delà d’un seuil. Nous prouvons qu’en présence des informations supplémentaires, ce seuil disparaît et le BP réussi pour n’importe quel lambda. Finalement, nous dérivons des expressions asymptotiques pour PageRank sur une classe de graphes aléatoires non dirigés appelés « fast expanders », en utilisant des techniques théoriques à la matrice aléatoire. Nous montrons que PageRank peut être approché pour les grandes tailles du graphe comme une combinaison convexe du vecteur de dégré normalisé et le vecteur de personnalisation du PageRank, lorsque le vecteur de personnalisation est suffisamment délocalisé. Par la suite, nous caractérisons les formes asymptotiques de PageRank sur le Stochastic Block Model (SBM) et montrons qu’il contient un terme de correction qui est fonction de la structure de la communauté. / In this thesis, we study random graphs using tools from Random Matrix Theory and probability to tackle key problems in complex networks and Big Data. First we study graph anomaly detection. Consider an Erdős-Rényi (ER) graph with edge probability q and size n containing a planted subgraph of size m and probability p. We derive a statistical test based on the eigenvalue and eigenvector properties of a suitably defined matrix to detect the planted subgraph. We analyze the distribution of the derived test statistic using Random Matrix Theoretic techniques. Next, we consider subgraph recovery in this model in the presence of side-information. We analyse the effect of side-information on the detectability threshold of Belief Propagation (BP) applied to the above problem. We show that BP correctly recovers the subgraph even with noisy side-information for any positive value of an effective SNR parameter. This is in contrast to BP without side-information which requires the SNR to be above a certain threshold. Finally, we study the asymptotic behaviour of PageRank on a class of undirected random graphs called fast expanders, using Random Matrix Theoretic techniques. We show that PageRank can be approximated for large graph sizes as a convex combination of the normalized degree vector and the personalization vector of the PageRank, when the personalization vector is sufficiently delocalized. Subsequently, we characterize asymptotic PageRank on Stochastic Block Model (SBM) graphs, and show that it contains a correction term that is a function of the community structure.

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2013-2014. / Les graphes sont des objets mathématiques abstraits utilisés pour modéliser les interactions entre les éléments constitutifs des systèmes complexes. Cette utilisation est motivée par le fait qu’il existe un lien fondamental entre la structure de ces interactions et les propriétés macroscopiques de ces systèmes. La théorie de la percolation offre un paradigme de choix pour analyser la structure de ces graphes, et ainsi mieux comprendre les conditions dans lesquelles ces propriétés émergent. Les interactions dans une grande variété de systèmes complexes partagent plusieurs propriétés structurelles universelles, et leur incorporation dans un cadre théorique unique demeure l’un des principaux défis de l’étude des systèmes complexes. Exploitant une approche multitype, une idée toute simple mais étonnamment puissante, nous avons unifié l’ensemble des modèles de percolation sur graphes aléatoires connus en un même cadre théorique, ce qui en fait le plus général et le plus réaliste proposé à ce jour. Bien plus qu’une simple compilation, le formalisme que nous proposons augmente significativement la complexité des structures pouvant être reproduites et, de ce fait, ouvre la voie à plusieurs nouvelles avenues de recherche. Nous illustrons cette assertion notamment en utilisant notre modèle pour valider et formaliser certaines intuitions inspirées de résultats empiriques. Dans un premier temps, nous étudions comment la structure en réseau de certains systèmes complexes (ex. réseau de distribution électrique, réseau social) facilite leur surveillance, et par conséquent leur éventuel contrôle. Dans un second temps, nous explorons la possibilité d’utiliser la décomposition en couches “k-core” en tant que structure effective des graphes extraits des systèmes complexes réels. Enfin, nous utilisons notre modèle pour identifier les conditions pour lesquelles une nouvelle stratégie d’immunisation contre des maladies infectieuses est la stratégie optimale. / Graphs are abstract mathematical objects used to model the interactions between the elements of complex systems. Their use is motivated by the fact that there exists a fundamental relationship between the structure of these interactions and the macroscopic properties of these systems. The structure of these graphs is analyzed within the paradigm of percolation theory whose tools and concepts contribute to a better understanding of the conditions for which these emergent properties appear. The underlying interactions of a wide variety of complex systems share many universal structural properties, and including these properties in a unified theoretical framework is one of the main challenges of the science of complex systems. Capitalizing on a multitype approach, a simple yet powerful idea, we have unified the models of percolation on random graphs published to this day in a single framework, hence yielding the most general and realistic framework to date. More than a mere compilation, this framework significantly increases the structural complexity of the graphs that can now be mathematically handled, and, as such, opens the way to many new research opportunities. We illustrate this assertion by using our framework to validate hypotheses hinted at by empirical results. First, we investigate how the network structure of some complex systems (e.g., power grids, social networks) enhances our ability to monitor them, and ultimately to control them. Second, we test the hypothesis that the “k-core” decomposition can act as an effective structure of graphs extracted from real complex systems. Third, we use our framework to identify the conditions for which a new immunization strategy against infectious diseases is optimal.

Dans cette thèse, nous étudions les propriétés de concentration des fonctions propres du laplacien discret sur des graphes réguliers de degré fixé dont le nombre de sommets tend vers l'infini. Cette étude s'inspire de la théorie de l'ergodicité quantique sur les variétés. Par analogie avec cette dernière, nous développons un calcul pseudo-différentiel sur les arbres réguliers : nous définissons des classes de symboles et des opérateurs associés, et nous prouvons un certain nombre de propriétés de ces classes de symboles et opérateurs. Nous montrons notamment que les opérateurs sont bornés dans L², et nous donnons des formules de l'adjoint et du produit. Nous nous servons ensuite de cette théorie pour montrer un théorème d'ergodicité quantique pour des suites de graphes réguliers dont le nombre de sommets tend vers l'infini. Il s'agit d'un résultat de délocalisation de la plupart des fonctions propres dans la limite des grands graphes réguliers. Les graphes vérifient une hypothèse d'expansion et ne comportent pas trop de cycles courts, deux hypothèses vérifiées presque sûrement par des suites de graphes réguliers aléatoires. / N this thesis, we study concentration properties of eigenfunctions of the discrete Laplacian on regular graphs of fixed degree, when the number of vertices tend to infinity. This study is made in analogy with the Quantum Ergodicity theory on manifolds. We construct a pseudo-differential calculus on regular trees by defining symbol classes and associated operators and proving some properties of these classes of symbols and operators. In particular we prove that the operators are bounded on L² and give adjoint and product formulas. We then use this theory to prove a Quantum Ergodicity theorem on large regular graphs. This is a property of delocalization of most eigenfunctions in the large scale limit. We consider expander graphs with few short cycles (for instance random large regular graphs). These hypothesis are almost surely satisfied by sequences of random regular graphs.

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. / The thesis fits into the random matrix theory, in intersection with free probability and operator algebra. It is part of a general approach which is common since the last decades: using tools and concepts of non commutative probability in order to get general results about the spectrum of large random matrices. Where are interested here in generalization of Voiculescu's asymptotic freeness theorem. In Chapter 1 and 2, we show some results of strong asymptotic freeness for gaussian, random unitary and deterministic matrices. In Chapter 3 and 4, we introduce the notion of asymptotic false freeness for deterministic matrices and certain random matrices, Hermitian with independent sub-diagonal entries, interpolating Wigner and Lévy models.