Graphique aléatoire

Le terme « presque tous » dans le contexte des graphes aléatoires fait référence à une séquence d'espaces et de probabilités, telle que les probabilités d'erreur tendent vers zéro.

La théorie des graphes aléatoires étudie les propriétés typiques de ces graphes, c'est-à-dire celles qui se vérifient avec une forte probabilité pour des graphes issus d'une distribution particulière. Par exemple, on peut se demander, pour une valeur donnée de n, quelle est la probabilité que le graphe soit connexe . Dans l'étude de ces questions, les chercheurs s'intéressent souvent au comportement asymptotique des graphes aléatoires — les valeurs vers lesquelles convergent diverses probabilités lorsque n devient très grand. La théorie de la percolation caractérise la connexité des graphes aléatoires, en particulier ceux de taille infinie.

La percolation est liée à la robustesse du graphe (ou réseau). Étant donné un graphe aléatoire de nœuds et de degré moyen , on supprime aléatoirement une fraction de nœuds et il n'en reste qu'une fraction . Il existe un seuil de percolation critique en dessous duquel le réseau se fragmente, tandis qu'au-dessus, il forme une composante connexe géante.

La percolation localisée consiste à supprimer un nœud, ses voisins, puis ses plus proches voisins, etc., jusqu'à ce qu'une fraction des nœuds du réseau soit éliminée. Il a été démontré que, pour un graphe aléatoire dont les degrés suivent une loi de Poisson, le comportement est exactement le même que pour une suppression aléatoire.

Les graphes aléatoires sont largement utilisés dans la méthode probabiliste , où l'on cherche à démontrer l'existence de graphes possédant certaines propriétés. L'existence d'une propriété sur un graphe aléatoire peut souvent impliquer, grâce au lemme de régularité de Szemerédi , l'existence de cette propriété sur presque tous les graphes.

Dans les graphes réguliers aléatoires , sont les graphes -réguliers tels que et soient des nombres naturels, , et est pair.

La séquence des degrés d'un graphe dépend uniquement du nombre d'arêtes dans les ensembles

Si le nombre d'arêtes d'un graphe aléatoire est suffisamment grand pour garantir que presque chaque sommet a un degré minimal d'au moins 1, alors presque tout graphe est connexe et, si ce nombre est pair, presque chaque sommet admet un couplage parfait. En particulier, dès que le dernier sommet isolé disparaît dans presque tout graphe aléatoire, ce graphe devient connexe.

Presque tous les processus de graphes sur un nombre pair de sommets avec l'arête augmentant le degré minimum à 1 ou un graphe aléatoire avec un peu plus d' arêtes et avec une probabilité proche de 1 garantissent que le graphe a un couplage complet, à l'exception d'au plus un sommet.

Pour une certaine constante , presque tout graphe étiqueté à sommets et au moins arêtes est hamiltonien . Lorsque la probabilité tend vers 1, l'arête particulière qui augmente le degré minimal à 2 rend le graphe hamiltonien.

Les propriétés d'un graphe aléatoire peuvent changer ou rester invariantes sous l'effet de transformations de graphes. Mashaghi A. et al., par exemple, ont démontré qu'une transformation qui convertit les graphes aléatoires en leurs graphes duaux (ou graphes de lignes) produit un ensemble de graphes avec une distribution des degrés presque identique, mais avec des corrélations de degrés et un coefficient de clustering significativement plus élevé.

Étant donné un graphe aléatoire G d'ordre n dont l'ensemble des sommets V ( G ) = {1, ..., n } est déterminé par un algorithme glouton sur le nombre de couleurs, les sommets peuvent être colorés avec les couleurs 1, 2, ... (le sommet 1 est coloré en 1, le sommet 2 est coloré en 1 s'il n'est pas adjacent au sommet 1, sinon il est coloré en 2, etc.). Le nombre de colorations propres d'un graphe aléatoire, étant donné un nombre q de couleurs, appelé son polynôme chromatique , reste inconnu à ce jour. La mise à l'échelle des zéros du polynôme chromatique des graphes aléatoires, en fonction des paramètres n et du nombre d'arêtes m ou de la probabilité de connexion p, a été étudiée empiriquement à l'aide d'un algorithme basé sur la reconnaissance de motifs symboliques.

Considérons un modèle de graphe aléatoire donné, défini sur l'espace de probabilité , et soit une fonction à valeurs réelles qui associe à chaque graphe un vecteur de m propriétés. Pour un fixé , les graphes aléatoires conditionnels sont des modèles dans lesquels la mesure de probabilité attribue une probabilité nulle à tous les graphes tels que .

Les graphes aléatoires conditionnellement uniformes constituent un cas particulier : tous les graphes possédant des propriétés spécifiées se voient attribuer une probabilité égale. Ils peuvent être considérés comme une généralisation du modèle d'Erdős-Rényi G ( n , M ), lorsque l'information de conditionnement n'est pas nécessairement le nombre d'arêtes M , mais toute autre propriété arbitraire du graphe . Dans ce cas, très peu de résultats analytiques sont disponibles et la simulation est nécessaire pour obtenir des distributions empiriques des propriétés moyennes.

La première utilisation d'un modèle de graphe aléatoire remonte à 1938, par Helen Hall Jennings et Jacob Moreno, qui ont étudié un « sociogramme aléatoire » (un modèle d'Erdős-Rényi orienté) afin de comparer la proportion de liens réciproques dans leurs données de réseau avec celle du modèle aléatoire. Une autre utilisation, sous le nom de « réseau aléatoire », a été proposée par Ray Solomonoff et Anatol Rapoport en 1951, qui ont utilisé un modèle de graphes orientés avec un degré sortant fixe et des attaches aux autres sommets choisies aléatoirement.

Le modèle Erdős-Rényi de graphiques aléatoires a été défini pour la première fois par Paul Erdős et Alfréd Rényi dans leur article de 1959 « On Random Graphs » et indépendamment par Gilbert dans son article « Random graphs ».