Graphes et petits mondes : cours de Seconde SNT

Quand tu ouvres une application de réseau social, tu vois une liste d'amis, d'abonnés ou d'abonnements. Derrière cette liste, il y a une structure : des personnes et des liens entre elles. Pour étudier cette structure, on ne garde que l'essentiel : qui est relié à qui. Les photos, les messages et les noms passent au second plan.

L'outil mathématique qui sert à ça s'appelle un graphe. Le programme de SNT invite à utiliser cette structure pour représenter un réseau de relations et à comprendre la notion de « petit monde » ¹. Dans ce cours, tu vas apprendre le vocabulaire des graphes, puis découvrir pourquoi des chercheurs ont été frappés par la brièveté des chaînes de relations qui nous séparent des autres.

Le cours suit cet ordre : le vocabulaire, l'hypothèse du petit monde, le modèle de 1998, ce qu'il explique, puis une méthode pour chercher un chemin dans un réseau.

Prenons cinq personnes : Ana, Bilal, Chloé, Dimitri et Emma. Ana est amie avec Bilal et Chloé. Bilal est ami avec Dimitri. Chloé est amie avec Dimitri. Dimitri est ami avec Emma. On dessine un point par personne et un trait par amitié. Tu obtiens un graphe à 5 sommets et 5 arêtes.

Combien d'étapes faut-il pour passer de toi à une personne choisie au hasard sur Terre, en ne passant que par des gens qui se connaissent ? Intuitivement, on imagine une très longue chaîne. Pourtant, des observations répétées suggèrent le contraire.

L'idée remonte à 1929. Cette année-là, l'écrivain hongrois Frigyes Karinthy a lancé l'idée qu'on appellera plus tard les six degrés de séparation : deux personnes prises au hasard seraient reliées par une chaîne d'environ six relations ³.

En 1967, le psychosociologue Stanley Milgram a mené l'expérience du petit monde ³. C'est elle qui a donné son nom au « paradoxe de Milgram » ³. Les travaux de Milgram sont aussi à l'origine, plutôt lointaine, de la notion de graphe petit-monde étudiée plus tard par les statisticiens ².

Pour un élève de Seconde, retiens la logique : on modélise une société par un graphe où les sommets sont les personnes et les arêtes les relations, puis on se demande si la distance typique entre deux sommets est petite.

Observer qu'une chaîne est courte ne suffit pas : les chercheurs voulaient comprendre pourquoi et reproduire ce comportement avec un modèle. En 1998, Duncan J. Watts et Steven H. Strogatz, de l'université Cornell, ont publié le premier modèle de réseau consacré au petit monde : le modèle de Watts–Strogatz ³. Les statisticiens parlent de graphes « petit-monde » pour ce type de réseau ².

Leur résultat dépasse les réseaux humains. Ils montrent que des réseaux du monde naturel et du monde artificiel, comme le réseau de neurones du petit ver Caenorhabditis elegans ou des réseaux électriques, ont les caractéristiques d'un petit monde ³.

Les chercheurs ont aussi un énoncé mathématique : quand on prend deux nœuds au hasard, l'écart moyen qui les sépare suit le logarithme de la taille du réseau, c'est-à-dire qu'il croît bien moins vite que le nombre de nœuds ³. Tu n'as pas à manipuler ce résultat en Seconde. Retiens simplement ceci : même si le réseau devient gigantesque, la distance typique ne s'allonge que très lentement.

Prends un réseau très régulier, un treillis : chaque sommet est relié seulement à ses voisins proches, comme des personnes alignées en cercle qui ne parlent qu'à leurs deux ou trois voisines. Dans un tel réseau, il y a beaucoup de cliques, mais les distances sont grandes : pour aller de l'autre côté du cercle, il faut traverser presque tout le monde. La distance moyenne est proportionnelle au nombre de sommets ³.

Le résultat qui a suscité tant d'enthousiasme est le suivant : il suffit de modifier quelques arêtes de ce treillis pour faire chuter fortement la distance moyenne, tout en conservant l'essentiel des cliques ³.

Ce modèle a aussi été étudié dans des réseaux dits « sans échelle », dans lesquels le nombre de connexions des nœuds peut différer de plusieurs ordres de grandeur ³. Cela veut dire que certains sommets sont très connectés et d'autres presque pas. Ces notions dépassent le programme de Seconde, mais elles montrent que le modèle de 1998 n'est pas la fin de l'histoire.

Le modèle de Watts et Strogatz appuie une observation du sociologue Mark Granovetter : ce sont les liens faibles qui maintiennent ensemble les réseaux sociaux ³. Un lien faible relie deux personnes qui se connaissent peu : un ancien camarade de collège, un contact rencontré en stage. Ces liens font office de raccourcis entre des groupes qui, sans eux, resteraient séparés.

Depuis 1998, d'autres modèles reproduisant l'effet du petit monde ont vu le jour ; celui de Jon Kleinberg figure parmi les plus souvent cités. Les spécialistes des réseaux complexes continuent d'étudier ce thème ³.

L'idée a aussi attiré des chercheurs de disciplines très variées. Duncan Watts racontait avoir reçu, après la publication du modèle, des lettres de mathématiciens, physiciens, biochimistes, sociologues, économistes et ingénieurs, ainsi que d'une entreprise qui employait le concept pour la mise en réseau sur Internet ³. Les statisticiens l'utilisent aussi pour étudier les réseaux de villes en géographie ².

Une activité classique en SNT consiste à chercher une chaîne d'au plus six poignées de main qui te relie à une personnalité connue ¹. Voici une démarche rigoureuse pour trouver ce type de chemin dans un graphe donné.