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.

Formulation statistique 

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.

Exemples 

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.

On peut interpréter ce modèle comme un modèle de graphes aléatoires composé de  graphes d'Erdős-Rényi distincts avec les paramètres  respectivement, avec des bigraphes entre eux, où chaque arête possible entre les blocs  et  est incluse indépendamment avec la probabilité . 

De nombreux autres modèles de graphes aléatoires populaires peuvent être compris comme des modèles de graphes aléatoires échangeables définis par un graphon ; un aperçu détaillé est donné dans l'article d'Orbanz et Roy.

Matrices d'adjacence échangeables 

Un graphe aléatoire de taille  peut être représenté comme une matrice d'adjacence aléatoire . Afin d'imposer une cohérence entre des graphes aléatoires de tailles différentes, il est naturel d'étudier la séquence des matrices d'adjacence qui apparaissent comme sous-matrices supérieures  d'une matrice infinie de variables aléatoires ; cela  permet de générer  en ajoutant un nœud à  et en échantillonnant les arêtes  pour . Dans cette perspective, les graphes aléatoires sont définis comme des tableaux infinis symétriques aléatoires .

L'importance fondamentale des   dans les probabilités classiques incite à rechercher une notion analogue dans le cadre des graphes aléatoires. Une telle notion est donnée par les matrices échangeables conjointement, c'est-à-dire les matrices aléatoires satisfaisant

 

pour toute permutation  d'entiers naturels, où  est l'égalité en distribution. Intuitivement, cette condition signifie que la distribution des graphes aléatoires est inchangée par un réétiquetage de ses sommets ; autrement dit, les étiquettes des sommets ne portent aucune information.

Il existe un théorème de représentation pour les matrices d'adjacences aléatoires échangeables conjointement, analogue au  pour les séquences échangeables. Il s'agit d'un cas particulier du  pour les tableaux échangeables conjointement et, dans ce cadre, il affirme que la matrice aléatoire  est générée comme suit :

 échantilloner indépendamment  
  indépendamment aléatoirement avec une probabilité 

où  est un graphon (éventuellement aléatoire). Autrement dit, modèle de graphes aléatoires a une matrice d'adjacence échangeable conjointement si et seulement si c'est un modèle de graphes aléatoires échangeables conjointement défini en termes d'un certain graphon.

Estimation de graphons 
En raison de problèmes d'identifiabilité, il est impossible d'estimer la fonction graphon  ou les positions latentes des nœuds  ; il existe deux aproches principales  pour l'estimation du graphon.  Une direction vise à estimer  à une classe d'équivalence près
, ou d'estimer la matrice de probabilités induite par .

Formulation analytique 
Tout graphe  à  sommets  peut être identifié à sa  matrice d'adjacence .
Cette matrice correspond à une fonction en escalier , définie par le partitionnement  en intervalles 
, où l'intervalle 
et, pour , 
 .
La fonction  est le graphon associé au graphe .

En général, pour une suite de graphes  dont le nombre de sommets tend vers l'infini, on peut analyser le
comportement limite de la suite en considérant le comportement limite des fonctions . 
Si ces graphes convergent (selon une définition appropriée de convergence), alors la limite de ces graphes correspond à la limite de ces fonctions associées.

Cela motive la définition d'un graphon (abréviation de "fonction de graphe") comme une fonction symétrique mesurable  qui
capte la notion de limite d'une suite de graphes. 
Il s'avère que pour des suites de graphes denses, plusieurs notions de convergence apparemment distinctes sont équivalentes et que, pour chacune d'elles, l'objet limite naturel est un graphon. 

 Exemples Exemple 1: On considère une suite aléatoire   graphes d'Erdős-Rényi  avec un paramètre fixe .
Intuitivement, comme  tend vers l'infini, la limite de cette suite de graphes est déterminée uniquement par la densité des arêtes de ces graphes.

Dans l'espace des graphons, il s'avère qu'une telle suite converge presque sûrement vers fonction constante , ce qui correspond à  l'intuition ci-dessus.Exemple 2: On considère la suite  de demi-graphes définie en prenant pouur  le graphe bipartite sur les sommets u_1, u_2, \dots, u_ et  tels  soit adjacent à  quand . Si les sommets sont énumérés dans l'ordre, alors
la matrice d'adjacence  a deux coins qui sont des matrices blocs « demi-carrés » remplis de 1, le reste des entrées étant égal à zéro.
Par exemple, la matrice d'adjacence de  est donnée par

