Une interrogation a été émise il y a un siècle avec l’avènement des échanges internationaux qui ont succédé à la Première Guerre mondiale. Elle intéresse toujours les mathématiciens et elle suscite encore des recherches : deux êtres humains quelconques, pris au hasard, sont-ils toujours reliés par une chaîne de connaissances comportant un « petit » nombre d’intermédiaires ?
L’étude des liens reliant les individus d’une population donnée remonte à la fin des années 1920. L’écrivain hongrois Frigyes Karinthy est le premier à avoir émis l’idée, dans une nouvelle, que tout être humain puisse être relié à n’importe quel autre habitant de la planète par une chaîne de connaissances comprenant au plus six maillons.
Frigyes Karinthy (1887–1938).
Une expérimentation historique
L’idée de Frigyes Karinthy fut reprise dans les années 1960 par le psychosociologue américain Stanley Milgram. Celui-ci mena une première expérience avec soixante volontaires du Nebraska, à qui il donna soixante lettres destinées à des habitants du Massachusetts. Les expéditeurs ne connaissaient pas les destinataires et devaient transmettre la lettre à une de leurs connaissances, les lettres voyageant ainsi « d’ami en ami » jusqu’à ce que quelqu’un connaisse le destinataire et la lui remette. Très peu de lettres arrivèrent à leur destinataire, car certains maillons n’ont pas joué le jeu et ont coupé la chaîne de transmission, mais les lettres qui furent remises n’étaient passées que par un très petit nombre d’intermédiaires.
Stanley Milgram (1933–1984).
Cette expérience fut critiquée car le nombre de participants était faible ; en outre, elle ne mettait en jeu que des personnes d’un même pays et d’un même milieu social. Elle fut cependant reprise et l’avènement des réseaux sociaux sur Internet renouvela son intérêt. En 2011, une étude du réseau Facebook (Facebook Inc., 2004) montra ainsi que chaque abonné est relié à n’importe quel autre par une chaîne comportant en moyenne 4,74 relations. Là encore, on peut émettre des réserves : une grande partie de l’humanité n’est pas connectée à ce réseau ; certains adhérents complètent leur liste d’amis avec des centaines de personnes qu’ils ne connaissent pas réellement, voire en achètent par milliers pour augmenter artificiellement leur notoriété (des listes d’« amis » se vendent sur Internet !)…
Prenons au hasard vingt personnes membres du réseau social mondial imaginaire Pilebook (Criton et fils, 2020) qui, deux à deux, ne se connaissent pas. Supposons que l’on puisse, toujours aléatoirement, connecter entre elles certaines de ces personnes par des liens, chaque lien étant établi entre deux personnes du groupe. Par convention, on dirait alors que deux personnes directement reliées sont « amies sur Pilebook ». Si l’on a créé (19 × 20) / 2, soit 190 liens différents, chacune des vingt personnes est directement reliée aux dix-neuf autres : le graphe représentant cette situation est alors un graphe complet.
Si le graphe n’est pas complet, c’est-à-dire si tous les liens possibles ne sont pas présents, il pourrait y avoir des points isolés, c’est-à-dire un ou des membres du groupe qui ne sont connectés à personne. Le graphe représentant cette situation est alors non connexe. On pourrait également avoir deux ou plusieurs sous-graphes, chacun étant connexe, mais sans aucun lien entre eux.
Si le graphe est connexe, mais non complet, certaines personnes ne seront pas directement « amies sur Pilebook », mais pourront être connectées indirectement grâce à une chaîne d’une ou de plusieurs personnes intermédiaires.
À partir de la situation où chacune des vingt personnes est reliée aux dix-neuf autres, on supprime des liens de façon aléatoire. Après ces suppressions, deux personnes, Adriano et Theresa, ne sont plus reliées indirectement que par une chaîne d’intermédiaires qui comprend les dix-huit autres personnes du groupe.
1. Combien de liens a-t-on supprimés, au minimum ?
2. Même question si la chaîne d’intermédiaires la plus courte entre Adriano et Theresa comprend dix-sept personnes, puis seize, quinze…