Processus d'exploration des grands graphes aléatoires: analyse exacte et approximation

Mots clés

graphe aléatoire, algorithme d'exploration

Détail de l'offre

Les graphes aléatoires jouent un rôle de plus en plus prépondérant dans de nombreuses applications des probabilités (réseaux sociaux, modèles épidémiologiques, réseaux de télécommunication, réseaux d'interaction de gènes...) Les caractéristiques géométriques locales précises d'un graphe réel étant en général inconnues, il apparait comme naturel de le modéliser par un graphe aléatoire ayant des propriétés statistiques analogues, comme par exemple le modèle de configuration, et d'étudier la limite en grand graphe de ce graphe aléatoire.

Plus précisément, on peut accéder à un certain nombres de caractéristiques d'un graphe (connexité, diamètre...) par des processus d'exploration. Lorsqu'une construction séquentielle du graphe aléatoire existe, un couplage judicieux avec le processus d'exploration peut permettre d'accéder au comportement dans la limite grand graphe des propriétés d'intérêt.

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, afin de donner des approximations en grand graphe des caractéristiques de ces processus.