Processus d'exploration, de marquage et de contagion sur les grands graphes aléatoires: construction couplée, analyse exacte et approximation.

Offre de thèse

Date limite de candidature

29-05-2026

Date de début de contrat

01-10-2026

Directeur de thèse

MARCHAND Régine

Encadrement

Encadrement 50/50 entre les deux co-directeurs, à l'institut Elie Cartan de Lorraine sur le site de Nancy.

Type de contrat

Concours pour un contrat doctoral

Candidater à cette offre

école doctorale

IAEM - INFORMATIQUE - AUTOMATIQUE - ELECTRONIQUE - ELECTROTECHNIQUE - MATHEMATIQUES

équipe

PROBAS STATS

contexte

Les graphes aléatoires jouent un rôle de plus en plus prépondérant dans de nombreux applications des probabilités: ils peuvent représenter des réseaux sociaux, des modèles épidémiologiques sur de grandes populations, des réseaux de télécommunication, des réseaux d'interaction de gènes, des réseaux d'énergie, etc. Dans ces contextes, on sera amené à étudier de très grands graphes (parfois plusieurs millions de sommets), et de donner les caractéristiques générales de ces objets en limite grand graphe, en les modélisant par un grand graphe aléatoire ayant des caractéristiques générales données, plutôt que d'en donner les caractéristiques géométriques locales précises, qui sont en général inconnues.

spécialité

Mathématiques

laboratoire

IECL - Institut Elie Cartan de Lorraine

Mots clés

grand graphe aléatoire, processus de construction et d'exploration, modèle de configuration

Détail de l'offre

L'objectif principal de ce travail de thèse est de donner un cadre théorique probabiliste précis à l'étude de l'approximation en grand graphe, de différents processus d'exploration de ces grands graphes aléatoires. Pour modéliser l'incertitude liée à la géométrie précise du graphe, nous travaillerons en priorité sur des graphes aléatoires générés par le modèle de configuration. On suppose que les degrés des noeuds sont connus (et réalisent par exemple un n-échantillon d'une loi de probabilité
donnée sur N), et on tire au sort une réalisation d'un multi-graphe ayant cette distribution de degrés,
par appariement séquentiel et uniforme des demi-arêtes des noeuds. On s'intéressera alors
naturellement à des processus d'exploration de ces graphes: l'exploration en longueur, et l'exploration
en profondeur permettent de tester la connexité du graphe, et éventuellement de construire des arbres couvrants pour celui-ci. On peut par ailleurs, explorer ce graphe en suivant la propagation d'une épidémie ou un processus de contact, construire une famille indépendante maximale par l'algorithme dit de la greedy independent set, ou encore, en construisant à la volée un couplage des noeuds. La construction séquentielle du graphe par le modèle de configuration, décrite plus haut, induit alors des représentations markoviennes naturelles dans des espaces de mesures ponctuelles. On peut alors coupler, de manière fructueuse, cette construction avec l'un des processus d'exploration mentionnés ci-dessus, en obtenant des représentations markoviennes simples, qui permettent alors de décrire facilement les caractéristiques de ces processus d'exploration, en régime asymptotique grand graphe. Cette approche couplée est souvent appelée constructing while exploring.
L'objectif général de ce travail de thèse sera de contribuer à généraliser cette approche de constructing while exploring à une plus grande classe de graphes et de processus d'exploration et/ou de contagion, afin de donner des approximation en grand graphe des caractéristiques de ces processus.

Keywords

large random graphs, exploration and construction processes, configuration model

Subject details

The main objective of this thesis is to provide a precise probabilistic theoretical framework for studying large-graph approximation for various processes exploring these large random graphs. To model the uncertainty associated with the precise geometry of the graph, we will focus primarily on random graphs generated by the configuration model. We assume that the degrees of the nodes are known (and follow, for example, an n-sample from a given probability distribution on N), and we randomly select a realization of a multigraph with this degree distribution, by sequentially and uniformly pairing the half-edges of the nodes. We will then naturally be interested in processes exploring these graphs: breadth-first search and depth-first search allow us to test the graph's connectivity and, potentially, to construct spanning trees for it. One can also explore this graph by following the propagation of an epidemic or a contact process, construct a maximal independent set using the so-called greedy independent set algorithm, or by constructing a coupling of the nodes on the fly. The sequential construction of the graph via the configuration model, described above, then yields natural Markovian representations in point-measure spaces. One can then fruitfully combine this construction with one of the exploration processes mentioned above.

Profil du candidat

Nous recherchons un(e) candidat(e) ayant un bagage solide en probabilités: modélisation probabiliste, étude des processus aléatoires, analyse stochastique, combinatoire. Une appétence pour les approches algorithmiques, et pour la simulation de processus aléatoires sur machine, sera un plus. Au delà de son expertise technique, nous recherchons avant tout un(e) candidat(e) ayant un goût prononcé pour la recherche, l'esprit d'initiative et de persévérance, et une curiosité mathématique dépassant le cadre de son sujet de thèse.

