Un moteur de recherche, pour le meilleur et pour le pire

Nous sommes en train de faire une expérience nouvelle : un ensemble de données d’une taille incroyablement supérieure au volume de tous ceux dont nous avons pu disposer jusqu’à présent est accessible instantanément grâce à Internet. En glissant nos doigts sur le clavier d’un ordinateur relié au réseau des réseaux, nous faisons apparaître sur l’écran de notre machine une page web (composée de textes et d’images) choisie parmi une quantité inouïe de documents électroniques, physiquement localisés sur les ordinateurs du monde entier.

Bien sûr, pour s’y retrouver, des outils sont nécessaires. Vous pouvez noter les adresses des pages qui vous sont utiles, mieux, vous pouvez stocker ces adresses et les organiser en tenant compte de vos critères propres : ce sont les systèmes de signets (bookmarks). Vous pouvez aussi télécharger les pages qui vous intéressent le plus et les ranger dans des dossiers de votre ordinateur, dossiers que vous classerez en les emboîtant ; cela constituera une bibliothèque personnelle électronique que vous compléterez en suivant les liens contenus dans ces pages stockées. En théorie, on se débrouille par de tels moyens artisanaux, et, au début du web, chacun travaillait ainsi.

Qu’est-ce qui a changé ? Les moteurs de recherche ! Ils vous dispensent presque totalement des signets et des téléchargements. Si vous voulez connaître les rapports entre deux personnages que rien ne rassemble, tapez dans le moteur de recherche Einstein + Marilyn Monroe, les réponses vous surprendront.

Premiers résultats obtenus pour la requête Einstein + Marilyn Monroe (le 29 janvier 2007).

Ces moteurs de recherche ont bouleversé l’usage du web et ont contribué à son succès. Leur fonctionnement se fonde sur des milliers d’ordinateurs stockant des copies des pages les plus importantes, et constituant de volumineux index qui permettent de savoir sur quelle page et à quel endroit dans la page se trouve tel mot, ainsi que des informations associées, dont la très importante « note de notoriété » de chaque page.

Grands nombres

Aucun moteur de recherche ne réussit à tout stocker et traiter. C’est d’ailleurs impossible, puisque certaines pages dynamiques changent de contenu toutes les heures, voire toutes les secondes, et que d’autres sont engendrées à la demande. Le moteur de recherche Google annonçait en 2005 qu’il traitait 8 milliards de pages (8 168 684 336, le 4 septembre 2005), ce qui est beaucoup, surtout qu’une page web contient souvent plus d’informations qu’une page de livre ou de journal. Depuis lors, Google ne publie plus de chiffres aussi précis, mais revendique toujours plus de 8 milliards de pages indexées.

Préparation des données de Google.
La collecte des données se fait en permanence et incrémente le contenu des mémoires des milliers d’ordinateurs de la société Google. Ce contenu définit un graphe où chaque page est représentée par un point et est reliée par les liens indiqués sur chaque page. Pour attribuer la note de notoriété de chaque page, on imagine un surfeur aléatoire passant de page en page en procédant selon les règles suivantes. Dans 15 pour cent des cas, et aussi lorsque la page ne contient pas de lien vers une autre page, il choisit au hasard une page parmi toutes les pages possibles et retravaille à partir de celle-là. Dans les autres cas, il choisit au hasard un des liens de cette page, clique dessus et se rend à la page citée. Le PageRank théorique de la page P est la probabilité pour que le surfeur aléatoire se trouve sur cette page P et cette probabilité est une mesure fine de notoriété.
Infographie : Pour la Science

Parmi les idées utilisées pour faire fonctionner les moteurs de recherche, celle à l’origine du PageRank (pour déterminer la notoriété d’une page) est remarquablement simple et efficace. Cet algorithme révolutionnaire a fait le succès du moteur de recherche de la société Google. Tout le monde est concerné par son fonctionnement. On ignore si cet algorithme a été nommé PageRank parce qu’il note les pages web et donc permet de les ranger, ou s’il doit son nom à l’un de ses inventeurs, Larry Page. Avec l’autre inventeur, Sergey Brin, ils fondèrent la société Google en septembre 1998, alors qu’ils préparaient une thèse en informatique à l’Université Stanford en Californie. Leur thèse, jamais terminée, portait sur le PageRank qui est aujourd’hui breveté et constitue un nom déposé.

Le nom Google quant à lui provient du mot googol introduit par Edward Kasner pour désigner le nombre 10¹⁰⁰ (un 1 suivi de 100 zéros). L’immeuble du siège Californien de la société porte le nom de Googleplex, un googleplex étant le nombre 10^googol, c’est-à-dire un 1 suivi de un googol de zéros. Le succès du moteur de recherche Google est tel qu’un nouveau verbe a été créé en anglais pour désigner son utilisation : to google.

Sélectionner, puis ranger

Lorsque vous interrogez le moteur de recherche de Google, par exemple avec les mots Enigma Turing, il détermine toutes les pages (parmi celles que ses robots d’exploration ont visitées et qui sont stockées par la société Google) qui comportent les deux mots Enigma et Turing. (Notons que les majuscules n’ont pas d’importance pour Google.) Il trouvait ainsi 77 000 références le 4 septembre 2005, et le 29 janvier 2007 à Paris, environ 491 000.

