A random walk among random graphs

Un cours sur l'étude des graphes aléatoires. Les notions s'accompagnent de nombreux exemples et d'exercices corrigés. ©Electre 2025

Cours spécialisés

Une promenade parmi des graphes aléatoires.

Les graphes aléatoires occupent une place centrale en probabilité et en statistique. Ce sont de puissants outils pour modéliser des systèmes complexes dans de nombreux domaines. Ce cours, conçu pour des étudiants de master et de doctorat, propose une introduction aux modèles fondamentaux de la théorie des graphes aléatoires - parmi lesquels les arbres de Bienaymé-Galton-Watson, le graphe d'Erdõs-Rényi, ainsi que les modèles à attachement préférentiel, tels que le graphe de Barabâsi-Albert. Nous présentons des démonstrations modernes et concises de résultats majeurs, comme l'émergence d'une composante géante dans le graphe d'Erdõs-Rényi, ou encore le comportement asymptotique des degrés et des distances dans les graphes à attachement préférentiel. Une attention particulière est portée aux outils probabilistes fondamentaux qui sous-tendent ces résultats - notamment la méthode des moments, la théorie des marches aléatoires et la poissonnisation - dotant ainsi les étudiants d'un ensemble de techniques puissantes, applicables bien au-delà du champ de ce cours.

A random walk among random graphs

A random walk among random graphs. Random graphs now stand at the forefront of modern probability and statistics, serving as powerful tools for modeling complex systems across disciplines. This course, tailored for Master's and PhD students, offers a rigorous and insightful introduction to the foundational models of random graph theory-among them the Bienaymé-Galton-Watson trees, the Erdõs-Rényi graph, and preferential attachment models such as the Barabâsi-Albert graph. We present short and modern proofs of landmark results, including the emergence of a giant component in Erdõs-Rényi graphs and the asymptotic behavior of distances and degree distributions in preferential attachment networks. Special emphasis is placed on the core probabilistic techniques that drive these analyses-such as the method of moments, random walk theory, and Poissonization-equipping students with versatile tools that apply far beyond the scope of this course.