De nos jours, on regroupe souvent plusieurs modèles voisins sous l’appellation « Erdős-Rényi » et le plus naturel d’un point de vue probabiliste est certainement le suivant. On se fixe un entier naturel n ≥ 1 et l’on considère l’ensemble de sommets { ①, ②, …, ⓝ} où chaque paire de sommets distincts forme une arête.
Il y a donc (n2)\binom{n}{2} arêtes possibles ( (n2)\binom{n}{2} est bien sûr le coefficient binomial habituel, c’est-à-dire le nombre de manières de choisir 2 objets parmi n) et ces arêtes sont ajoutées l’une après l’autre uniformément au hasard. Ce procédé génère une suite croissante de graphes aléatoires (les arêtes étant ajoutées aléatoirement) notés
G(n,0)⊂G(n,1)⊂⋯⊂G(n,m)⊂⋯⊂G(n,(n2))G(n,0) \subset G(n,1) \subset \dots \subset G(n,m) \subset \dots \subset G\left(n, \binom{n}{2}\right)
où G(n, m) est le graphe obtenu après l’ajout de m arêtes.
En particulier, G(n,0) est composé de n sommets isolés alors que G(n,(n2))G\left(n,\binom{n}{2}\right) est le graphe complet, voir la figure ci-dessous.