Graphe aléatoire

Graphe orienté aléatoire avec 20 nœuds et une probabilité de présence d'arête égale à 0,1.

Un graphe aléatoire est un graphe généré par un processus aléatoire.

Les modèles de base d'Erdős et Rényi

Le premier modèle de graphes aléatoires a été popularisé par Paul Erdős et Alfréd Rényi dans une série d'articles publiés entre 1959 et 1968Modèle:Référence insuffisante.

Il y a deux modèles d'Erdős et Rényi, étroitement liés : le graphe aléatoire binomial et le graphe aléatoire uniforme. Dans les deux modèles, il s'agit d'un graphe aléatoire non orienté, qui n'a ni boucles, ni arêtes multiples. On utilise les notations suivantes :

• l'ensemble des sommets est Modèle:Math noté par la suite $[[n]]$;
• les arêtes potentiellement présentes sont les Modèle:Math parties à deux éléments de $[[n]]$; l'ensemble de ces arêtes est parfois noté $(\genfrac{}{}{0ex}{}{[[n]]}{2}).$ Il sera noté toutefois Modèle:Mvar pour des raisons de commodité typographique, et de cohérence avec l'article sur l'inégalité de Harris.

Le graphe aléatoire binomial

Dans ce modèle, souvent noté $𝔾(n,p),$ chacune des Modèle:Math arêtes potentielles est présente avec probabilité Modèle:Mvar, et absente avec probabilité Modèle:Math, cela indépendamment du statut des autres arêtes. Le cas Modèle:Math a été étudié par Erdős dès 1947. Le nombre Modèle:Mvar d'arêtes de $𝔾(n,p)$ suit la loi binomiale de paramètres Modèle:Math et Modèle:Mvar.

Le graphe aléatoire uniforme

Dans ce modèle, souvent noté $𝔾(n,M),$ on choisit uniformément un sous-ensemble de M arêtes parmi les Modèle:Math arêtes possibles. Si on considère un graphe G à n sommets et M arêtes, la probabilité d'obtenir G par ce modèle est donnée par :

$\mathbb{P}(𝔾(n,M)=G)=\frac{1}{(\genfrac{}{}{0ex}{}{(\genfrac{}{}{0ex}{}{n}{2})}{M})}.$

C'est le modèle $𝔾(n,M)$ qui est principalement étudié dans la série d'articles fondateurs publiés par Erdős et Rényi entre 1959 et 1968.

Les deux processus aléatoires à valeurs graphe

On peut partir d'un graphe sans arêtes, donc totalement déconnecté, et ajouter une arête tirée au hasard uniformément dans Modèle:Mvar, puis une autreModèle:Etc., sans remise.

On obtient ainsi une suite finie $\{𝔾(n,M){\}}_{0\le M\le n(n-1)/2}$ de Modèle:Math graphes aléatoires uniformes (comme défini à la section précédente). Cette suite est croissante au sens de l'inclusion de l'ensemble des arêtes et forme un processus à temps discret à valeurs dans l'ensemble des graphes.

Un avantage de cette construction est de voir coexister différents graphes aléatoires de paramètres Modèle:Mvar différents, sur le même espace probabilisé, et de pouvoir ainsi comparer leurs caractéristiques, non pas en moyenne ou en loi, mais pour chaque élément ω de l'espace probabilisé considéré. Cela permet de raisonner par couplage.

On peut aussi associer à chaque arête Modèle:Mvar de Modèle:Mvar une variable aléatoire Modèle:Math, le poids de l'arête, de sorte que la famille Modèle:Math soit une famille de variables aléatoires i.i.d., par exemple de loi uniforme sur l'intervalle [0, 1]. On note alors $𝔾(n,p)$ le graphe formé des arêtes dont le poids est inférieur à p. Pour chaque arête, cela se produit avec probabilité

$\mathbb{P}(T_e\le p)=p.$

On obtient ainsi une famille

$\{𝔾(n,p){\}}_{0\le p\le 1}$

