II - 3 - Google et le PageRank
Google est une société fondée en 1998 par Larry Page et Sergei Brin en Californie. Mais Google est avant tout un moteur de recherche créé en 1996 par les deux cofondateurs de la société alors qu’ils étaient encore étudiants à l’université de Stanford. Le projet Google traite d’un moteur de recherche dont le fondement est basé sur le principe d’une analyse des relations entre les sites Web.
a. Le fonctionnement du moteur de recherche Google
Le moteur de recherche tel qu’il est apparu en 1998 a
Depuis le printemps 2003 le moteur de recherche fonctionne comme suit :
Tout d’abord l’indexation, elle est réalisée par le Google bot[1], c’est un spider bot[2] qui est chargé de ré indexer les pages contenues dans l’index actuel mais aussi d’indexer les nouvelles pages. La période d’indexation s’adapte aux besoins de rafraîchissement des différentes pages, que ce soit des pages personnelles (mises à jour à une fréquence aléatoire) ou des pages d’actualité (avec des fréquences de mises à jour plus importantes). C’est une nouveauté de Google car dans sa première version le moteur de recherche effectuait ses trois fonctions via l’utilisation de plusieurs robots. Le Google bot est capable de suivre tout type de lien et il est donc capable d’indexer la totalité du Web.
En plus du Google bot, il existe deux autres robots d’indexation qui ont des fonctions bien particulières, elles sont liées aux nouveautés que proposent Google :
. Un robot qui se charge d’indexer les pages affichées ensuite dans Google News,
. Un robot qui se charge d’indexer les pages commerciales qui seront affichées dans le bandeau de droite d’une réponse à une requête quelconque, c’est le robot de Google AdSense.
La seconde étape durant laquelle le calcul des notes des pages en fonction du contenu et des liens.
Pendant que de nombreux chercheurs ont passé beaucoup de temps à imaginer des algorithmes capables d’indexer tout le Web ou de l’indexer le plus rapidement possible Larry Page et Sergei Brin se sont penchés sur le classement des résultats d’une recherche. Ils ont imaginé une méthode pour déterminer l’importance d’une page Web. Contrairement à d’autres algorithmes le pageRank ne se base pas sur le contenu total d’une page Web mais plutôt sur ses liens sortants mais aussi entrants.
En français PageRank signifie rang de la page, on retrouve dans cette dénomination la volonté de classer les pages par importance et de leur donner un rang pour les distinguer les unes des autres lors d’une requête sur le moteur de recherche.
Définition de l’algorithme du pageRank telle qu’énoncée dans la publication de Google :
Le PageRank peut être calculé en utilisant un simple algorithme itératif, et correspond au vecteur propre principal de la matrice normalisée des liens du Web.
1) Le concept de base de l’algorithme :
Un lien d’une page A vers une page B est traduit par le fait que le webmestre de la page A estime que la page B est de bonne qualité et, de plus, il y a de fortes chances pour que le domaine des informations contenues dans la page B ait un lien avec le domaine des informations de la page A. En possédant un lien vers la page B, A affecte donc un vote à B.
On comprend donc aisément que plus la page B reçoit de votes (possède des liens entrants) d’autres pages du Web plus elle est considérée comme importante par Google et plus elle aura de chances de se retrouver bien placée en réponse à une requête dans le domaine dont elle traite.
Remarques :
- L’importance de la page B émettrice du lien vers la page B n’est pas négligeable pour déterminer l’importance de la page B. En effet une page possédant une multitude de liens entrants de la part de sites persos n’obtiendra le même classement qu’une page qui possède quelques liens entrants de la part de sites reconnus et mondialement connus.
- Comme pour l’indexation incrémentale, et comme son nom l’indique l’algorithme pageRank n’attribue pas un classement pour un site complet mais pour chaque page qui le constitue. Aucune extrapolation (moyenne des pages d’un site ou autre) n’a été réalisée afin de noter le site plutôt que ses pages.
- L’algorithme pageRank ne scrute pas le contenu d’une page afin d’y déceler les méta données ou autres informations qui pourraient aider le moteur d’indexation à donner une note pertinente en rapport avec tel ou tel sujet. L’algorithme pageRank est basé sur le principe des liens et donc le fait qu’une page est un fort pageRank ne signifie pas que son contenu est très intéressant ni que les informations sont vraies, une page a un fort pageRank si de nombreuses pages pointent vers elle.
2) La barre d’outils de Google[3]
Afin de mieux sensibiliser les utilisateurs du moteur de recherche, Google propose une barre d’outils qui s’insère sous menus du navigateur Web. Cette barre d’outil Google donne la possibilité d’effectuer une recherche à l’aide d’une barre de saisie de texte, la réponse à la requête est transcrite dans la fenêtre de recherche de Google habituelle. La nouvelle fonctionnalité qui la différencie par rapport aux autres barres d’outils des moteurs de recherche est l’affichage du pageRank de la page en cours.
Figure II.3.a :La barre d’outil de Google ( la Google Toolbar
On voit ci-dessus, qu’en plus des outils habituels la barre d’outil de Google affiche sous la forme d’une progression verte sur fond blanc. Ici le pageRank est de 9/10, la page est www.cnn.com alors que la requête était « cnn ».
De nombreux articles traitent de l’algorithme pageRank depuis sa sortie en 1998. L’équipe de Google a volontairement gardé une part de secret dans cet algorithme en donnant seulement le principe de base qui pour une page donnée calcule le rang d’une page. De ce fait de nombreux mathématiciens ont émis des hypothèses pour retrouver l’algorithme exact. Avec la formule du pageRank ces derniers n’ont qu’à essayer avec plusieurs paramètres et plusieurs hypothèses pour se rapprocher des vrais résultats retournés actuellement par la « Google Toolbar ».
3) La formule de l’algorithme pageRank
Même si tous les secrets de l’algorithme pageRank n’ont pas été testés la plupart des informations ont été données et cela suffit pour, dans un premier temps, s’intéresser à la formule mathématique qui a fait la gloire du moteur de recherche Google.
Les pages T1, T2, …, Tn possèdent des liens sortants vers la page A, le pageRank de la page A est le suivant :
PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
PR(A) est le pageRank calculée pour une page A (idem pour T1, Tn…).
d est un coefficient d’amortissement qui limite l’importance de la quantité des votes donnés à une page. Ce facteur peut être ajusté entre 0 et 1, il prend généralement la valeur 0.85.
La notation (1-d) est la garantie que la moyenne des pageRank de l’ensemble des pages Web est égal à 1.
T1 à Tn sont des pages qui émettent des liens vers la page A.
C(Tn) est le nombre de liens émis par la page Tn. Cette partie de la formule nous met la puce à l’oreille sur le fait que si une page Y qui pointe vers la page possède de nombreux liens sortants l’importance de chaque lien (et donc de celui pointant vers A) va être minimisé proportionnellement au nombre de liens.
Le résultat de cette formule donne dans la théorie des valeurs fractionnaires, en effet on peut s’apercevoir que le pageRank d’une page peut varier de 0.15 jusqu’à une valeur très grande. Hors nous avons vu précédemment (cf 2) la barre d’outils de Google) que les pageRank affichés dans la pratique sont compris entre 0 et 10 et ce ne sont que des valeurs entières.
Google cache une partie de son algorithme, certains parlent d’une échelle logarithmique de base 10 qui, en effet, fait retomber sur les bonnes valeurs les rangs calculés par le pageRank.
Voici les 11 possibilités de valeurs de pageRank affiché sur la barre d’outils de Google :
PageRank affiché[4] |
PageRank calculé par l'algo | ||
0 |
1 |
à |
10 |
1 |
10 |
à |
100 |
2 |
100 |
à |
1 000 |
3 |
1 000 |
à |
10 000 |
4 |
10 000 |
à |
100 000 |
5 |
100 000 |
à |
1 000 000 |
6 |
1 000 000 |
à |
10 000 000 |
7 |
10 000 000 |
à |
100 000 000 |
8 |
100 000 000 |
à |
1 000 000 000 |
9 |
1 000 000 000 |
à |
10 000 000 000 |
10 |
supérieur |
à |
100 000 000 000 |
Tableau II.3.b : PageRank affiché en fonction du pageRank calculé
Remarque :
L’échelle logarithmique de base 10 est reprise dans de nombreux articles traitant de l’algorithme pageRank de Google mais elle n’est en aucun cas énoncée explicitement par les fondateurs de l’algorithme. Cependant cette hypothèse offre des résultats qui se rapprochent du résultat retourné par la barre d’outil de Google et elle aide à la compréhension.
L’algorithme itératif
Si on s’intéresse de plus prés à la définition donnée dans la publication de Google on s’aperçoit que l’on parle d’un algorithme itératif et qui va donc de pages en pages pour calculer le pageRank de chacune d’elles, et ceci, en boucle. Une question se pose alors étant donnée la formule sur la valeur de pageRank de la première page visitée. Elle va influencer les valeurs des pageRank des pages vers qui elle a un lien sortant, et ainsi de suite. Il parait donc très important de connaître la valeur de pageRank de départ à donner ou à calculer et il faudrait pouvoir évaluer par la suite si la valeur choisie était la bonne.
→ En réalité le caractère itératif de l’algorithme fait que chaque itération fait converger les résultats vers une valeur de plus en plus précise. La valeur finale est retenue à chaque fin d’itération et est réinjectée dans l’itération suivante. On s’aperçoit alors que qu’elle que soit la valeur donnée en entrée l’itération fera toujours converger l’algorithme vers la même valeur. Pour accélérer le processus d’itération qui devrait boucler autant de fois que de pages visitées le facteur d’amortissement a été mis en place dans l’algorithme, il joue le rôle de modérateur et fait converger les valeurs rapidement. Le nombre d’itérations utilisé pour indexer le nombre impressionnant de pages Web existantes (quelques milliards) est d’environ 40.
Ce qui a été présenté jusque ici est la partie de l’algorithme du moteur de recherche. L’algorithme est la base du moteur de recherche Google mais depuis sa mise en fonctionnement en 1998 le moteur de recherche a subi des modifications. D’une part les robots d’indexation ont été améliorés (cf a-Le fonctionnement du moteur de recherche Google) et d’autre part des modifications ont été effectuées au niveau du PageRank afin que les notes données aux pages soient bien objectives et pertinentes.
En effet Google s’est intéressé de plus prés au contenu des pages et a mis en place un système pour évaluer si une page est bien en relation avec le texte du lien par lequel a est arrivé le robot d’indexation. Bien que Google ne dévoile rien sur les algorithmes utilisés sur de nombreux forums les administrateurs de sites parlent d’algorithme Hilltop et localrank.
De plus le PageRank veut se protéger des systèmes qui ont pour but de faire apparaître des pages dans le début des listes de réponse, et ceci en jouant avec l’algorithme PageRank. Pour se protéger de ses pages indésirables Google utiliserait des filtres identiques à ceux utilisés pour filtrer nos mails.
Le domaine des algorithmes des moteurs de recherche se montre divers et varié mais ce qui le caractérise le plus c’est l’évolution qu’il subit du fait de la forte demande des utilisateurs qui souhaitent trouver avec facilité, rapidité et fiabilité une réponse à leur requête. Dans le lot des moteurs de recherche Google a su se positionner dans les premiers dés son arrivée en 1998 avec son algorithme PageRank. Alors que sa place de numéro un est difficile à détrôner Google ne souhaite pas en rester là et, en plus des fonctionnalités de plus en plus nombreuses qu’il propose, renforce son algorithme afin de gagner en rapidité et en pertinence. Les caractéristiques présentées ci-dessus ne sont que des théories et, alors que les premiers moteurs de recherche sémantiques montrent le bout de leur nez certaines théories apparaissent désormais sur le fait que Google, lui aussi, se tournerait vers des outils sémantiques.
[1] GoogleBot : Robot d’indexation de Google
[2] Spider Bot : De l’anglais Robot araignée c’est un robot d’indexation qui parcourt les pages du Web telle une araignée du fait de la similitude de la structure d’Internet à une toile d’araignée.
[3] La barre d’outils de Google = Google Toolbar
[4] PageRank calculé selon une hypothèse d’utilisation d’une échelle logarithmique, cela dit très proche de la réalité.
/https%3A%2F%2Fassets.over-blog.com%2Ft%2Fcedistic%2Fcamera.png)
/http%3A%2F%2Ffile%3A%2F%2FC%3A%2FDOCUME~1%2Fagno%2FLOCALS~1%2FTemp%2Fmsohtml1%2F01%2Fclip_image001.gif)