En mathématiques, un graphe aléatoire est un graphe généré par un processus aléatoire. 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 1968[1][source insuffisante].

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

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

Il y a deux modèles d'Erdős et Rényi, formellement différents, mais é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 {1, 2, 3, ..., n} noté par la suite  ;
  • les arêtes potentiellement présentes sont les n(n–1)/2 parties à deux éléments de  ; l'ensemble de ces arêtes est parfois noté   Il sera noté toutefois J pour des raisons de commodité typographique, et de cohérence avec l'article sur l'inégalité de Harris.

Le graphe aléatoire binomial modifier

Dans ce modèle, souvent noté   chacune des n(n–1)/2 arêtes potentielles est présente avec probabilité p, et absente avec probabilité 1-p, cela indépendamment du statut des autres arêtes. Le cas p = 0,5 a été étudié par Erdős dès 1947[2]. Le nombre Np d'arêtes de   suit la loi binomiale de paramètres n(n–1)/2 et p.

Le graphe aléatoire uniforme modifier

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

 

C'est le modèle   qui est principalement étudié dans la série d'articles fondateurs publiés par Erdős et Rényi entre 1959 et 1968[3].

Les deux processus aléatoires à valeurs graphe modifier

  • On peut partir d'un graphe sans arêtes, donc totalement déconnecté, et ajouter une arête tirée au hasard uniformément, puis une autre, etc., sans remise. On obtient ainsi une suite   croissante (au sens de l'inclusion de l'ensemble des arêtes), de 1 + n(n–1)/2 graphes aléatoires, qui forme un processus à temps discret à valeurs dans l'ensemble des graphes. Chaque terme de la suite est un graphe aléatoire uniforme défini à la section précédente. Un avantage de cette construction est de voir coexister différents graphes aléatoires de paramètres M 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 e de J une variable aléatoire Te, le poids de l'arête, de sorte que la famille (Te)eJ soit une famille de variables aléatoires i.i.d., par exemple de loi uniforme sur l'intervalle [0, 1]. On note alors   le graphe formé des arêtes dont le poids est inférieur à p. Pour chaque arête, cela se produit avec probabilité
 
On obtient ainsi une famille   croissante, de graphes aléatoires, qui forme un processus à temps continu, à valeurs dans l'ensemble des graphes. Cette famille est croissante au sens de l'inclusion de l'ensemble des arêtes : une arête e présente dans   est aussi présente dans   puisque   Chaque terme de la famille de graphes est un graphe aléatoire binomial défini précédemment.

Métaphore. On peut imaginer les sommets du graphe comme n îles sur un lac, communicant à l'aide de passerelles (les arêtes e), submergées à des profondeurs respectives Te 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 modifier

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 Np d'un graphe aléatoire de loi   est donc très proche de   surtout si cette dernière quantité   est grande devant n : en effet[4],

 

De plus, la loi conditionnelle de   sachant que Np = M est précisément   Pour cette raison, si M est proche de  , ou, de manière équivalente, si

 

il est généralement admis (et souvent démontré[5]) que les deux modèles   et   ont des propriétés très proches.

En poussant plus loin, notons T(k) la k-ième valeur de la suite   une fois que cette dernière suite est rangée dans l'ordre croissant : la suite   est appelée la suite des statistiques d'ordre de la suite   Lorsque p prend la valeur aléatoire T(M), alors   est exactement   Pour corroborer les observations précédentes, notons que T(M) est très proche de   au sens où, en conséquence de résultats célèbres de Donsker et de Kolmogorov[6], la probabilité

 

satisfait

 

les 1er et 4e termes étant les queues de distribution des lois de Rayleigh et de Kolmogorov, respectivement : en résumé, le supremum (lorsque M varie) des erreurs   est de l'ordre de 1/n.

Ordre et croissance modifier

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 à {0,1}J. 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
 
  • Une partie A de Ω est dite croissante si
 
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.
Exemples :