de graphes aléatoires binomiaux (comme défini précédemment). Cette famille est croissante au sens de l'inclusion de l'ensemble des arêtes ; en effet une arête Modèle:Mvar présente dans

$𝔾(n,p)$

est aussi présente dans

$𝔾(n,p^{\prime })$

dès que

$p^{\prime }\ge p$

puisque

$\{T_e\le p\}\Rightarrow \{T_e\le p^{\prime }\}$

. De plus, cette famille forme un processus à temps continue à valeurs dans l'ensemble des graphes.

Métaphore : on peut voir les sommets du graphe comme n îles sur un lac, communicant à l'aide de passerelles (les arêtes e), submergées à des profondeurs respectives Modèle:Mvar sous la surface de l'eau. Si le lac se vide de son eau graduellement, on va voir émerger progressivement les passerelles, et des composantes connexes regroupant de plus en plus d'îles vont se former.

Liens entre les deux modèles

En vertu du théorème central limite, ou de l'inégalité de Hoeffding, la loi binomiale est très concentrée autour de son espérance. Plus précisément, le nombre d'arêtes Modèle:Mvar d'un graphe aléatoire de loi $𝔾(n,p)$ est donc très proche de $\hat{M}=\lfloor p(\genfrac{}{}{0ex}{}{n}{2})\rfloor$ surtout si cette dernière quantité $\hat{M}$ est grande devant n : en effet,

$\mathrm{\forall }t>0,\mathbb{P}(|N_p-\hat{M}|\ge tn)\le 2{\mathrm{e}}^{-2t^2}.$

De plus, la loi conditionnelle de $𝔾(n,p)$ sachant que Modèle:Mvar est précisément $𝔾(n,M).$ Pour cette raison, si Modèle:Mvar est proche de $\hat{M}$, ou, de manière équivalente, si

$p\simeq \frac{2M}{n(n-1)},$

il est généralement admis (et souvent démontré) que les deux modèles $𝔾(n,p)$ et $𝔾(n,M)$ ont des propriétés très proches.

En poussant plus loin, notons Modèle:Math la k-ième valeur de la suite $(T_e{)}_{e\in J}$ une fois que cette dernière suite est rangée dans l'ordre croissant : la suite $(T_{(k)}{)}_{1\le e\le n(n-1)/2}$ est appelée la suite des statistiques d'ordre de la suite $(T_e{)}_{e\in J}.$ Lorsque p prend la valeur aléatoire Modèle:Math, alors $𝔾(n,T_{(M)})$ est exactement $𝔾(n,M).$ Pour corroborer les observations précédentes, notons que Modèle:Math est très proche de $2M/n(n-1),$ au sens où, en conséquence de résultats célèbres de Donsker et de Kolmogorov, la probabilité

${\phi }_n(x)=\mathbb{P}(\underset{1\le M\le n(n-1)/2}{\sup }\{|T_{(M)}-\frac{2M}{n(n-1)}|\}\ge \frac{x\sqrt{2}}{n})$

satisfait

$\exp (-2x^2)\le \underset{n}{\mathrm{lim\; inf}}{\phi }_n(x)\le \underset{n}{\mathrm{lim\; sup}}{\phi }_n(x)\le 2\sum _{r=1}^{+\mathrm{\infty }}(-1{)}^{r-1}\exp (-2r^2{x}^2),$

les Modèle:1er et Modèle:4e membres étant les queues de distribution des lois de Rayleigh et de Kolmogorov, respectivement : en résumé, le supremum (lorsque M varie) des erreurs $|T_{(M)}-2M/n(n-1)|$ est de l'ordre de 1/n.

Ordre et croissance

Un graphe peut être vu comme une partie de l'ensemble J des arêtes, donc l'espace probabilisé est ici l'ensemble Ω des parties de J, qu'on peut parfois identifier à Modèle:Math. Cette identification est en particulier utile lorsqu'on veut appliquer l'inégalité de Harris.

