🔍
Seconde
Maths SNT
Première
spécialité S STI2D STMG ES ES Spécialité
Terminale
spécialité Maths Expertes STI2D STMG S
BTS
Groupe A (SE) Groupe B ( MS / MI )
Colles
Numérique
Simulation et calcul num. Communication num. Calculettes
Informatique
Algorithmique python Matlab Scilab Latex Javascript     ...
Math@ppliquées
Application économique: coût marginalFractales - IFS & jeu du chaosConversion analogique - NumériquePoint fixe - RelaxationPropagation d'ondesMartingale à un jeu de hasard     ...
Divers
Plan du site Paradoxes et logique Générateur de devoirs Editeur de texte Contact A propos Biblio/Filmo Liens English pages
☰      
next_inactive up previous
suivant: Réseaux de communication (à venir ...)

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



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 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 1.


Pour arriver à donner une information à la fois rapide et pertinente, Google construit dynamiquement le graphe de toutes les pages internet 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.


Ainsi, pour connaître la note d'une page, il faut connaître la valeur de ses pages voisines dans le graphes, pour lesquelles il faut connaître les valeurs des autres voisines pour lesquelles ....


Le processus de tri, classement et notation se fait en deux grandes étapes:

  • 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;


La liste des pages trouvées est ensuite simplement retournée classé par ordre de pagerank.


Le travail principal qu'il reste à effectuer est donc le calcul de ces fameux pagerank. Ce point est le fondement essentiel du moteur de recherche Google.


Détermination du pagerank - Calcul de probabilités

On suppose que l'ensemble des pages contenant les mots clés recherchés ont été préselectionnées. On construit alors le graphe associé à toutes ces pages, en reliant entre elles les pages qui contiennent un lien de l'une vers l'autre.
La relation "contenir un lien vers" n'est pas une relation symétrique: si la page $ A$ contient un lien vers la page $ B$ , cela ne signifie pas nécessairement que la page $ B$ contient elle aussi un lien vers la page $ A$ . Ce graphe ainsi construit est donc un graphe orienté, les arêtes de celui-ci sont représentées par une flèche pour indiquer "qui pointe vers qui".


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.

Figure: Graphe orienté constitué de 4 pages
\begin{figure}\begin{center} \psset{unit=1cm} \begin{pspicture}(0.,-1.)(7,7) \p... ...[linewidth=1.5pt]{->}(5.5,0.6)(1.6,5.4) \end{pspicture} \end{center}\end{figure}

Ce graphe se lit de la manière suivante:

  • les pages $ A$ , $ B$ , $ C$ et $ 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;
  • ...


La notation de chacune de ces pages peut se rechercher en terme de probabilités: en se promenant au hasard sur cet ensemble de page, quelles seraient les chances de se retrouver sur la page $ A$ , sur la page $ B$ , ....

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é $ \frac{e}{4}=\frac{0,15}{4}$ 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é $ \displaystyle \frac{1}{2}p_D$ (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$ :

$\displaystyle \left\{\begin{array}{lcl} p_A&=&\displaystyle \frac{0,15}{4}+(1-... ...ght] \vspace{0.3cm}\\ p_D&=&\displaystyle \frac{0,15}{4} \end{array}\right. $ (1)

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 à:

$\displaystyle \left\{\begin{array}{rcrcrcrcl} p_A &-& 0,85 p_B &-& 0,85 p_C &-... ...425 p_D &=& 0,0375 \vspace{0.3cm}\\ &&&&&& p_D &=& 0,0375 \end{array}\right. $

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 p_D=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$ :

$\displaystyle \left\{\begin{array}{rcccl} p_A &-& 0,85 p_B &=& 0,85 p_c + 0,425... ...75 = 0,0989 \vspace{0.3cm}\\ 0,85 p_A &-& p_B &=& -0,0375 \end{array}\right. $

On trouve finalement :

$\displaystyle \left\{\begin{array}{ccc} p_A &=& 0,4711 \vspace{0.3cm}\\ p_B &=... ...& 0,0534 \vspace{0.3cm}\\ p_D &=& 0,0375 \vspace{0.3cm}\\ \end{array}\right. $

Ainsi, dans cet exemple, les 4 pages seraient classées dans l'ordre: $ A$ , $ B$ , $ C$ et $ D$.



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 2.


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.


Le pagerank, ou degré de pertinence, de chaque page va être évalué par étapes successives.


On notera $ A_n$ , $ B_n$ , $ C_n$ et $ D_n$ les valeurs correspondantes à la $ n^{\mbox{\scriptsize {iè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

$\displaystyle A_0=B_0=C_0=D_0=\frac{1}{4}$


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^{\mbox{\scriptsize {ième}}}$ étape, celles-ci deviennent à la $ (n+1)^{\mbox{\scriptsize {ième}}}$ étape $ A_{n+1}$ , $ B_{n+1}$ , $ C_{n+1}$ , $ D_{n+1}$ , avec

$\displaystyle \left\{\begin{array}{lcl} A_{n+1}&=&\displaystyle \frac{0,15}{4}+... ...D_n\vspace{0.3cm}\\ D_{n+1}&=&\displaystyle \frac{0,15}{4} \end{array}\right. $

Ces relations permettent alors de calculer de proche en proche $ A_1$ , $ B_1$ , $ C_1$ et $ D_1$ , puis ensuite $ A_2$ , $ B_2$ , $ C_2$ et $ D_2$ , puis ...:

$\displaystyle \left\{\begin{array}{lcll} A_1&=&\displaystyle \frac{0,15}{4}+(1-... ...pace{0.3cm}\\ D_1&=&\displaystyle \frac{0,15}{4} &=0,0375 \end{array}\right. $

puis,

$\displaystyle \left\{\begin{array}{lcll} A_2&=&\displaystyle \frac{0,15}{4}+(1-... ...pace{0.3cm}\\ D_2&=&\displaystyle \frac{0,15}{4} &=0,0375 \end{array}\right. $

et ainsi de suite pendant le nombre $ n$ d'étapes souhaité.


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.

  • 1 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...
  • 2 à 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).




suivant: Réseaux de communication (à venir ...)