Voir la source de Graphon

[[File:Exchangeable random graph from graphon.png|thumb|300px|upright=3|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 <math>n</math> est généré en assignant indépendamment à chaque sommet <math>k \in \{1,\dotsc,n\}</math> une variable aléatoire latente
    <math>U_{k} \sim \mathrm{U}(0,1)</math> (valeurs sur l'axe vertical) et
    comprenant chaque arête <math>(k,l)</math> indépendamment avec la probabilité <math>f(U_{k},U_{l})</math>.
    Par exemple, l'arête <math>(3,5)</math> (vert, pointillé) est présente avec la probabilité
    <math>f(0,72,0,9)</math> ; les cases vertes dans le carré de droite représentent les
    valeurs de <math>(u_{3},u_{5})</math> et <math>(u_{5},u_{3})</math>. La partie supérieure gauche
    montre la réalisation du graphe sous la forme d'une matrice d'adjacence.]]

En [[théorie des graphes]] et en [[statistique]], un '''graphon''' (aussi connu sous le terme '''limite de graphes''') est une [[fonction symétrique]] [[Mesure (mathématiques)|mesurable]]  <math>W:[0,1]^2\to[0,1]</math>, qui joue un rôle important dans l'étude des [[Densité d'un graphe|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 [[Graphe aléatoire|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 <math>W:[0,1]^{2}\to[0,1]</math>. Habituellement, un graphon est un modèle de graphes aléatoires échangeables selon le schéma suivant :

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

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

Il résulte de cette définition et de la [[loi des grands nombres]] que, si <math>W\neq0</math>, les modèles de graphes aléatoires échangeables sont denses presque sûrement<ref name=Orbanz:Roy:2015 />.

=== Exemples ===
L'exemple le plus simple d'un graphon est <math>W(x,y)\equiv p</math> pour une constante <math>p\in[0,1]</math>. Dans ce cas, le modèle de graphes aléatoires échangeables associé est le  {{Lien|trad=Erdős-Rényi model|fr=modèle d'Erdős-Rényi}} <math>G(n,p)</math> qui contient chaque arête indépendamment avec probabilité <math>p</math>.

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

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<ref name=Orbanz:Roy:2015 />.

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

L'importance fondamentale des {{Lien|trad=Exchangeable random variables|fr=variables aléatoires échangeables}}  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 [[Matrice aléatoire|matrices aléatoires]] satisfaisant

: <math> (X_{ij}) \  \overset{d}{=} \, (X_{\sigma(i)\sigma(j)})</math>

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

# échantillonner indépendamment <math>u_{j}\sim U[0,1]</math> 
# <math>X_{ij}=X_{ji}=1</math> indépendamment aléatoirement avec une probabilité <math>W(u_i,u_j),</math>

où <math>W :[0,1]^2\to[0,1]</math> 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 <math>W</math> ou les positions latentes des nœuds <math>u_i</math> ; il existe deux aproches principales  pour l'estimation du graphon.  Une direction vise à estimer <math>W</math> à une [[Relation d'équivalence|classe d'équivalence]] près
<ref>{{Lien arXiv
   | auteur = Patrick J. Wolfe et Sofia C. Olhede
   | titre = Nonparametric graphon estimation
   | année = 2013
   | version =
   | eprint = 1309.5936
   | libellé =
   | id =
 }}</ref>{{,}}<ref>
{{article|nom=Choi|prénom=David|nom2=Wolfe|prénom2=Patrick J.|date=February 2014|titre=Co-clustering separately exchangeable network data|arxiv=1212.4093|journal=The Annals of Statistics|volume=42|numéro=1|pages=29–63|doi=10.1214/13-AOS1173|issn=0090-5364}}.</ref>, ou d'estimer la matrice de probabilités induite par <math>W</math><ref>{{ article|nom=Gao|prénom=Chao|nom2=Lu|prénom2=Yu|nom3=Zhou|prénom3=Harrison H.|date=December 2015|titre=Rate-optimal graphon estimation|journal=The Annals of Statistics|volume=43|numéro=6|pages=2624–2652|doi=10.1214/15-AOS1354|arxiv=1410.5837}}</ref>{{,}}<ref>{{article |nom=Yuan|prénom=Zhang|nom2=Elizaveta|prénom2=Levina|nom3=Ji|prénom3=Zhu|date=2017|titre=Estimating network edge probabilities by neighbourhood smoothing|url=https://academic.oup.com/biomet/article-abstract/104/4/771/4158787?redirectedFrom=fulltext|journal=Biometrika|volume=104|numéro=4|pages=771–783|doi=10.1093/biomet/asx042}}.</ref>.

== Formulation analytique ==
Tout graphe <math>G</math> à <math>n</math> sommets <math>\{1, 2, \dots, n\}</math> peut être identifié à sa  [[matrice d'adjacence]] <math>A_G</math>.
Cette matrice correspond à une fonction en escalier <math>W_G : [0,1]^2 \to [0, 1]</math>, définie par le partitionnement <math>[0,1]</math> en intervalles 
<math>I_1, I_2, \dots, I_n</math>, où l'intervalle <math>I_j= ](j-1)/n,j/n[</math>
et, pour <math>(x,y)\in I_i\times I_j</math>, 
: <math>W_G(x,y)={A_G}_{ij}</math>.
La fonction <math>W_G</math> est le '''graphon associé''' au graphe <math>G</math>.

En général, pour une suite de graphes <math>(G_n)</math> 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 <math>(W_{G_n})</math>. 
Si ces graphes convergent (selon une définition appropriée de [[limite d'une suite|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 <math>W :[0,1]^{2}\to[0,1]</math> 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<ref name=Lovasz:2013 />. 

=== Exemples ===
'''Exemple 1''': On considère une suite aléatoire <math>(G_n)</math>  graphes d'Erdős-Rényi <math>G_n = G(n,p)</math> avec un paramètre fixe <math>p</math>.
Intuitivement, comme <math>n</math> 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 [[Convergence de variables aléatoires|presque sûrement]] vers fonction constante <math>W(x,y)\equiv p</math>, ce qui correspond à  l'intuition ci-dessus.

'''Exemple 2''': On considère la suite <math>(H_n)</math> de [[demi-graphe]]s définie en prenant pouur <math>H_n</math> le graphe bipartite sur les sommets <math>2n</math>u_1, u_2, \dots, u_<math>n</math> et <math>v_1, v_2, \dots, v_{n}</math> tels <math>u_i</math> soit adjacent à <math>v_j</math> quand <math>i\le j</math>. Si les sommets sont énumérés dans l'ordre, alors
la matrice d'adjacence <math>A_{H_n}</math> 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 <math>H_{3}</math> est donnée par
:<math block = "display"> \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}.</math>

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

'''Exemple 3''': On considère une suite <math>(K_{n,n})</math> de [[graphe biparti complet|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 <math>(K_{n,n})</math> est semblable à une matrice de diagonale, avec deux blocs de uns et deux blocs de zéros.
Par exemple, la matrice d'adjacence de <math>K_{2,2}</math> est donnée par
:<math block = "display"> \begin{bmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0  \end{bmatrix}.</math>

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

'''Exemple 4''':
On considère la suite <math>(K_{n,n})</math> 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 <math>K_{2,2}</math> est donnée par
: <math block = "display"> \begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0  \end{bmatrix}.</math> 

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

'''Exemple 6''': Étant donné le graphe <math>G</math> avec graphon associé <math>W = W_G</math>, on peut retrouver des paramètres du graphe  <math>G</math> en récupérant des transformations de <math>W</math>.

Par exemple, la densité des arêtes (c'est-à-dire le degré moyen divisé par le nombre de sommets) de <math>G</math> est donnée par l'intégrale
:<math block = "display"> \int_{0}^1 \int_0^1 W(x,y) \; \mathrm{d}x \, \mathrm{d}y</math>.
En effet, <math>W</math> est à valeurs dans <math>\{0,1\}</math>, et chaque chaque <math>(i, j)</math>
de <math>G</math> 
correspond à une région <math>I_i \times I_j</math>
de surface <math>1/n^2</math> où <math>W</math> est égal à <math>1</math>.

Un raisonnement similaire montre que le nombre de triangles de <math>G</math> est égal à
:<math block = "display"> \frac 16 \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 .</math>

=== 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 <math>G(n,p)</math> pour certains <math>p</math> 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 <math>n</math>.

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 [[théorie de la divergence|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]]{{refm|qrandom}}.

==== Nombre de sous-graphes ====

Une façon de mesurer la distance entre deux graphes <math>G</math> et <math>H</math> est de comparer leurs nombres de sous-graphes.
CEn d'autres termes, pour chaque graphe <math>F</math>, on compare le nombre de copies de <math>F</math> dans <math>G</math> et dans <math>H</math>.
Si ces nombres sont proches pour chaque graphe <math>F</math>, alors
intuitivement <math>G</math> et <math>H</math> 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 <math>F</math> et <math>G</math>, la 
{{Lien|trad=Homomorphism density|fr=densité d'homomorphismes|texte=densité d'homomorphismes}} <math>t(F, G)</math> de <math>F</math> dans <math>G</math> est définie comme étant le nombre de [[morphisme de graphes|morphismes de graphes]] de <math>F</math> dans <math>G</math>.
En d'autres termes, <math>t(F,G)</math> est la probabilité pour qu'une fonction choisie au hasard des sommets de <math>F</math> dans les sommets de <math>G</math> envoie des sommets adjacents dans <math>F</math> sur des sommets adjacents dans <math>G</math>.

Les graphons offrent un moyen simple de calculer les densités d'homomorphismes.
En effet, pour un graphe <math>G</math> avec graphon associé <math>W_G</math> et un autre graphe <math>F</math>, on a
:<math block = "display"> 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)}</math>,
où l'intégrale est multidimensionnelle, et évaluée sur l' hypercube unité <math>[0,1]^{V(F)}</math>.
Ceci découle de la définition d'un graphon associé, quand on considère le cas où l'intégrale ci-dessus vaut <math>1</math>.
On peut alors étendre la définition de la densité d'homomorphismes à des graphons arbitraires <math>W</math>, en utilisant la même intégrale et en définissant
:<math block = "display"> 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)}</math>
pour tout graphe <math>F</math>.

===== Limites en termes de densité d'homomorphismes =====
Dans ce cadre, une suite de graphes <math>(G_n)</math> est dite convergente si, pour chaque graphe fixé <math>F</math>, la suite de densités d'homomorphismes <math>\left(t(F, G_n)\right)</math> converge. Bien que cela ne résulte pas immédiatement de la définition, si <math>(G_n)</math> converge en ce sens, alors il existe un graphon <math>W</math> tel que, pour chaque graphon <math>F</math>, on ait également
:<math display = "block"> \lim_{n\to\infty} t(F, G_n) = t(F, W)</math>.

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

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

: <math block = "display"> \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|</math>

prise sur tous les sous-ensembles mesurables <math>S, T</math> de l'intervalle unité{{refm|Lovasz:2013}}.

Cette norme étend la notion de distance définie plus haut, car pour deux graphes <math>G</math> et <math>H</math> avec un même ensemble <math>V</math> de <math>n</math> sommets, la norme de coupe avec les graphons associés
:<math block = "display"> \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|</math>
permet de calculer la discrépance maximale des densités d'arêtes entre <math>G</math> et <math>H</math>. 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 <math>W</math> et <math>U</math> comme étant 

:<math block = "display"> \delta_\square(U, W) = \inf_{\varphi} \lVert U - W^\varphi \rVert_\square</math>

où <math>W^\varphi(x,y) = W(\varphi(x), \varphi(y))</math> est la composition de <math>W</math> avec l'application <math>\varphi</math>, et l'infimum est pris sur toutrd les mesures bijections préservant les mesures de l'intervalle unité dans lui-même{{refm|whatis}}.
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 <math>U \sim W</math> quand <math>\delta_\square(U, W) = 0</math>. L'espace de graphons résultant, noté <math>\tilde{\mathcal{W}}_0</math>, est un [[espace métrique]] pour <math>\delta_\square</math>.

Cet espace est [[Compacité (mathématiques)|compact]]. De plus, l'ensemble de tous les graphes est une [[partie dense]] de l'espace. Les graphes sont identifiés comme des [[Fonction étagée|fonctions en escalier]] à valeurs dans <math>\{0,1\}</math> sur le  carré unité. Ces observations montrent que l'espace des graphons est  l'[[espace complet|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 <math>(\tilde{\mathcal{W}}_0, \delta_{\square})</math>, on peut prouver des versions plus fortes du [[lemme de régularité de Szemerédi]].

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

== Généralisations ==
Les graphons sont naturellement associés aux graphes simples denses. 
Il existe des extensions de ce modèle à des [[Graphe orienté|graphes orientés]] denses pondérés, souvent appelés graphons décorés{{refm|decorate}}. Il existe également des extensions récentes à la famille des graphes creux, tant du point de vue des modèles de graphes aléatoires<ref name=Veitch:Roy:2015 /> que de la théorie des limites des graphes<ref name=Borgs:Chayes:Cohn:Zhao:2014:sgc1 />{{,}}<ref name=Borgs:Chayes:Cohn:Zhao:2014:sgc2 />.

== Notes et références ==
{{Traduction/référence|en|Graphon|976161163}}
<references>
<ref name = qrandom>{{Article
  | nom1 = Chung | prénom1 = Fan R. K. | lien auteur1 = Fan Chung
  | lien auteur2 = Ronald Graham | nom2 = Graham | prénom2 = Ronald L.
  | nom3 = Wilson | prénom3 = R. M.
  | titre = Quasi-random graphs
  | journal = [[Combinatorica]]
  | année = 1989
  | volume = 9
  | numéro = 4
  | pages = 345–362
  | doi = 10.1007/BF02125347 }}
</ref>

<ref name = decorate>{{article
  | auteur = Vinay A. Vaishampayan 
  | titre  = Classification in a Large Network
  | date   = 2019 
  | périodique =  2019 IEEE International Symposium on Information Theory (ISIT)
  | pages=1807–1811
  | doi=10.1109/ISIT.2019.8849301
  | arxiv = 1902.05531}}
</ref>

<ref name = norms>{{Article
  | nom1 = Hatami | prénom1 = H. | lien auteur1 = Hamed Hatami
  | titre = Graph norms and Sidorenko's conjecture
  | journal = [[Israel Journal of Mathematics]]
  | année = 2010
  | volume = 175
  | numéro = 1
  | pages = 125–150
  | doi = 10.1007/s11856-010-0005-1 | arxiv = 0806.0047 }}
</ref>

<ref name = sidorenko>{{Article
  | nom1 = Sidorenko | prénom1 = A. | lien auteur1 = Alexander Sidorenko
  | titre = A correlation inequality for bipartite graphs
  | journal = [[Graphs and Combinatorics]]
  | année = 1993
  | volume = 9
  | numéro = 2–4
  | pages = 201–204
  | doi = 10.1007/BF02988307}}
</ref>

<ref name = whatis>{{Article
  | nom1 = Glasscock | prénom1 = D. | lien auteur1 = Daniel Glasscock
  | titre = What is a graphon
  | journal = [[Notices of the American Mathematical Society]]
  | année = 2015
  | volume = 62
  | numéro = 1
  | pages = 46–48
  | arxiv = 1611.00718}}
</ref>

<ref name=Veitch:Roy:2015>{{article| nom1 = Veitch| prénom1 = Victor| nom2 = Roy| prénom2 = Daniel M. | titre = The Class of Random Graphs Arising from Exchangeable Random Measures |périodique = ArXiv |arxiv=1512.03099| class = math.ST| année = 2015}}</ref>

<ref name=Borgs:Chayes:Cohn:Zhao:2014:sgc1>{{Article|nom1=Borgs|prénom1=Christian|nom2=Chayes|prénom2=Jennifer T.|nom3=Cohn|prénom3=Henry|nom4=Zhao|prénom4=Yufei| titre = An ''L''<sup>''p''</sup> theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions | journal = [[Transactions of the American Mathematical Society]]| volume = 372| numéro = 5| pages = 3019–3062|arxiv=1401.2906 | année = 2019| doi = 10.1090/tran/7543}}</ref>

<ref name=Borgs:Chayes:Cohn:Zhao:2014:sgc2>{{Article|nom1=Borgs|prénom1=Christian|nom2=Chayes|prénom2=Jennifer T.|nom3=Cohn|prénom3=Henry|nom4=Zhao|prénom4=Yufei| titre = An ''L''<sup>''p''</sup> theory of sparse graph convergence II: LD convergence, quotients, and right convergence | journal = [[Annals of Probability|The Annals of Probability]]| volume = 46| numéro = 1| pages = 337–396|arxiv=1408.0744| année = 2018| doi = 10.1214/17-AOP1187}}</ref>

<ref name=Lovasz:2013>{{Ouvrage| éditeur = [[American Mathematical Society]]| auteur1 = László Lovász| titre = Large Networks and Graph Limits | date = 2012 | pages totales = 475 |isbn= 9780821890851| collection = American Mathematical Society colloquium publications | numéro dans collection = 60}}</ref>

<ref name=Orbanz:Roy:2015>{{Article| volume = 37| numéro = 2| pages = 437–461| nom1 = Orbanz| prénom1 = P.| nom2 = Roy| prénom2 = D.M.| titre = Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures| journal = [[IEEE Transactions on Pattern Analysis and Machine Intelligence]]| doi=10.1109/tpami.2014.2334607| pmid = 26353253| arxiv = 1312.7857| année = 2015}}
</ref>

</references>

{{portail|mathématiques|probabilités et statistiques}}

[[Catégorie:Théorie des graphes]]
[[Catégorie:Graphe aléatoire]]