• L'inclusion est une relation d'ordre partielle sur Ω.
• Comme d'ordinaire, une application X définie sur Ω, à valeurs réelles, est dite croissante si

$\{\omega \le {\omega }^{\prime }\}\Rightarrow \{X(\omega )\le X({\omega }^{\prime })\}.$

• Une partie A de Ω est dite croissante si

$\{\omega \le {\omega }^{\prime }\text{et}\omega \in A\}\Rightarrow \{{\omega }^{\prime }\in A\}.$

De manière équivalente, une partie A de Ω est dite croissante si sa fonction indicatrice est croissante.

• La propriété de décroissance d'une application ou d'une partie a une définition analogue.

Modèle:Exemple On a l'inégalité suivante : Modèle:Théorème Modèle:Exemple

La connexité

Le seuil de connexité

Modèle:Théorème On dit que Modèle:Math est un seuil étroit pour la propriété de connexité, l'étroitesse faisant référence au fait que la propriété est vérifiée même si $a_n$ tend vers l'infini strictement moins vite que $\ln n.$

Énumération des points isolés

Il est plus facile (plus probable) de réussir à couper les n – 1 connexions entre un point et son complémentaire, que les k(n – k) connexions entre un groupe de k points et son complémentaire, car la fonction Modèle:Math augmente très rapidement au voisinage de 1, d'où, lorsque k augmente, beaucoup plus d'arêtes à couper, et une probabilité bien plus faible de réussir à les couper toutes. En corollaire, avec le choix du paramètre p fait plus haut, le graphe G(n, p) sera non connexe « presque uniquement » s'il a des points isolés, au sens où la probabilité d'être connexe est très proche de la probabilité de ne pas avoir de points isolés, $\mathbb{P}(X_n=0),$ qui vaut approximativement Modèle:Math En effet, on a le résultat suivant : Modèle:Théorème Modèle:Démonstration Ce théorème est une illustration frappante du paradigme de Poisson, selon lequel, lorsque se présente un grand nombre d'opportunités d'observer un événement rare (Modèle:C.-à-d. peu probable), alors le nombre total d'événements rares effectivement observés suit une loi de Poisson.

Le théorème double-exponentiel

Erdős et Rényi en déduisent un résultat plus précis que la propriété de seuil étroit : Modèle:Théorème Modèle:Démonstration Notons Modèle:Mvar le premier instant t où le graphe $𝔾(t,n)$ est connexe :

$T_n=\inf \{t\ge 0|𝔾(t,n)\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{e}\},$

de sorte que

$\left\{𝔾(t,n)\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{e}\right\}\Rightarrow \{T_n\le t\}\Rightarrow \{\mathrm{\forall }\epsilon >0,𝔾(t+\epsilon ,n)\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{e}\}.$

On peut alors voir le théorème double-exponentiel comme un résultat sur le développement asymptotique de Modèle:Mvar : si Modèle:Mvar est défini par la relation suivante :

$T_n=\frac{\ln n}{n}+\frac{Z_n}{n},$

alors le théorème double-exponentiel stipule que Modèle:Mvar converge en loi vers la distribution de Gumbel, ce qui pourrait se traduire, dans une version probabiliste de la notation de Landau, par :

$T_n=\frac{\ln n}{n}+\mathrm{\Theta }\left(\frac{1}{n}\right).$

Le graphe aléatoire infini

Modèle:Article détaillé Erdős et Rényi ont généralisé le modèle binomial au cas d'un graphe infini dénombrableModèle:Refsou, montrant qu'on obtenait alors (presque sûrement) un graphe possédant des propriétés d'universalité (contenant en particulier tout graphe fini ou dénombrable comme sous-graphe) ; ce graphe a été redécouvert à plusieurs reprises et est le plus souvent connu sous le nom de graphe de Rado.

Voir aussi

Bibliographie

• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Chapitre.

Article connexe

Introduction de probabilités en théorie des graphes

Lien externe

• Laurent Massoulié, Réseaux: contrôle distribué et phénomènes émergents, 2015