{"id":241,"date":"1999-11-04T00:00:00","date_gmt":"1999-11-03T23:00:00","guid":{"rendered":"http:\/\/www.largeur.com\/?p=241"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T22:00:00","slug":"maths","status":"publish","type":"post","link":"https:\/\/largeur.com\/?p=241","title":{"rendered":"On conna\u00eet la largeur du Web: dix-neuf clics"},"content":{"rendered":"

A ce jour, le Web compte environ 800 millions de documents. Une \u00e9tude r\u00e9cente<\/a>, conduite par le math\u00e9maticien Albert-Laszlo Barabasi de l’Universit\u00e9 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 \u00e0 l’autre. Comment faut-il comprendre et relativiser ce chiffre?<\/p>\n

Il s’agit d’un probl\u00e8me de th\u00e9orie des graphes, situ\u00e9 assez exactement au carrefour des math\u00e9matiques et de l’informatique. Math\u00e9matiquement, le Web est un graphe, c’est-\u00e0-dire un ensemble de sommets (les pages) reli\u00e9s par des liens. Un grand nombre de probl\u00e8mes math\u00e9matiques se mod\u00e9lisent au moyen de graphes. La th\u00e9orie des graphes consiste \u00e0 \u00e9tablir des m\u00e9thodes pour parcourir ces structures de mani\u00e8re optimale afin de r\u00e9soudre ces probl\u00e8mes. <\/p>\n

Le mythe fondateur de la th\u00e9orie des graphes est le probl\u00e8me des ponts de K\u00f6nigsberg, une ville de Prusse-Orientale, aujourd’hui russe au nom de Kaliningrad. La ville est travers\u00e9e par la Pregel, et sept ponts sont construits pour relier deux \u00eeles et les deux rives. De passage, le grand savant suisse Leonhard Euler, en route pour la cour de Russie, se demanda s’il \u00e9tait possible de franchir chaque pont une seule fois et revenir \u00e0 son point de d\u00e9part. Mission impossible, d\u00e9monstration donn\u00e9e par Euler, la th\u00e9orie des graphes \u00e9tait n\u00e9e.<\/p>\n

Plus pr\u00e8s de nous, le professeur Barabasi<\/a> a voulu estimer ce qu’on appelle la largeur d’un graphe (le Web), \u00e0 savoir la distance moyenne entre deux sommets pris au hasard. L’\u00e9quipe du professeur a pris un \u00e9chantillon d’environ 300’000 distances et l’on peut penser que son r\u00e9sultat est statistiquement fiable. Ce qui est clair, c’est que la moyenne de 19 clics obtenue est certainement sup\u00e9rieure \u00e0 la v\u00e9ritable largeur du Web, car il est \u00e9vident que le robot \u00e9lectronique utilis\u00e9 par le professeur ne trouvera pas forc\u00e9ment le chemin le plus court entre deux pages. Le chiffre donne cependant une bonne estimation sup\u00e9rieure de cette largeur. <\/p>\n

Dans les probl\u00e8mes math\u00e9matiques classiques, on a plut\u00f4t l’habitude de consid\u00e9rer le \u00abdiam\u00e8tre\u00bb d’un graphe, soit la distance maximale entre deux sommets. Dans le cas du Web, le diam\u00e8tre exact est impossible \u00e0 d\u00e9terminer car il faudrait effectuer une analyse exhaustive de l’ensemble des pages. Il est cependant plausible de penser que le diam\u00e8tre et la largeur du graphe sont du m\u00eame 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 \u00e0 une cinquantaine de clics de souris l’une de l’autre. <\/p>\n

Une telle assertion math\u00e9matique peut sembler \u00e9tonnante. J’aimerais la justifier indirectement, en donnant des analogies. <\/p>\n

Premier exemple:<\/b>
\nA combien de poign\u00e9es de main \u00eates-vous du Pr\u00e9sident des Etats-Unis, ou de n’importe quel autre \u00eatre humain?<\/p>\n

Chacun de nous a serr\u00e9 au moins une fois la main d’un d\u00e9put\u00e9, d’un journaliste parlementaire ou d’un diplomate, ce qui nous met \u00e0 deux poign\u00e9es de main de la pr\u00e9sidente de la Conf\u00e9d\u00e9ration. Elle m\u00eame a r\u00e9cemment accueilli Bill Clinton \u00e0 Gen\u00e8ve. Nous sommes donc tous au grand maximum \u00e0 trois poign\u00e9es de main du Pr\u00e9sident am\u00e9ricain.<\/p>\n

Faites le m\u00eame raisonnement de l’autre c\u00f4t\u00e9 de l’Atlantique, et vous en concluerez que nous sommes \u00e0 quelques poign\u00e9es de main (environ 6, peut-\u00eatre 7) de l’ensemble du peuple am\u00e9ricain. Empiriquement, le diam\u00e8tre du graphe est de l’ordre de 10, et sa largeur 6. Ainsi, un graphe qui semble a priori gigantesque (l’Humanit\u00e9, 6 milliards de \u00absommets\u00bb) peut se r\u00e9v\u00e9ler tr\u00e8s \u00e9troit: nous sommes au maximum \u00e0 10 poign\u00e9es de main de n’importe quel autre Terrien (en excluant cette fois ceux qui vivent seuls sur une \u00eele d\u00e9serte, ou ceux qui ne serrent pas les mains…). <\/p>\n

Le probl\u00e8me du Web est parfaitement analogue et le chiffre de 19 refl\u00e8te assez bien les similitudes, comme les diff\u00e9rences, des situations. Il est en outre assez clair que m\u00eame une augmentation explosive de la taille du graphe ne va pas modifier sensiblement ces valeurs. Il y a 50 ans, le graphe des poign\u00e9es de main avait certainement les m\u00eames caract\u00e9ristiques, et la population a augment\u00e9 consid\u00e9rablement 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 \u00eatres humains.<\/p>\n

Deuxi\u00e8me exemple:<\/b>
\nVous souvenez-vous du cube de Rubik, dit aussi \u00abcube hongrois\u00bb? Il date d’une vingtaine d’ann\u00e9es et il a d\u00e9clench\u00e9 le plus incroyable engouement pour un jeu math\u00e9matique. Du jamais vu! Comme de nombreux math\u00e9maticiens, je me suis passionn\u00e9 pour cet exercice difficile. Je peine aujourd’hui \u00e0 remettre un Rubik en position de d\u00e9part, et je n’ai jamais r\u00e9ussi, ni maintenant, ni \u00e0 l’\u00e9poque glorieuse, \u00e0 descendre au-dessous de la minute (je connais par contre plusieurs de ces \u00abone-minute men\u00bb, comme on les appelait \u00e0 l’\u00e9poque). <\/p>\n

Occasionnellement, je ressors mon Rubik. J’ai encore le mode d’emploi sous la main, et j’y recours lorsque j’ai oubli\u00e9 mes protocoles. Il faut en g\u00e9n\u00e9ral 180 mouvements (en une minute, cela demande une dext\u00e9rit\u00e9 certaine) pour remettre le cube en place. Les experts ont quelques raccourcis, mais l’ordre de grandeur est le m\u00eame: on doit proc\u00e9der syst\u00e9matiquement, et il n’est pas question de traiter le probl\u00e8me de fa\u00e7on diff\u00e9renci\u00e9e selon la position de d\u00e9part donn\u00e9e. <\/p>\n

Rappelons qu’il y a environ 4*10^19 (soit un nombre de 20 chiffres) positions diff\u00e9rentes. Le Rubik peut donc s’\u00e9tudier comme un graphe contenant ce nombre de sommets, soit plus que l’\u00e2ge de l’Univers exprim\u00e9 en nanosecondes. Pour le remettre dans sa position initiale, il s’agit de parcourir ce graphe (chaque lien \u00e9tant un mouvement possible du cube) d’une mani\u00e8re particuli\u00e8rement intelligente, puisqu’il est exclu de tester tous les parcours possibles. <\/p>\n

Clairement, le diam\u00e8tre du graphe qui mod\u00e9lise le cube de Rubik est bien plus petit que les 180 coups qu’utilisent les meilleurs joueurs pour le r\u00e9soudre. Math\u00e9matiquement, on a m\u00eame pu montrer qu’il \u00e9tait plus petit que 70, et la pr\u00e9somption est qu’il est m\u00eame sensiblement inf\u00e9rieur. Il suffit en effet d’une douzaine de coups seulement pour d\u00e9ranger un cube hongrois et le rendre tout \u00e0 fait m\u00e9connaissable. En d’autres termes, la largeur du graphe doit \u00eatre de l’ordre d’une vingtaine, et le diam\u00e8tre peut-\u00eatre 40. Id\u00e9alement, n’importe quel cube se r\u00e9sout donc en une quarantaine de coups seulement. <\/p>\n

Math\u00e9matiquement, la d\u00e9termination exacte de la largeur ou du diam\u00e8tre d’un graphe est extr\u00eamement difficile et les approches sont multiples. Les internautes peuvent facilement toucher le probl\u00e8me 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\u00e8s difficile \u00e0 trouver. <\/p>\n

——-
\nFran\u00e7ois Sigrist est professeur de math\u00e9matiques \u00e0 l’Universit\u00e9 de Neuch\u00e2tel (Suisse).<\/p>\n","protected":false},"excerpt":{"rendered":"

Selon une \u00e9tude am\u00e9ricaine, il suffit en moyenne de 19 clics de souris pour passer d’une page Web \u00e0 une autre, prise au hasard. Cours acc\u00e9l\u00e9r\u00e9 de th\u00e9orie des graphes, par le math\u00e9maticien Fran\u00e7ois Sigrist.<\/p>\n","protected":false},"author":982,"featured_media":0,"comment_status":"open","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-241","post","type-post","status-publish","format-standard","hentry","category-technophile","technophile"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t