Dans la théorie des graphes aléatoires, la plus grande découverte de Erdös et Rényi est que de nombreuses propriétés topologiques apparaissent subitement. En d’autres termes, à partir d’une certaine probabilité, la plupart des graphes aléatoires ont une certaine propriété. C’est pour cette raison que nous pouvons introduire la notion de probabilité critique. Et la connaissance de celle-ci permet de connaître les grandes tendances de l’évolution d’un graphe aléatoire. Cette catégorisation est aisément interprétable dans la théorie de la percolation puisqu’elle correspond à un changement de phase global de la nature du graphe par l’émergence de la propriété considérée et ceci est particulièrement fréquent par les systèmes de petites dimensions. Par contre, pour les réseaux qui sont par nature de dimension infinie, la situation est radicalement différente. Des graphes plus grands ayant la même probabilité d’occupation auront plus d’arêtes et donc l’apparition de cycles par exemple sera déjà effective avec une probabilité moindre. Cela signifie qu’il n’y a pas unicité de la criticité globale même si le degré moyen du graphe a une valeur critique indépendante de la taille ; phénomène qui n’est pas sans rappeler le multifractal.

L’un des premiers problèmes à résoudre pour comprendre la topologie locale d’un graphe aléatoire est l’apparition de sous-graphes. Les exemples les plus simples de sous-graphes sont les cycles, les arbres et les graphes complets. Cependant comme ces structures ont été très étudiées en théorie des graphes en particulier via la vision de Ramsey, leur apparition apporte de nombreuses informations sur la catégorie du graphe considéré et ce d’autant plus que nous déterminons explicitement la probabilité critique à partir de laquelle presque tout graphe contient un sous-graphe à n sommets et l arêtes i.e. Pc(N)= cN-k/l. Ces données bien que probabilistes et globales donnent non seulement des informations locales mais permettent de dépasser des difficultés combinatoires insurmontables autrement.

En généralisant cette approche nous pouvons atteindre des résultats prédits par la théorie de la percolation en particulier le changement de phase global d’une structure composée de clusters indépendants en une structure dominée par un cluster géant. Cela permet entres autres d’absorber les résultats de connectivité puisque nous avons de facto une connectivité forte. L’un des cas les plus intéressants pour traiter la percolation au sens de la criticité, ce sont les arbres de Cayley. En effet pour ces arbres n-aires complets i.e. chaque noeud a n voisins exceptés les feuilles qui sont unaires, les calculs peuvent être menés à leur terme, procurant ainsi un modèle concret avec une interprétation qualitative puisque nous pouvons déterminer si la structure est arbrifiée, fractale ou compacte.

Seulement les petits mondes obéissent à d’autres règles et pour capturer leur différence comportementale en terme d’évolution nous devons généraliser les graphes aléatoires de la théorie de Erdös-Rényi pour rendre compte de la loi-puissance. Pour cela il est nécessaire d’aborder les séries formelles et en particulier les fonctions génératrices pour gérer de manière compacte, la complexité informationnelle des réseaux considérés. Dans ce nouveau cadre, l’infini structurel est comme imbriqué dans sa propre complexité, afin de montrer la puissance de sa simplicité. Et c’est en ce sens que les petits mondes englobent les graphes aléatoires.