A ce jour, le Web compte environ 800 millions de documents. Une étude récente, conduite par le mathématicien Albert-Laszlo Barabasi de l’Université de Notre Dame aux Etats-Unis, montre que si l’on prend deux pages au hasard, il suffit en moyenne de 19 clics de souris pour passer de l’une à l’autre. Comment faut-il comprendre et relativiser ce chiffre?
Il s’agit d’un problème de théorie des graphes, situé assez exactement au carrefour des mathématiques et de l’informatique. Mathématiquement, le Web est un graphe, c’est-à-dire un ensemble de sommets (les pages) reliés par des liens. Un grand nombre de problèmes mathématiques se modélisent au moyen de graphes. La théorie des graphes consiste à établir des méthodes pour parcourir ces structures de manière optimale afin de résoudre ces problèmes.
Le mythe fondateur de la théorie des graphes est le problème des ponts de Königsberg, une ville de Prusse-Orientale, aujourd’hui russe au nom de Kaliningrad. La ville est traversée par la Pregel, et sept ponts sont construits pour relier deux îles et les deux rives. De passage, le grand savant suisse Leonhard Euler, en route pour la cour de Russie, se demanda s’il était possible de franchir chaque pont une seule fois et revenir à son point de départ. Mission impossible, démonstration donnée par Euler, la théorie des graphes était née.
Plus près de nous, le professeur Barabasi a voulu estimer ce qu’on appelle la largeur d’un graphe (le Web), à savoir la distance moyenne entre deux sommets pris au hasard. L’équipe du professeur a pris un échantillon d’environ 300’000 distances et l’on peut penser que son résultat est statistiquement fiable. Ce qui est clair, c’est que la moyenne de 19 clics obtenue est certainement supérieure à la véritable largeur du Web, car il est évident que le robot électronique utilisé par le professeur ne trouvera pas forcément le chemin le plus court entre deux pages. Le chiffre donne cependant une bonne estimation supérieure de cette largeur.
Dans les problèmes mathématiques classiques, on a plutôt l’habitude de considérer le «diamètre» d’un graphe, soit la distance maximale entre deux sommets. Dans le cas du Web, le diamètre exact est impossible à déterminer car il faudrait effectuer une analyse exhaustive de l’ensemble des pages. Il est cependant plausible de penser que le diamètre et la largeur du graphe sont du même ordre de grandeur, soit entre 10 et 50. Je peux donc affirmer ici que deux pages Web (si l’on exclut les exceptions comme les pages sans liens) sont au maximum à une cinquantaine de clics de souris l’une de l’autre.
Une telle assertion mathématique peut sembler étonnante. J’aimerais la justifier indirectement, en donnant des analogies.
Premier exemple:
A combien de poignées de main êtes-vous du Président des Etats-Unis, ou de n’importe quel autre être humain?
Chacun de nous a serré au moins une fois la main d’un député, d’un journaliste parlementaire ou d’un diplomate, ce qui nous met à deux poignées de main de la présidente de la Confédération. Elle même a récemment accueilli Bill Clinton à Genève. Nous sommes donc tous au grand maximum à trois poignées de main du Président américain.
Faites le même raisonnement de l’autre côté de l’Atlantique, et vous en concluerez que nous sommes à quelques poignées de main (environ 6, peut-être 7) de l’ensemble du peuple américain. Empiriquement, le diamètre du graphe est de l’ordre de 10, et sa largeur 6. Ainsi, un graphe qui semble a priori gigantesque (l’Humanité, 6 milliards de «sommets») peut se révéler très étroit: nous sommes au maximum à 10 poignées de main de n’importe quel autre Terrien (en excluant cette fois ceux qui vivent seuls sur une île déserte, ou ceux qui ne serrent pas les mains…).
Le problème du Web est parfaitement analogue et le chiffre de 19 reflète assez bien les similitudes, comme les différences, des situations. Il est en outre assez clair que même une augmentation explosive de la taille du graphe ne va pas modifier sensiblement ces valeurs. Il y a 50 ans, le graphe des poignées de main avait certainement les mêmes caractéristiques, et la population a augmenté considérablement depuis. Plus philosophiquement, ce que le chiffre de 19 signifie est rassurant: il y a bien moins de liens dans le cybermonde qu’entre les êtres humains.
Deuxième exemple:
Vous souvenez-vous du cube de Rubik, dit aussi «cube hongrois»? Il date d’une vingtaine d’années et il a déclenché le plus incroyable engouement pour un jeu mathématique. Du jamais vu! Comme de nombreux mathématiciens, je me suis passionné pour cet exercice difficile. Je peine aujourd’hui à remettre un Rubik en position de départ, et je n’ai jamais réussi, ni maintenant, ni à l’époque glorieuse, à descendre au-dessous de la minute (je connais par contre plusieurs de ces «one-minute men», comme on les appelait à l’époque).
Occasionnellement, je ressors mon Rubik. J’ai encore le mode d’emploi sous la main, et j’y recours lorsque j’ai oublié mes protocoles. Il faut en général 180 mouvements (en une minute, cela demande une dextérité certaine) pour remettre le cube en place. Les experts ont quelques raccourcis, mais l’ordre de grandeur est le même: on doit procéder systématiquement, et il n’est pas question de traiter le problème de façon différenciée selon la position de départ donnée.
Rappelons qu’il y a environ 4*10^19 (soit un nombre de 20 chiffres) positions différentes. Le Rubik peut donc s’étudier comme un graphe contenant ce nombre de sommets, soit plus que l’âge de l’Univers exprimé en nanosecondes. Pour le remettre dans sa position initiale, il s’agit de parcourir ce graphe (chaque lien étant un mouvement possible du cube) d’une manière particulièrement intelligente, puisqu’il est exclu de tester tous les parcours possibles.
Clairement, le diamètre du graphe qui modélise le cube de Rubik est bien plus petit que les 180 coups qu’utilisent les meilleurs joueurs pour le résoudre. Mathématiquement, on a même pu montrer qu’il était plus petit que 70, et la présomption est qu’il est même sensiblement inférieur. Il suffit en effet d’une douzaine de coups seulement pour déranger un cube hongrois et le rendre tout à fait méconnaissable. En d’autres termes, la largeur du graphe doit être de l’ordre d’une vingtaine, et le diamètre peut-être 40. Idéalement, n’importe quel cube se résout donc en une quarantaine de coups seulement.
Mathématiquement, la détermination exacte de la largeur ou du diamètre d’un graphe est extrêmement difficile et les approches sont multiples. Les internautes peuvent facilement toucher le problème du doigt: soit un parcours de 19 liens entre deux pages choisies au hasard, comment faire pour trouver un chemin avec un clic de moins? Comme pour le cube de Rubik, il y a de fortes chances que ce chemin existe, mais il est très difficile à trouver.
——-
François Sigrist est professeur de mathématiques à l’Université de Neuchâtel (Suisse).