Quand  croît, ces deux coins deviennent lisses. Conformément à cette intuition, la suite  converge vers le demi-graphon  défini par  lorsque  et  sinon.Exemple 3: On considère une suite  de graphes bipartis complets avec deux parties de même taille.
On ordonne les sommets en plaçant tous les sommets d'une partie avant les sommets de l'autre partie.  
La matrice d'adjacence de  est semblable à une matrice de diagonale, avec deux blocs de uns et deux blocs de zéros.
Par exemple, la matrice d'adjacence de  est donnée par

Quand  croît, cette structure en blocs de la matrice d'adjacence demeure, 
de sorte que cette suite de graphes converge vers un graphon « bipartite complet » 
défini par  si  et , et  sinon. Exemple 4:
On considère la suite  de l'exemple précédent.
Si on ordonne les sommets en alternant entre les deux parties,
la matrice d'adjacence a une structure d'échiquier de zéros et de uns.
Par exemple, dans cet ordre, la matrice d'adjacence de  est donnée par
  

Quand  croît, 
la matrice d'adjacence devient un échiquier de plus en plus fin. Malgré ce comportement, la limite de  doit unique et égale au graphon de l'exemple 4.
Cela signifie que la définition d'une limite d'une suite de graphes doit être indépendante de ré-étiquetages des sommets.Exemple 5: On considère  une suite aléatoire  de graphes aléatoires pour  en posant  pour un graphon fixe .
Alors, et comme dans le premier exemple de cette section, la suite  converge vers  presque sûrement.Exemple 6''': Étant donné le graphe  avec graphon associé , on peut retrouver des paramètres du graphe   en récupérant des transformations de .

Par exemple, la densité des arêtes (c'est-à-dire le degré moyen divisé par le nombre de sommets) de  est donnée par l'intégrale
.
En effet,  est à valeurs dans , et chaque chaque 
de  
correspond à une région 
de surface  où  est égal à .

Un raisonnement similaire montre que le nombre de triangles de  est égal à

 Notions de convergence 

Il existe de nombreuses façons de mesurer la distance entre deux graphiques.
Si on s'intéresse aux métriques qui « préservent » les propriétés extrémales des graphes,
on doit se limiter aux métriques qui considèrent que des graphes aléatoires sont similaires.
Par exemple, si on
tire aléatoirement deux graphes indépendamment dans un modèle d'Erdős-Rényi  pour certains  fixes, la distance entre ces deux graphes pour une métrique « raisonnable » doit être proche de zéro avec une grand probabilité pour les grands entiers .

Il existe deux métriques naturelles qui se comportent bien en ce sens sur les graphiques aléatoires denses.
La première est une métrique d'échantillonnage, pour laquelle deux graphes sont proches si les distributions de leurs sous-graphes sont proches.
La seconde est une métrique de  des arêtes, pour lasuelle deux graphes sont proches lorsque les densités de leurs arêtes sont proches sur tous leurs sous-ensembles correspondants de sommets.

Miraculeusement, une suite de graphes converge lorsque pour l'une des distances précisément lorsqu'elle converge pour l'autre.
De plus, les objets limite pour les deux distances sont des graphons.
L'équivalence de ces deux notions de convergence reflète l'équivalence des différentes notions de graphes quasi-aléatoires au sens de Fan_Chung.

 Nombre de sous-graphes 

Une façon de mesurer la distance entre deux graphes  et  est de comparer leurs nombres de sous-graphes.
CEn d'autres termes, pour chaque graphe , on compare le nombre de copies de  dans  et dans .
Si ces nombres sont proches pour chaque graphe , alors
intuitivement  et  sont des graphes d'apparence similaire.

 Densité homomorphe 

Il est équivalent de considérer des homomorphismes des graphes plutôt que directement les sous-graphes. En effet, 
pour de grands graphes denses, le nombre de sous-graphes et le nombre d'homomorphismes de graphes à partir d'un graphe fixe sont asymptotiquement égaux.

Étant donné les deux graphes  et , la 
  de  dans  est définie comme étant le nombre de morphismes de graphes de  dans .
En d'autres termes,  est la probabilité pour qu'une fonction choisie au hasard des sommets de  dans les sommets de  envoie des sommets adjacents dans  sur des sommets adjacents dans .

Les graphons offrent un moyen simple de calculer les densités d'homomorphismes.
En effet, pour un graphe  avec graphon associé  et un autre graphe , on a
,
où l'intégrale est multidimensionnelle, et évaluée sur l' hypercube unité .
Ceci découle de la définition d'un graphon associé, quand on considère le cas où l'intégrale ci-dessus vaut .
On oeut alors étendre la définition de la densité d'homomorphismes à des graphons arbitraires , en utilisant la même intégrale et en définissant

pour tout graphe .

 Limites en termes de densité d'homomorphismes 

Dans ce cadre, une suite de graphes  est dite convergente si, pour chaque graphe fixé , la suite de densités d'homomorphismes  converge. Bien que cela ne résulte pas immédiatement de la définition, si  converge en ce sens, alors il existe un graphon  tel que, pour chaque graphon , on ait également
.

 Distance de coupe 
Soient  et  deux graphes sur le même ensemble de sommets. Une façon de mesurer leur distance est de se restreindre aux sous-ensembles  de l'ensemble des sommets, et pour chaque paire de ces sous-ensembles, de comparer le nombre d'arêtes  de  vers  dans  au nombre d'arêtes  entre  et  dans .
Si ces nombres sont proches (par rapport au nombre total de sommets) pour chaque paire de sous-ensembles, cela suggère que  et  sont des graphes similaires.

Formellement, on définit, pour toute fonction symétrique mesurable , la norme de coupe comme étant la quantité

 

prise sur tous les sous-ensembles mesurables  de l'intervalle unité.

Cette norme étend la notion de distance définie plus haut, car pour deux graphes  et  avec un même ensemble  de  sommets, la norme de coupe avec les graphons associés

permet de calculer la discrépance maximale des densités d'arêtes entre  et . Cette définition peut être utilisée aussi lorsque les graphees ne sont pas sur le même ensemble de sommets.

Cette mesure de distance a encore un défaut : elle peut attribuer une distance non nulle à deux graphes isomorphes.
Pour s'assurer que des graphes isomorphes sont à distance nulle, il faut calculer la norme de coupe minimale sur tous les réétiquetages possibles des sommets.

Cela motive la définition de la distance de coupe'' entre deux graphons  et  comme étant 

où  est la composition de  avec l'application , et l'infimum est pris sur toutrd les mesures bijections préservant les mesures de l'intervalle unité dans lui-même.
La distance de coupe entre deux graphes est définie comme étant la distance de coupe entre les graphonss associés.

Espace métrique 
Pour transformer la distance de coupure en une distance d'espace métrique, on considère l'ensemble de tous les graphons et on identifie deux graphons  quand . L'espace de graphons résultant, noté , est un espace métrique pour .

Cet espace est compact. De plus, l'ensemble de tous les graphes est une partie dense de l'espace. Les graphes sont identifiés comme des fonctions en escalier à valeurs dans  sur le  carré unité. Ces observations montrent que l'espace des graphons est  l'complété de l'espace des graphes par rapport à la distance de coupe.

Applications

Lemme de régularité 

En utilisant la compacité de l'espace des graphons , on peut prouver des versions plus fortes du lemme de régularité de Szemerédi.

Conjecture de Sidorenko 

La nature analytique des graphons permet une plus grande flexibilité dans l'approches des inégalités concernant les homomorphismes. 

Par exemple, la conjecture de Sidorenko est un problème ouvert majeur en théorie des graphes extrémaux ; elle affirme que pour tout graphe  à  sommets avec degré moyen  pour un , et pour un graphe bipartite  à  sommets et  arêtes, le nombre de morphismes de  dans  est au moins égal à . Puisque cette quantité est le nombre moyen de sous-graphes étiquetés de  d'un graphe aléatoire , la conjecture peut être interprétée comme l'énoncé que, dans tout graphe bipartite , un graphe aléatoire atteint (en moyenne) le nombre minimum de copies de  parmi tous les graphes ayant une certaine densité d'arêtes fixée.

De nombreuses approches de la conjecture de Sidorenko formulent le problème comme une inégalité intégrale sur des graphes, ce qui permet ensuite d'attaquer le problème en utilisant d'autres approches analytiques.

Généralisations 

Les graphons sont naturellement associés aux graphes simples denses. 
Il existe des extensions de ce modèle à des graphes orientés denses pondérés, souvent appelés graphons décorés. Il existe également des extensions récentes à la famille des graphes creux, tant du point de vue des modèles de graphes aléatoires que de la théorie des limites des graphes.

Notes et références 

Théorie des graphes
Graphe aléatoire