Principe du référencement du moteur de recherche Google

Introduction - Avertissement

• Google BERT: un moteur à base d'IA (Intelligence Articifielle) capable d'analyser les combinaisons de mots
• Page Experience: le confort des internautes, aussi appelé UX (pour User eXperience), est alors un élement clé
• Fraîcheur de l'information: pour privilégier les informations les plus récentes, voire les actualités selon le domaine
• Correspondance neuronale: rendant le moteur capable de comprendre et faire des concepts dans les requêtes

Principe général

Un exemple de réseau est celui formé par l'ensemble des pages accessibles sur internet. Les noeuds de ce réseau sont les diverses pages, celles-ci pouvant avoir des liens entre elles (des "hyperliens" ou "hyperréférences", c'est-à-dire des liens dynamiques sur lesquels il suffit de cliquer pour aboutir à la page pointée).
Les noeuds de ce réseau (les pages internet) se comptent actuellement en centaine de milliards, le nombre de connexions entre ces noeuds étant lui aussi d'autant plus gigantesque.
Les moteurs de recherche, Google par exemple, ont pour objectif de classer ces milliards de pages, et d'être par la suite en mesure de trouver dans ce gigantesque réseau les pages pertinentes vis-à-vis d'une requête avancée par un utilisateur.
Aucun moteur de recherche ne peut stocker et traiter autant de pages ¹.

Pour arriver à donner une information à la fois rapide et pertinente, Google construit dynamiquement le graphe de toutes les pages auxquelles il peut accéder. Des programmes informatiques créés et lancés par Google se promènent continûment le long de ce graphe en le complétant ou le modifiant chaque fois que nécessaire (ajout de nouvelles pages ou nouveaux liens, suppression de pages ou liens n'existant plus).
Par ailleurs, afin de pouvoir retourner à l'utilisateur une information pertinente, ces pages sont "notées" permettant ainsi de les classer par degré de pertinence, mais aussi de retourner à l'utilisateur une liste de pages ordonnée.
Le moteur de recherche Google attribue à cette fin à chaque page une valeur de notoriété appelée "pagerank": plus cette valeur est importante, plus la page est jugée pertinente et sera bien située dans l'ordre des résultats retournés; inversement plus cette valeur est faible (proche de zéro) moins la page est considérée comme pertinente.

La valeur du pagerank d'une page est déterminée par le nombre de lien pointant vers cette page que l'on peut trouver sur d'autres pages, et de la valeur du pagerank de chacune de ces pages. En d'autres termes, une page est jugée d'autant plus pertinente qu'elle est citée un grand nombre de fois par des pages elles mêmes jugées int&éressantes.

• le moteur de recherche préselectionne tout d'abord dans un premier temps l'ensemble des pages répondant au(x) mot(s) clé(s) fourni(s);
• ensuite, le graphe constitué par ces pages est construit permettant de calculer pour chacune d'entre elle le pagerank, ou degré de notoriété ou de pertinence de la page;

Détermination du pagerank - Calcul de probabilités

Le graphe ci-dessous est un exemple d'un tel graphe orienté dans le cas où l'on ne considère pour commencer que 4 pages.

• les pages A, B, C ou D ont été préselectionnées comme contenant toutes les mots clés recherchés
• la page A contient un lien vers la page B
• la page D contient un lien vers les pages A et C, tandis qu'aucune page ne "pointe" vers elle;
• …

En effet, on peut imaginer que la page la plus pertinente est celle vers laquelle "s'orientent" les autres, et donc que, en se promenant au hasard entre ces pages, ce soit finalement celle sur laquelle on passe le plus de temps.

On suppose de plus pour compléter ce modèle, et pour simuler d'autant mieux une personne qui naviguerait aléatoirement entre ces pages, qu'il existe une probabilité e pour que, à tout moment, cette personne saute sur une page quelconque, au hasard et indépendamment des liens qui se trouvaient face à elle. On prendra par la suite comme valeur e = 0,15 (valeur proche de celle utilisée par Google).

On note p_A, p_B, p_C et p_D les probabilités de se trouver respectivement sur la page A, B, C ou D.

Par exemple, on peut se trouver sur la page A complétement au hasard (probabilité car il y a 4 pages au total), ou bien dans le cas contraire (probabilité 1−0,15=0,85) en provenant de la page B avec la probabilité p_B, ou de la page C avec la probabilité p_C, ou encore de la page D avec la probabilité (car en provenant de la page D, on peut aller aussi bien en A que en C ).

Ce raisonnement permet d'exprimer la probabilité p_A, puis, de manière analogue, les probablités p_B, p_C et p_D:

Ce système est un système d'équations linéaire à 4 équations et 4 inconnues, p_A, p_B, p_C et p_D, qu'il ne reste plus alors qu'à résoudre.

En ordonnant les termes, ce système est équivalent à:

La dernière équation donne directement p_D = 0,0375, puis l'avant dernière, connaissant p_D donne la valeur de p_C = 0,0375 + 0,425 = 0,0534.

Ensuite, connaissant les valeurs de p_C et p_D, il ne reste plus que les deux premières équations à résoudre qui forment un système linéaire de deux équations à deux inconnues p_A et p_B:

On trouve finalement les valeurs des probabilités:

L'inconvénient majeur de cette méthode est que, en réalité, le nombre de pages qui peuvent répondre à certains mots clés peut facilement s'élever à quelques centaines de milliers, voire quelques millions (essayez de demander par exemple à Google de rechercher les mots clés "référencement Google", ou encore "cours mathématiques", ou bien sûr les mots clés de votre choix, et observez le nombre de pages qui ont été référencées par Google (ce nombre est donné par Google juste en dessous des mots clés fournis)).
Malheureusement, même avec les ordinateurs les plus puissants actuellement, la résolution de grands systèmes linéaires peut prendre énormément de temps ².

Cette méthode n'est ainsi pas applicable, d'autant plus que l'on souhaite que ces calculs soit effectués très rapidement (accepteriez-vous d'attendre ne serait-ce que quelques heures pour avoir une réponse à votre recherche ?) et très régulièrement afin que les résultats restent à jour malgré l'évolution fréquente et rapide des très nombreuses pages, de leur contenu, et des liens qui les relient (à chaque instant, des pages sont modifiées, créees, supprimées, ...).