Parmi les propriétés et paramètres d'un graphe,

  • la connexité est croissante, c.-à-d. la partie A de Ω constituée de tous les graphes connexes, est une partie croissante de Ω : si on ajoute une arête à un graphe connexe, le graphe ainsi obtenu est encore connexe ;
  • la planarité est décroissante : si on enlève une arête à un graphe planaire, le graphe ainsi obtenu est encore planaire ;
  • le nombre chromatique est croissant ;
  • le nombre de stabilité est décroissant ;
  • la propriété triangle-free est décroissante.

On a l'inégalité suivante :

Inégalité de Harris — Dans le cadre du graphe aléatoire binomial,

  • soit deux variables aléatoires X et Y croissantes sur Ω. Alors
 
  • soit deux parties croissantes A et B de Ω. Alors
 
Remarques :
  • Cela revient à dire qu'il y a une corrélation positive entre les variables concernées, puisqu'on peut reformuler la première inégalité sous la forme suivante en utilisant la covariance :
 
  • L'inégalité vaut aussi pour des variables ou des parties décroissantes, mais le sens des inégalités change lorsque les variables ou les parties concernées ont des sens de monotonie opposés.

La connexité modifier

Le seuil de connexité modifier

Théorème (Erdős, Rényi, 1960) — Posons an = np(n) — ln n, ou encore :

 
  • Si   alors
     
  • Si   alors
     

On dit que ln(n)/n 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   tend vers l'infini strictement moins vite que  

Énumération des points isolés modifier

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 f(k) = k(n – k) 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,   qui vaut approximativement e–ec En effet, on a le résultat suivant :

Points isolés (Erdős, Rényi, 1960). —  Supposons que

 

Alors le nombre Xn de points isolés du graphe   converge en loi vers une loi de Poisson de paramètre ec.

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 (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 modifier

Erdős et Rényi en déduisent un résultat plus précis que la propriété de seuil étroit :

Théorème double-exponentiel (Erdős, Rényi, 1960) —  Supposons que

 
Alors
 

Notons Tn le premier instant t où le graphe   est connexe :

 

de sorte que

 

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

 

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

 

Le graphe aléatoire infini modifier

Erdős et Rényi ont généralisé le modèle binomial au cas d'un graphe infini dénombrable[réf. souhaitée], 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 modifier

Notes modifier

  1. Le premier article, publié en 1959, est "On Random Graphs I", Publ. Math. Debrecen 6, 290.
  2. (en) P. Erdős, « Some remarks on the theory of graphs », Bull. Amer. Math. Soc., vol. 53, no 4,‎ , p. 292-294 (lire en ligne). On considère souvent cet article comme marquant la naissance de la « méthode probabiliste » pour l'étude des graphes non aléatoires, en particulier pour la théorie de Ramsey.
  3. Pour un historique, voir (en) M. Karoński et A. Ruciński, « The origins of the theory of random graphs », dans The Mathematics of Paul Erdős, Berlin, Springer, coll. « Algorithms Combin. » (no 13), , p. 311-336.
  4. Pour plus de détails, voir Janson, Łuczak et Ruciński 2000, chap. 2, « Exponentially small probabilities ».
  5. Voir Janson, Łuczak et Ruciński 2000, section 1.4, « Asymptotic equivalence », p. 14.
  6. Voir (en) Galen R. Shorack et Jon A. Wellner, Empirical Processes With Applications to Statistics, SIAM, , 998 p. (ISBN 978-0-89871-684-9, lire en ligne), section 3.8, « Limiting distributions under the null hypothesis », p. 142, et chap. 18, « The Standardized Quantile Process », p. 637.
  7. a et b Janson, Łuczak et Ruciński 2000, Th. 6.7, p. 144.
  8. Voir l'article « Bijection de Joyal », ou bien Martin Aigner et Günter M. Ziegler, Raisonnements divins, 2e édition, 2006, p. 195-201, La formule de Cayley pour le nombre d’arbres.

Bibliographie modifier

Article connexe modifier

Introduction de probabilités en théorie des graphes

Lien externe modifier

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