Graphon

Tout graphe ${\displaystyle G}$ à ${\displaystyle n}$ sommets ${\displaystyle \{1,2,\dots ,n\}}$ peut être identifié à sa matrice d'adjacence ${\displaystyle A_{G}}$. Cette matrice correspond à une fonction en escalier ${\displaystyle W_{G}:[0,1]^{2}\to [0,1]}$, définie par le partitionnement ${\displaystyle [0,1]}$ en intervalles ${\displaystyle I_{1},I_{2},\dots ,I_{n}}$, où l'intervalle ${\displaystyle I_{j}=](j-1)/n,j/n[}$ et, pour ${\displaystyle (x,y)\in I_{i}\times I_{j}}$,

${\displaystyle W_{G}(x,y)={A_{G}}_{ij}}$.

La fonction ${\displaystyle W_{G}}$ est le graphon associé au graphe ${\displaystyle G}$.

En général, pour une suite de graphes ${\displaystyle (G_{n})}$ 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 ${\displaystyle (W_{G_{n}})}$. 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 ${\displaystyle W:[0,1]^{2}\to [0,1]}$ 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^[6].

Exemple 1: On considère une suite aléatoire ${\displaystyle (G_{n})}$ graphes d'Erdős-Rényi ${\displaystyle G_{n}=G(n,p)}$ avec un paramètre fixe ${\displaystyle p}$. Intuitivement, comme ${\displaystyle n}$ 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 ${\displaystyle W(x,y)\equiv p}$, ce qui correspond à l'intuition ci-dessus.

Exemple 2: On considère la suite ${\displaystyle (H_{n})}$ de demi-graphes définie en prenant pour ${\displaystyle H_{n}}$ le graphe biparti sur les sommets ${\displaystyle u_{1},u_{2},\dots ,u_{n}}$ et ${\displaystyle v_{1},v_{2},\dots ,v_{n}}$ tels ${\displaystyle u_{i}}$ soit adjacent à ${\displaystyle v_{j}}$ quand ${\displaystyle i\leq j}$. Si les sommets sont énumérés dans l'ordre, alors la matrice d'adjacence ${\displaystyle A_{H_{n}}}$ 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 ${\displaystyle H_{3}}$ est donnée par

${\displaystyle {\begin{bmatrix}0&0&0&1&1&1\\0&0&0&0&1&1\\0&0&0&0&0&1\\1&0&0&0&0&0\\1&1&0&0&0&0\\1&1&1&0&0&0\end{bmatrix}}.}$

Quand ${\displaystyle n}$ croît, ces deux coins deviennent lisses. Conformément à cette intuition, la suite ${\displaystyle (H_{n})}$ converge vers le demi-graphon ${\displaystyle W}$ défini par ${\displaystyle W(x,y)=1}$ lorsque ${\displaystyle |x-y|\geq 1/2}$ et ${\displaystyle W(x,y)=0}$ sinon.

Exemple 3: On considère une suite ${\displaystyle (K_{n,n})}$ 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 ${\displaystyle (K_{n,n})}$ est semblable à une matrice de diagonale, avec deux blocs de uns et deux blocs de zéros. Par exemple, la matrice d'adjacence de ${\displaystyle K_{2,2}}$ est donnée par

${\displaystyle {\begin{bmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}}.}$

Quand ${\displaystyle n}$ croît, cette structure en blocs de la matrice d'adjacence demeure, de sorte que cette suite de graphes converge vers un graphon « biparti complet » ${\displaystyle W}$ défini par ${\displaystyle W(x,y)=1}$ si ${\displaystyle \min(x,y)\leq 1/2}$ et ${\displaystyle \max(x,y)>1/2}$, et ${\displaystyle W(x,y)=0}$ sinon.

Exemple 4: On considère la suite ${\displaystyle (K_{n,n})}$ 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 ${\displaystyle K_{2,2}}$ est donnée par

${\displaystyle {\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}}.}$