L’ordre dans lequel Google affiche ces pages pertinentes pour répondre à votre interrogation dépend de nombreux facteurs, mais les deux principaux sont, d’une part, la proximité des mots recherchés dans le texte et, d’autre part, la note qui a été attribuée à chaque page par l’algorithme PageRank. Plus les mots sont proches dans une page, plus elle a de chances de se retrouver bien placée parmi les réponses retenues, mais parmi toutes les pages comportant Enigma et Turing rapprochées (elles sont très nombreuses), PageRank fixe l’ordre des réponses. On comprend l’importance du classement : pour qu’une page soit proposée dans le premier écran de résultats, il faut qu’elle soit bien notée par PageRank.

Recherche des sites pertinents
Lorsque l’on interroge le moteur de recherche Google pour trouver les pages contenant une série de mots, un calcul est opéré comportant deux phases.
1. La recherche des pages répondant à la requête, c’est-à-dire contenant effectivement les mots recherchés. Ce travail est effectué grâce à d’énormes index informatiques (analogues aux index des livres) qui ont été calculés à l’avance après l’opération mensuelle de parcours du Web par les robots logiciels de Google en charge de télécharger tout ce qu’on peut trouver.
2. La classification des pages retenues qui fait apparaître en tête les pages les plus intéressantes. Pour cette classification, les deux principaux facteurs pris en compte sont la proximité des mots recherchés dans les pages retenues, et la notoriété des pages. Celle-ci a été calculée à l’avance par l’algorithme PageRank mis au point par les créateurs de Google en 1998.
Infographie : Pour la Science

L’évaluation de la note est fondée sur un principe de vote démocratique et sur ce que l’on désigne par le modèle du surfeur aléatoire. Ces deux idées garantissent à la fois la pertinence des résultats et une certaine robustesse aux tentatives de manipulations. L’évaluation de notoriété produite par PageRank est calculée grâce à une astuce que nous allons voir, classant les quelque 8 milliards de pages prises en compte.

Objectivité ?

Avant de détailler le principe et le calcul pratique de PageRank, précisons que lorsque l’on interroge Google sur un mot ou une liste de mots, il répond de manière « objective » par une liste de liens placés à gauche sur la page de résultats et qu’il n’est pas possible d’acheter une bonne place sur cette liste en payant Google. Selon les propres mots de la firme : « Google ne pratique pas la vente des positions dans les résultats : il est impossible d’acheter une valeur PageRank supérieure à la réalité du Web. Avec la recherche Google, vous disposez d’une solution simple, rapide, honnête et objective pour trouver des sites Web dont les informations répondent à vos besoins ».

En revanche, les liens affichés à droite, de même que certains placés en haut sur fond grisé, sont des liens commerciaux, pour lesquels il faut payer, et ce sont eux qui permettent à Google de gagner de l’argent. (Ces liens sont peu nombreux en général : il n’y en a pas si vous interrogez Google sur Turing seul ; il y en a un si vous l’interrogez sur Enigma.) Cette « objectivité » des réponses principales de Google est sans doute un élément important de son succès, mais aujourd’hui rien ne la garantit : Google affirme qu’aucun critère commercial n’entre en ligne de compte dans l’affichage des réponses principales qu’il affiche, mais personne, sauf lui, ne peut le vérifier. Nous reviendrons sur ces aspects éthiques, traités de manière insatisfaisante à l’heure actuelle.

Le PageRank d’une page est un nombre qui mesure sa notoriété. En principe, il s’agit d’une probabilité, donc d’un nombre entre 0 et 1 ; cependant, ce nombre peut être, par commodité, multiplié par un facteur constant positif, on peut aussi en prendre le logarithme ou effectuer d’autres transformations, pourvu qu’elles ne changent pas l’ordre des classements.

Le surfeur aléatoire est un utilisateur imaginaire du web, qui va de page en page, toujours en avant (c’est-à-dire sans jamais utiliser le bouton de « retour à la page précédente ») et qui, lorsqu’il affiche une page, choisit pour aller à la suivante un lien au hasard sur la page affichée : il choisit en tirant au sort l’un des liens présents sur la page courante, sans en favoriser aucun. Lorsque la page affichée est une page sans lien, une page « cul-de-sac », le surfeur choisit au hasard une page parmi les milliards de pages disponibles et reprend sa promenade aléatoire.

De plus, pour éviter que le surfeur aléatoire reste dans une même zone de l’espace web, à chaque nouvelle page, le surfeur, avec une probabilité fixée à l’avance, appelée le coefficient d’échappement (en général 0,15), choisit une nouvelle page parmi toutes les pages possibles. Un tel surfeur imaginaire qui parcourt indéfiniment le web passera plus de temps sur les pages citées par un grand nombre de pages, et moins sur les autres. Cette proportion de temps passée sur une page donnée est le PageRank théorique de la page (nous le nommons PageRank théorique, car celui calculé diffère en plusieurs points de celui de la théorie).