Candidate profile

We are looking for a candidate with a strong background in probability theory: probabilistic modeling, study of random processes, stochastic analysis, and combinatorics. An interest in algorithmic approaches and in computer simulations of random processes would be appreciated. Beyond technical expertise, we are primarily looking for a candidate with a strong passion for research, a spirit of initiative and perseverance, and a mathematical curiosity that extends beyond the scope of her/his thesis topic.

Référence biblio

[1] Daniel Ahlberg, Maria Deijfen, Svante Janson. Competing first passage percolation on random graphs with finite variance degrees. Random Structures and Algorithms 55, No. 3, 545-559, 2019.
[2] Tonći Antunovi&#263;, Yael Dekel, Elchanan Mossel, Yuval Peres. Competing first passage percolation on random regular graphs. Random Structures and Algorithms 50, No. 4, 534-583, 2017.
[3] O.S. Awolude, H. Don, E. Cator. The SIS process on Erdös-Rényi graphs: determining the infected fraction. Phys. Rev. E 111, 2025.
[4] Shankar Bhamidi, Remco van der Hofstad, Gerard Hooghiemstra. First passage percolation on random graphs
with finite mean degrees. Annals of Applied Probability 20, No. 5, 1907-1965, 2010.
[5] Shankar Bhamidi, Danny Nam, Oanh Nguyen, Allan Sly. Survival and extinction of epidemics on random graphs with general degree. Annals of Probability 49(1): 244-286, 2021.
[6] Paola Bermolen, Matthieu Jonckheere, and Pascal Moyal. The jamming constant of uniform random graphs. Stochastic Processes and their Applications 127(7):2138–2178, 2017.
[7] Béla Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics 1(4):311–316, 1980.
[8] Charles Bordenave, Marc Lelarge, and Justin Salez. Matchings on infinite graphs. Probability Theory and Related Fields 157(1-2): 183–208, 2013.
[9] Graham Brightwell, Svante Janson, and Malwina Luczak. The greedy independent set in a random graph with given degrees. Random Structures & Algorithms 51(4): 565–586, 2017.
[10] Alice Contat, and Nicolas Curien. Parking on Cayley trees and frozen Erdos–Rényi. The Annals of Probability 51(6): 1993-2055, 2023.
[11] Laurent Decreusefond, Jean-Stéphane Dhersin, Pascal Moyal, and Viet Chi Tran. Large graph limit for a sir process in random network with heterogeneous connectivity. The Annals of Applied Probabability 22(2): 541–575, 2012.
[12] Olivier Garet and Régine Marchand. Coexistence in two-type first-passage percolation models. The Annals ofApplied Probability 15(1A): 298:330, 2005.
[13] Olivier Garet and Régine Marchand. Asymptotic shape for the contact process in random environment. The Annals of Applied Probability 22(4): 1362:1410, 2012.
[14] Olivier Garet and Régine Marchand. Large deviations for the contact process in random environment. The Annals of Probability 42(4): 1438:1479, 2014.
[15] Mohamed Habib Aliou Diallo Aoudi, Pascal Moyal, and Vincent Robin. Markovian online matching algorithms on large bipartite random graphs. Methodology and Computing in Applied Probability 24(4): 3195–3225, 2022.
[16] Mohamed Habib Aliou Diallo Aoudi, Pascal Moyal, and Vincent Robin. Large graph limits of local matching algorithms on Configuration model graphs. ArXiv preprint arXiv:2410.18059v2, 2024.
[17] Rick Durrett. Random graph dynamics. Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, 2006.
[18] Nathanael Enriquez, Gabriel Faraud, Laurent Ménard, and Nathan Noiry. Depth first exploration of a configuration model. Electronic Journal of Probability 27: 1–27.
[19] Xiangying Huang, Rick Durrett. The contact process on random graphs and Galton Watson trees. ALEA, Lat. Am. J. Probab. Math. Stat. 17, No. 1, 159-182, 2020.
[20] Nathan Noiry, Vianney Perchet, and Flore Sentenac. Online matching in sparse random graphs: Non-asymptotic performances of greedy algorithm. Advances in Neural Information Processing Systems 34:21400–21412, 2021.
[21] Flore Sentenac, Nathan Noiry, Matthieu Lerasle, Laurent Ménard, and Vianney Perchet. Online matching in geometric random graphs. ArXiv preprint arXiv:2306.07891, 2023.
[22] Remco van der Hofstad. Random Graphs and Complex Networks: Volume 1. Cambridge University Press, USA, 1st edition, 2016.
[23] Daniel Valesin. The contact process on random graphs. Sociedade Brasileira de Matemática. Ensaios Mat. 40, 1-115, 2024.
[24] Nicholas C. Wormald. Differential equations for random processes and random graphs. The Annals of Applied Probability 5(4): 1217–1235, 1995.