Graphes aléatoires : deux modèles.

L'étude des graphes aléatoires consiste  à  se donner des distributions de probabilités sur les graphes (par exemple, pour tout n, je me donne telle distribution sur les graphes à n sommets, càd. une probabilité pour chacun de ces graphes d'être tiré au sort ou d'apparaître), puis à analyser ensuite :

• les probabilités d'avoir certaines propriétés (par exemple être connexe ou avoir des sommets isolés),
• les variables aléatoires correspondants à certains paramètres (par exemple le diamètre ou le nombre chromatique),
• la complexité d'algorithmes où les entrées sont les graphes se présentant selon la distribution de probabilité (la complexité en temps ou en espace est dans ce cas une valeur aléatoire dont on peut quantifier par exemple la valeur moyenne, on fait alors de l'analyse en moyenne).
  

Parmi les problématiques ayant stimulées la recherche sur les graphes aléatoires, on peut citer :

• la théorie des graphes et la combinatoire, où l'introduction de distributions de probabilités et l'usage d'inégalités classiques de théorie des probabilités a permis de démontrer des théorèmes d'existence (preuve par comptage, mais en plus raffiné, aussi appelé "la méthode probabiliste"),
• la description de phénomènes physiques avec des graphes, mais avec aussi une composante aléatoire (par exemple pour des phénomènes de percolation en physique),
• la description des graphes que l'on rencontre dans la vraie vie de tous les jours (par exemple les graphes de réseaux intranet ou internet), et qui seront donc les vrais entrées des algorithmes (par exemple les entrées qui produisent les pires complexités ne se présentent pratiquement jamais, alors l'algorithme pourra être très performant en pratique).
  

L'objectif ici est de présenter deux modèles de graphes aléatoires et de les comparer :

• Modèle A : étant donnés n sommets et un paramètre réel 0<p<1, alors pour toute paire de sommets (et indépendamment les unes des autres), il existe une arête avec probabilité p. Cela fournit une distribution sur les graphes à n sommets. Souvent désigné comme le modèle de Erdös-Renyi.
  
• Modèle B : génération aléatoire de graphes dont on a fixé la séquence des degrés.
  

Présenter plus formellement ces deux modèles et tenter de les comparer (par exemple pour le même nombre moyen d'arêtes, se comportent-ils pareil pour la connexité ?). Qu'est-ce qui les différencie ?


Attention : plus facile avec quelques notions de base en probabilités et en séries génératrices.

Quelques références (pas exhaustif).

• Introduction to Graph Theory, livre de D. West, Prentice Hall (2001). La section 8.5 présente des résultats avec leurs preuves sur le modèle A.
• Random Graphs, livre de B. Bollobas, Cambridge University Press (2001).
  
• Random graphs with arbitrary degree distributions and their applications, article de M. Newman, S. Strogatz  et D. Watts dans Physical Review E (2001). Présentation du modèle B.
  

Retour à la page des sujets.