Quand ${\displaystyle n}$ croît, la matrice d'adjacence devient un échiquier de plus en plus fin. Malgré ce comportement, la limite de ${\displaystyle (K_{n,n})}$ 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 ${\displaystyle (G_{n})}$ de graphes aléatoires pour ${\displaystyle W}$ en posant ${\displaystyle G_{n}\sim \mathbb {G} (n,W)}$ pour un graphon fixe ${\displaystyle W}$. Alors, et comme dans le premier exemple de cette section, la suite ${\displaystyle (G_{n})}$ converge vers ${\displaystyle W}$ presque sûrement.

Exemple 6: Étant donné le graphe ${\displaystyle G}$ avec graphon associé ${\displaystyle W=W_{G}}$, on peut retrouver des paramètres du graphe ${\displaystyle G}$ en récupérant des transformations de ${\displaystyle W}$.

Par exemple, la densité des arêtes (c'est-à-dire le degré moyen divisé par le nombre de sommets) de ${\displaystyle G}$ est donnée par l'intégrale

${\displaystyle \int _{0}^{1}\int _{0}^{1}W(x,y)\;\mathrm {d} x\,\mathrm {d} y}$.

En effet, ${\displaystyle W}$ est à valeurs dans ${\displaystyle \{0,1\}}$, et chaque chaque ${\displaystyle (i,j)}$ de ${\displaystyle G}$ correspond à une région ${\displaystyle I_{i}\times I_{j}}$ de surface ${\displaystyle 1/n^{2}}$ où ${\displaystyle W}$ est égal à ${\displaystyle 1}$.

Un raisonnement similaire montre que le nombre de triangles de ${\displaystyle G}$ est égal à

${\displaystyle {\frac {1}{6}}\int _{0}^{1}\int _{0}^{1}\int _{0}^{1}W(x,y)W(y,z)W(z,x)\;\mathrm {d} x\,\mathrm {d} y\,\mathrm {d} z.}$

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 ${\displaystyle G(n,p)}$ pour certains ${\displaystyle p}$ 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 ${\displaystyle n}$.

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 discrépance 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^[7].

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

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 ${\displaystyle F}$ et ${\displaystyle G}$, la densité d'homomorphismes (en) ${\displaystyle t(F,G)}$ de ${\displaystyle F}$ dans ${\displaystyle G}$ est définie comme étant le nombre de morphismes de graphes de ${\displaystyle F}$ dans ${\displaystyle G}$. En d'autres termes, ${\displaystyle t(F,G)}$ est la probabilité pour qu'une fonction choisie au hasard des sommets de ${\displaystyle F}$ dans les sommets de ${\displaystyle G}$ envoie des sommets adjacents dans ${\displaystyle F}$ sur des sommets adjacents dans ${\displaystyle G}$.

Les graphons offrent un moyen simple de calculer les densités d'homomorphismes. En effet, pour un graphe ${\displaystyle G}$ avec graphon associé ${\displaystyle W_{G}}$ et un autre graphe ${\displaystyle F}$, on a

${\displaystyle t(F,G)=\int \prod _{(i,j)\in E(F)}W_{G}(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}}$,

où l'intégrale est multidimensionnelle, et évaluée sur l' hypercube unité ${\displaystyle [0,1]^{V(F)}}$. Ceci découle de la définition d'un graphon associé, quand on considère le cas où l'intégrale ci-dessus vaut ${\displaystyle 1}$. On peut alors étendre la définition de la densité d'homomorphismes à des graphons arbitraires ${\displaystyle W}$, en utilisant la même intégrale et en définissant

${\displaystyle t(F,W)=\int \prod _{(i,j)\in E(F)}W(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}}$

pour tout graphe ${\displaystyle F}$.

Dans ce cadre, une suite de graphes ${\displaystyle (G_{n})}$ est dite convergente si, pour chaque graphe fixé ${\displaystyle F}$, la suite de densités d'homomorphismes ${\displaystyle \left(t(F,G_{n})\right)}$ converge. Bien que cela ne résulte pas immédiatement de la définition, si ${\displaystyle (G_{n})}$ converge en ce sens, alors il existe un graphon ${\displaystyle W}$ tel que, pour chaque graphon ${\displaystyle F}$, on ait également

$${\displaystyle \lim _{n\to \infty }t(F,G_{n})=t(F,W)}$$.

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

Formellement, on définit, pour toute fonction symétrique mesurable ${\displaystyle f:[0,1]^{2}\to \mathbb {R} }$, la norme de coupe comme étant la quantité

${\displaystyle \lVert f\rVert _{\square }=\sup _{S,T\subseteq [0,1]}\left|\int _{S}\int _{T}f(x,y)\;\mathrm {d} x\,\mathrm {d} y\right|}$

prise sur tous les sous-ensembles mesurables ${\displaystyle S,T}$ de l'intervalle unité^[6].

Cette norme étend la notion de distance définie plus haut, car pour deux graphes ${\displaystyle G}$ et ${\displaystyle H}$ avec un même ensemble ${\displaystyle V}$ de ${\displaystyle n}$ sommets, la norme de coupe avec les graphons associés

${\displaystyle \lVert W_{G}-W_{H}\rVert _{\square }={\frac {1}{n^{2}}}\max _{X,Y\subseteq V}\left|e_{G}(X,Y)-e_{H}(X,Y)\right|}$

permet de calculer la discrépance maximale des densités d'arêtes entre ${\displaystyle G}$ et ${\displaystyle H}$. 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 ${\displaystyle W}$ et ${\displaystyle U}$ comme étant

${\displaystyle \delta _{\square }(U,W)=\inf _{\varphi }\lVert U-W^{\varphi }\rVert _{\square }}$

où ${\displaystyle W^{\varphi }(x,y)=W(\varphi (x),\varphi (y))}$ est la composition de ${\displaystyle W}$ avec l'application ${\displaystyle \varphi }$, et l'infimum est pris sur toutrd les mesures bijections préservant les mesures de l'intervalle unité dans lui-même^[8]. La distance de coupe entre deux graphes est définie comme étant la distance de coupe entre les graphonss associés.

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 ${\displaystyle U\sim W}$ quand ${\displaystyle \delta _{\square }(U,W)=0}$. L'espace de graphons résultant, noté ${\displaystyle {\tilde {\mathcal {W}}}_{0}}$, est un espace métrique pour ${\displaystyle \delta _{\square }}$.

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 ${\displaystyle \{0,1\}}$ 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.

En utilisant la compacité de l'espace des graphons ${\displaystyle ({\tilde {\mathcal {W}}}_{0},\delta _{\square })}$, on peut prouver des versions plus fortes du lemme de régularité de Szemerédi.

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 ${\displaystyle G}$ à ${\displaystyle n}$ sommets avec degré moyen ${\displaystyle pn}$ pour un ${\displaystyle p\in [0,1]}$, et pour un graphe biparti ${\displaystyle H}$ à ${\displaystyle v}$ sommets et ${\displaystyle e}$ arêtes, le nombre de morphismes de ${\displaystyle H}$ dans ${\displaystyle G}$ est au moins égal à ${\displaystyle p^{e}n^{v}}$^[9]. Puisque cette quantité est le nombre moyen de sous-graphes étiquetés de ${\displaystyle H}$ d'un graphe aléatoire ${\displaystyle G(n,p)}$, la conjecture peut être interprétée comme l'énoncé que, dans tout graphe biparti ${\displaystyle H}$, un graphe aléatoire atteint (en moyenne) le nombre minimum de copies de ${\displaystyle H}$ 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^[10].

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^[11]. Il existe également des extensions récentes à la famille des graphes creux, tant du point de vue des modèles de graphes aléatoires^[12] que de la théorie des limites des graphes^[13],[14].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Graphon » (voir la liste des auteurs).

• Portail des mathématiques
• Portail des probabilités et de la statistique