Approximation des probabilités par des suites

Une alternative à ce calcul des probabilités exactes a été proposé par les fondateurs de Google.

On notera A_n, B_n, C_n et D_n les valeurs correspondantes à la n^ème étape.
On considère tout d'abord que, initialement, la pertinence de chaque page (ayant été préselectionnée comme contenant effectivement les mots clés recherchés) est équirépartie: dans notre exemple qui compte 4 pages, ces degrés de pertinence, valent ainsi pour chaque page

Les mêmes raisonnements et calculs qu'eefectués précédemment en termes de probabilité s'appliquent: si les valeurs A_n, B_n, C_n et D_n sont connues à la n^ème étape, celles-ci deviennent à la (n+1)^ème étape A_n+1, B_n+1, C_n+1, D_n+1, avec

puis,

Les quatres suites A_n, B_n, C_n et D_n convergent respectivement vers p_A, p_B, p_C et p_D qui sont les solutions du système ^[*].

A ce titre, les valeurs calculées pour A_n, B_n, C_n et D_n après quelques étapes constituent une approximation des valeurs limites p_A, p_B, p_C et p_D, approximation d'autant meilleure que n est choisi grand, c'est-à-dire qu'il y a eu un grand nombre d'étapes.

• ¹ Google annonçait en 2005 qu'il pouvait en indexer quelques huit milliards, mais, même si les performances technologiques en matière de stockage et rapidité de calcul s'accroissent, le nombre de pages à stocker et référencer se démultiplie lui aussi à grande vitesse...
• ² à titre d'information, la résolution en 2006 d'un système linéaire à quelques centaines de millions d'équations et d'inconnues demandait plusieurs jours de calcul sur un supercalculateur (ordinateur possédant un très grand nombre de processeurs calculant en parallèle, c'est-à-dire se partageant le travail et calculant simultanément).