Graphon

En théorie des graphes et en statistique, un graphon (aussi connu sous le terme limite de graphes) est une fonction symétrique mesurable , qui joue un rôle important dans l'étude des graphes denses. Les graphons sont à la fois une notion naturelle de limite d'une suite de graphes denses, et sont aussi les objets fondamentaux dans la définition des modèles de graphes aléatoires échangeables Les graphons sont liés aux graphes denses : d'une part, les modèles de graphes aléatoires définis par les graphons donnent lieu à des graphes denses presque sûrement. D'autre part, par le lemme de régularité de Szemerédi, les graphons capturent de nombreux aspects de la structure des graphes denses de grande taille. Un graphon est une fonction symétrique mesurable . Habituellement, un graphon est un modèle de graphes aléatoires échangeables selon le schéma suivant : À chaque sommet du graphe est attribué une valeur aléatoire indépendante Une arête figure dans le graphe avec probabilité . Un modèle de graphes aléatoires est un modèle de graphes aléatoires échangeable si et seulement s'il peut être défini en termes d'un graphon (éventuellement aléatoire) de cette manière. Le modèle basé sur un graphon fixe est parfois noté , par analogie avec le de graphes aléatoires. Un graphe généré à partir d'un graphon de cette manière est appelé un graphe -aléatoire. Il résulte de cette définition et de la loi des grands nombres que, si , les modèles de graphes aléatoires échangeables sont denses presque sûrement. L'exemple le plus simple d'un graphon est pour une constante . Dans ce cas, le modèle de graphes aléatoires échangeables associé est le qui contient chaque arête indépendamment avec probabilité . Plus généralement, on peut utiliser un graphon qui est constant par morceaux, en divisant le carré unité en blocs, et en posant sur le bloc d'indices . Le modèle de graphes aléatoires échangeables qui en résulte est le , une généralisation du modèle Erdős-Rényi.