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 $W:[0,1]^{2}\to [0,1]$, 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.

Réalisation d'un graphe aléatoire échangeable défini par un graphon. Le graphon est représenté sous la forme d'une carte thermique magenta (en bas à droite). Un graphe aléatoire de taille $n$ est généré en assignant indépendamment à chaque sommet $k\in \{1,\dotsc ,n\}$ une variable aléatoire latente $U_{k}\sim \mathrm {U} (0,1)$ (valeurs sur l'axe vertical) et comprenant chaque arête $(k,l)$ indépendamment avec la probabilité $f(U_{k},U_{l})$. Par exemple, l'arête $(3,5)$ (vert, pointillé) est présente avec la probabilité $f(0,72,0,9)$ ; les cases vertes dans le carré de droite représentent les valeurs de $(u_{3},u_{5})$ et $(u_{5},u_{3})$. La partie supérieure gauche montre la réalisation du graphe sous la forme d'une matrice d'adjacence.

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 $W:[0,1]^{2}\to [0,1]$. Habituellement, un graphon est un modèle de graphes aléatoires échangeables selon le schéma suivant :

1. À chaque sommet $j$ du graphe est attribuée une valeur aléatoire indépendante $u_{j}\sim U[0,1]$
2. Une arête $(i,j)$ figure dans le graphe avec probabilité $W(u_{i},u_{j})$.

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 $W$ est parfois noté $\mathbb {G} (n,W)$, par analogie avec le modèle d'Erdős-Rényi (en) de graphes aléatoires. Un graphe généré à partir d'un graphon $W$ de cette manière est appelé un graphe $W$-aléatoire.

Il résulte de cette définition et de la loi des grands nombres que, si $W\neq 0$, les modèles de graphes aléatoires échangeables sont denses presque sûrement.

Exemples

L'exemple le plus simple d'un graphon est $W(x,y)\equiv p$ pour une constante $p\in [0,1]$. Dans ce cas, le modèle de graphes aléatoires échangeables associé est le modèle d'Erdős-Rényi (en) $G(n,p)$ qui contient chaque arête indépendamment avec probabilité $p$.

Plus généralement, on peut utiliser un graphon qui est constant par morceaux, en divisant le carré unité en $k\times k$ blocs, et en posant $W=p_{lm}$ sur le bloc d'indices $(l,m)$. Le modèle de graphes aléatoires échangeables qui en résulte est le modèle stochastique en blocs (en), 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 $k$ graphes d'Erdős-Rényi distincts avec les paramètres $p_{ll}$ respectivement, avec des bigraphes entre eux, où chaque arête possible entre les blocs $(l,l)$ et $(m,m)$ est incluse indépendamment avec la probabilité $p_{lm}$.

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 $n$ peut être représenté comme une matrice d'adjacence aléatoire $n\times n$. 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 $n\times n$ d'une matrice infinie de variables aléatoires ; cela permet de générer $G_{n}$ en ajoutant un nœud à $G_{n-1}$ et en échantillonnant les arêtes $(j,n)$ pour $j<n$. Dans cette perspective, les graphes aléatoires sont définis comme des tableaux infinis symétriques aléatoires $(X_{ij})$.

L'importance fondamentale des variables aléatoires échangeables (en) 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

$(X_{ij})\ {\overset {d}{=}}\,(X_{\sigma (i)\sigma (j)})$

pour toute permutation $\sigma$ d'entiers naturels, où ${\overset {d}{=}}$ 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 théorème de représentation de De Finetti (en) pour les séquences échangeables. Il s'agit d'un cas particulier du théorème d'Aldous-Hoover (en) pour les tableaux échangeables conjointement et, dans ce cadre, il affirme que la matrice aléatoire $(X_{ij})$ est générée comme suit :

1. échantilloner indépendamment $u_{j}\sim U[0,1]$
2. $X_{ij}=X_{ji}=1$ indépendamment aléatoirement avec une probabilité $W(u_{i},u_{j}),$

où $W:[0,1]^{2}\to [0,1]$ 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 $W$ ou les positions latentes des nœuds $u_{i}$ ; il existe deux aproches principales pour l'estimation du graphon. Une direction vise à estimer $W$ à une classe d'équivalence près , ou d'estimer la matrice de probabilités induite par $W$.

Formulation analytique

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

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

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

En général, pour une suite de graphes $(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 $(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 $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.

Exemples

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

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

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

Exemple 3: On considère une suite $(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 $(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 $K_{2,2}$ est donnée par

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

Quand $n$ 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 » $W$ défini par $W(x,y)=1$ si $\min(x,y)\leq 1/2$ et $\max(x,y)>1/2$, et $W(x,y)=0$ sinon.

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

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

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

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

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

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

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

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

${\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.$

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 $G(n,p)$ pour certains $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 $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 (en) 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 $G$ et $H$ est de comparer leurs nombres de sous-graphes. CEn d'autres termes, pour chaque graphe $F$, on compare le nombre de copies de $F$ dans $G$ et dans $H$. Si ces nombres sont proches pour chaque graphe $F$, alors intuitivement $G$ et $H$ 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 $F$ et $G$, la densité d'homomorphismes (en) $t(F,G)$ de $F$ dans $G$ est définie comme étant le nombre de morphismes de graphes de $F$ dans $G$. En d'autres termes, $t(F,G)$ est la probabilité pour qu'une fonction choisie au hasard des sommets de $F$ dans les sommets de $G$ envoie des sommets adjacents dans $F$ sur des sommets adjacents dans $G$.

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

$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é $[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 $1$. On peut alors étendre la définition de la densité d'homomorphismes à des graphons arbitraires $W$, en utilisant la même intégrale et en définissant

$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 $F$.

Limites en termes de densité d'homomorphismes

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

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

.

Distance de coupe

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

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

$\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 $S,T$ de l'intervalle unité.

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

$\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 $G$ et $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 $W$ et $U$ comme étant

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

où $W^{\varphi }(x,y)=W(\varphi (x),\varphi (y))$ est la composition de $W$ avec l'application $\varphi$, 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 $U\sim W$ quand $\delta _{\square }(U,W)=0$. L'espace de graphons résultant, noté ${\tilde {\mathcal {W}}}_{0}$, est un espace métrique pour $\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 $\{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.

Applications

Lemme de régularité

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

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

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