Le dernier numéro d'
Accromath, passionnante revue mathématique québecoise en ligne, traite des mathématiques qui se cachent derrière le célébrissime moteur de recherche.
Comment classer les pages web au cours d'une requête?
La toile peut se voir comme un graphe dont les sommets sont les pages web, les arêtes, les liens qui les relient. Yvan Saint-Aubin, de l'Université de Montréal, use d'une métaphore parlante: celle du promeneur impartial. Il s'agit d'étiqueter le graphe en pondérant les arêtes par les probabilités que le promeneur aille d'une page vers une autre.
Pour illustrer son propos, il choisit un modèle simple de cinq pages: il s’amuse à imaginer que A est le site officiel des Jeux Olympiques, B celui des Jeux d’hiver 2014 de Sotchi, C celui de l’agence antidopage, D l’office de tourisme russe et E un grand périodique.
 |
| Graphe des 5 pages web |
Quelques calculs de probabilités plus loin (l'impartialité du promeneur dicte une équiprobabilité), on peut établir une matrice de changement d'état. Le but est alors de déterminer l'état stationnaire qui livrera l'ordre des probabilités recherché (c'est-à-dire les chances, dans l'ordre, que le promeneur se trouve à terme en A, B, C, D ou E). L’idée cruciale des concepteurs de l'algorithme de Google est que le comportement asymptotique du promeneur indique une préférence des internautes. Cet ordre servira d'ordre de référencement de ces 5 pages.
Le modèle à 5 pages revient à résoudre un système de 5 équations à 5 inconnues.
Imaginez les systèmes en jeu avec quelques 10 000 000 000 000 sites indexés par Google!
L'entreprise utilise plusieurs parcs d'ordinateurs pour affronter ces systèmes.
Des questions mathématiques difficiles restent en suspens. Comment est-on sûr de tomber sur un état stationnaire? Dépend-il des conditions initiales?
Source: le très bel article d'Yvan Saint-Aubin (ici en
pdf)
