13-18 mai 2018 Saint Pierre d'Oléron (France)
Analyse asymptotique de grands graphes aléatoires
Marion Sciauveau  1@  , Jean-François Delmas  1@  , Jean-Stéphane Dhersin  2@  
1 : Centre dÉnseignement et de Recherche en Mathématiques et Calcul Scientifique
Ecole des Ponts ParisTech
2 : Laboratoire Analyse, Géométrie et Applications
UMR7539

Les réseaux sociaux ou encore internet peuvent être représentés par des grands graphes aléatoires. Comprendre leur structure représente donc un enjeu important en mathématiques. Les graphons sont les objets limites pour les suites convergentes de grands graphes finis et denses, sous une certaine distance, appelée distance de coupe. Un graphon est une fonction mesurable, symétrique W : [0, 1]^2 → [0, 1]. De manière informelle, W(x,y)dx dy représente la densité d'arêtes entre les nœuds x et y.

Une caractérisation équivalente à la convergence métrique de suites de graphes denses peut-être donnée en terme de convergence de densités de sous-graphes. Par ailleurs, il est possible d'échantillonner des graphes simples, avec un nombre de nœuds donné, à partir d'un graphon W (appelés “W -random graphs” en anglais). Par cette construction, on obtient une suite de graphes qui converge presque sûrement vers le graphon W. Nous énoncerons plusieurs résultats autour des fluctuations associées à cette convergence, notamment un théorème central limite sur les densités de sous-graphes dans les “W -random graphs”.


Personnes connectées : 1