À ce modèle correspond une formule reliant le PageRank d’une page à celui des pages qui ont un lien vers elle, mais avant d’expliquer cette formule tirons un certain nombre de conséquences de la définition.

Démocratie dans le cyberespace

Le principe d’attribution de cette valeur de notoriété est fondé, non pas sur une notation humaine ou sur l’observation du nombre de fois qu’une page a été réellement consultée (ces deux éventualités sont impossibles à mettre en œuvre), et il concerne chaque page et non chaque site web : les pages d’un même site peuvent avoir des PageRank très différents. Même si une page n’est jamais visitée par les internautes, elle peut avoir un bon PageRank ; pour augmenter le PageRank de votre page personnelle, ne perdez pas votre temps à l’ouvrir dix fois par jour !

Une autre conséquence importante de la définition de PageRank est que le contenu des pages, à l’exception des liens qui y apparaissent, n’a aucune importance pour sa notation et que cette notation est globale : toute la structure des référencements des huit milliards de pages intervient dans le PageRank théorique et non pas seulement les pages proches (à quelques clics de celle à laquelle vous vous intéressez).

L’indifférence de PageRank relativement au contenu de la page a parfois été mal comprise. Elle ne signifie pas que les pages affichées en réponse à une question posée à Google sont sans rapport avec le contenu général de la page, car, bien sûr, pour qu’une page soit affichée en réponse à une requête, il faut avant tout qu’elle contienne les mots voulus (PageRank n’intervient qu’après la présélection des pages pertinentes). De plus, c’est en fonction du contenu de votre page que ceux qui réalisent de nouvelles pages la mentionneront ou non : il importe donc que les mots importants liés au sujet de votre page y apparaissent… et que votre page soit intéressante !

En consultant le site Google PageRank Calculator, vous aurez une idée du PageRank des pages qui vous intéressent, mais un tel outil est fondé sur ce que Google accepte de dévoiler ; le PageRank que Google rend public est un nombre entier entre 0 et 10 qui, d’après les spécialistes, est une approximation du logarithme du PageRank théorique et non le PageRank lui-même.

Début de la liste des sites ayant un PageRank de 10 affichée sur le site Search Engine Genie (janvier 2007).

Les pages qui ont la note de 10 sont indiquées sur le site Search Engine Genie. Parmi ces pages, on note celles de la NASA, du MIT, de Harvard, de Apple, de Microsoft, de Adobe, du New York Times et de… Google !

Principe mathématique du surfeur aléatoire

L’étude du surfeur aléatoire se ramène à un problème mathématique assez classique rattaché à la théorie des processus de Markov. Elle conduit à la formule suivante que nous allons examiner.

Si p est une page dont l’adresse apparaît dans les pages p₁, p₂,…, p_i alors le PageRank Pr(p) de p est lié aux PageRank Pr(p₁), Pr(p₂),…, Pr(p_i) de p₁, p₂,…, p_i par cette formule, qui fait aussi intervenir K le nombre total de pages pris en compte, e le coefficient d’échappement (0,15 généralement), et NL(p_m) le nombre de liens total vers d’autres pages que contient la page p_m (qui, par hypothèse, contient un lien vers p) :
Pr(p) = e/K + (1 – e) [Pr(p1)/NL(p₁) + Pr(p₂)/NL(p₂) + … + Pr(p_i)/NL(p_i)].

Cette formule est riche d’informations. D’abord, PageRank est un « bien » que chaque page distribue aux pages qu’elle cite : si une page en cite beaucoup, elle ne transmet à chacune qu’une faible partie de sa richesse ; si elle en cite peu, elle les enrichit plus. Ainsi, 15 % de votre PageRank sera équitablement transmis aux milliards d’autres pages qui, puisqu’elles sont très nombreuses, recevront individuellement très peu de ces 0,15 (c’est l’idée que le surfeur aléatoire avec une probabilité de 0,15 choisit de s’échapper sur une page prise au hasard). Pour les 85 % restant, si vous ne citez qu’une page, ils iront vers elle ; si vous en citez deux, ils seront partagés et iront pour moitié à chacune. Plus généralement : si votre page possède NL liens, chacune des pages citées recevra 0,85/NL du PageRank de votre page.

En clair, chaque page vote pour les pages dont elle mentionne l’adresse et reçoit des votes de toutes les pages qui la mentionnent. Son vote pour une autre page a une force proportionnelle à son PageRank et inversement proportionnelle au nombre de pages qu’elle mentionne.

Une page p donnée peut avoir un très gros PageRank théorique même si elle n’est citée que par une seule page q, à condition que q soit très populaire et que cette page q ne cite que très peu de pages. À l’autre extrême, une page peut être très populaire parce qu’elle est citée par un très grand nombre d’autres pages, même si aucune des pages qui la citent n’a un fort PageRank. La détermination du PageRank théorique s’apparente à un super-jeu de démocratie se mordant la queue : chaque page vote, et l’ensemble de tous ces votes, y compris ceux du type « A vote pour B qui vote pour A », fixe la notoriété de chacune.