L'algorithme PageRank de Google Promenade sur la toile

Michael Eisermann

Description

Depuis plus d'une décennie, Google domine le marché des moteurs de recherche sur Internet. Son point fort ? Il trie intelligemment ses résultats par
ordre de pertinence. Son fonctionnement repose en faitsur une judicieuse modélisation mathématique.

Informations

• Publié par: Force_IT
• Nombre de lectures: 22
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français

Extrait

44

actions

Par Michael Eisermann

L'algorithmePageRankde Google Promenade sur la toile

Depuis plus d'une décennie, Google domine le marché des 12 moteurs de recherche sur Internet. 11 1 Son point fort? Il trie intelligemment ses résultats par 10 2 ordre de pertinence. Son fonctionnement repose en fait sur une judicieuse modélisation mathématique. 9 3

8 4 epuissa conception en 1998, Google conti- nue à évoluer et la plupart des améliora- L'id D ée principale, par contre, a été publiée et est dis- 7 5 tions demeurent des secrets bien gardés. 6 ponible en ligne. Le pilier du succès de Google est une judicieuse modélisation mathématique.Illustration de la structure de graphe du Web. ✛ Moteur de recherche ✛ La Toile est un graphe Une base de données a une structure prédéfinieProfitons du peu de structure qui soit disponible. qui permet d'en extraire des informations, parL'Internet n'est pas une collection de textes indé- exemple « nom, rue, code postal, téléphone… ».pendants, mais un immense hypertexte : les pages L’Internet, par contre, est peu structuré : c'est unese citent mutuellement. Afin d'analyser cette struc- immense collection de textes de nature variée.ture, nous allons négliger le contenu des pages et Toute tentative de classification semble vouée àne tenir compte que des liens entre elles. Ce que l'échec, d'autant plus que le Web évolue rapide-nous obtenons est la structure d'un graphe, dont la ment : une multitude d'auteurs ajoutent constam-figure suivante montre un exemple en miniature. ment de nouvelles pages et modifient les pagesDans toute la suite, notons les pages Web par P, 1 existantes. P… Pet écrivonsj→icite la pagesi la page P 2n j Pour trouver une information dans ce tasP . Dans notre graphe, nous avons un lien 1→5, i amorphe, l'utilisateur pourra lancer une recherchepar exemple, mais pas de lien 5→1. de mots clés. Ceci nécessite une certaine prépara- tion pour être efficace : le moteur de recherche✛ Pages pertinentes copie préalablement les pages Web en mémoire locale et trie les mots par ordre alphabétique. LeLes liens sur Internet ne sont pas aléatoires mais résultat est un annuaire de mots clés avec leursont été édités avec soin. Quels renseignements pages Web associées.pourrait nous donner ce graphe ? L'idée de base, encore à formaliser, est qu'un lienj→iest une Pour un mot clé donné, il y a typiquement desrecommandation de la page Pd'aller lire la page j milliers de pages correspondantes (plus d'un mil-P . C'est ainsi un vote de Pen faveur de l'autorité i j lion pour « tangente » par exemple). Commentet de la pertinence de la page P. i aider l'utilisateur à repérer les résultats potentiel-Analysons notre exemple sous cet aspect. La pré- lement intéressants ? C'est sur ce point quesentation suivante de notre graphe suggère une Google a apporté sa grande innovation.hiérarchie possible – encore à justifier.

N°130 SeptembreOctobre2009

✛ Comptage récursif

Contrairement aux modèles précédents, la page P estrepérée comme la plus importante. C'est 5 bon signe, nous sommes sur la bonne piste… Remarquons que le comptage récursif est un sys- tème denéquations linéaires àninconnues. Dans notre exemple, oùn= 12, il est déjà pénible à résoudre à la main, mais encore facile sur ordina- teur. Pour les graphes beaucoup plus grands, nous aurons besoin de méthodes spécialisées.

DOSSIER •EXPLORATIONS MATHÉMATIQUES

Ici le poids du votej→iest proportionnel au poidsmde la page émettrice. C'est facile à for- j muler, mais moins évident à calculer. Une métho- de efficace sera présentée dans la suite. Pour vous rassurer, vous pouvez déjà vérifier que notre exemple admet bien la solution :

Autrement dit,mest égal au nombre de « votes » i pour la page P, où chaque vote contribue par la i même valeur 1. C'est facile à définir et à calculer, mais ne correspond souvent pas à l'importance ressentie par l'utilisateur : dans notre exemple, on trouvem=m= 4, devantm=m= 3. 1 95 7 Mais ce qui est pire encore, c’est que ce compta- ge naïf est trop facile à manipuler en ajoutant des pages sans intérêt qui recommandent une page quelconque.

✛ Comptage pondéré

Heuristiquement, une page Pparaît importante si i beaucoup de pages importantes la citent. Ceci nous amène à définir l'importancemde manière i récursive comme suit :

1 6 7 8 9

Autrement dit,mcompte le nombre de « votes i pondérés » pour la page P. C'est facile à définir et i à calculer, mais ne correspond toujours pas bien à l'importance ressentie : dans notre exemple, on trouvem=m= 2 devantm= 3/2 etm= 4/3. 1 95 7 Et, comme dans la situation précédente, ce comp- tage est très facile à truquer.

Il est plausible qu'une page importante reçoit beaucoup de liens. Avec un peu de naïveté, on croira aussi l'affirmation réciproque : si une page reçoit beaucoup de liens, alors elle est importan- te. Ainsi on pourrait définir l'importancemde la i page Pcomme le nombre des liensj→i. En for- i mule, ceci s'écrit comme suit :

2 3 412 11 10

✛ Comptage naïf

SeptembreOctobre 2009N°130

45

Le graphe des liens entre les différentes pages.

Certaines pages émettent beaucoup de liens : ceux-ci semblent moins spécifiques et leur poids sera plus faible. Nous partageons donc le vote de la page Penlparts égales, oùldénote le nombre j jj de liens émis. Ainsi on pourrait définir une mesu- re plus fine :

P 1 P 2 P 3 P 4 P 5 P PP P P P P 6 7 8 9 10 1112 m=1 11).(2 11 1 3 1 2 1 2

Parmi les pages P, P, Pet P, la page Psert de 1 2 34 1 référence commune et semble un bon point de départ pour chercher des informations. Il en est de même dans le groupe P, P, Pet Poù la page 9 10 1112 P sertde référence commune. La structure du 9 groupe P, P, Pet Pest similaire, où Pest la 5 6 78 7 plus citée. À noter toutefois que les pages Pet P , 1 9 déjà reconnues comme importantes, font référence à la page P. On pourrait ainsi soupçonner que la 5 page Pcontient de l'information essentielle pour 5 l'ensemble, qu'elle est donc la plus pertinente.

5

actions

46

✛ Un peu d’aléa

L'ALGORITHME PAGERANK DE GOOGLE

tempst+ 1 sur la page Pest donc : i

Avant de tenter de résoudre le système linéaire, essayons d'en développer une intuition. Pour ceci, imaginons un « surfeur aléatoire » qui se balade sur Internet en cliquant sur les liens au hasard.Étant donnée la distribution initialep, cette loi de Comment évolue sa position ?transition définit la distribution suivantep' = T(p). À titre d'exemple, supposons que notre surfeurC'est ainsi que l'on obtient la lignet+ 1 à partir de démarre au tempst= 0 sur la page P . Le seul lienla lignetdans nos exemples. En théorie des pro- 7 pointe vers P, donc au tempstbabilités, ceci s'appelle une= 1 le surfeur s'ychaîne de Markov. 5 retrouve avec probabilité 1. D'ici partent troisLa mesure stationnaire est caractérisée par l'équa- liens, donc au tempsttion d'équilibre= 2 il se trouve sur une desm= T(m), qui est justement notre pages P, P, Pavec probabilité 1/3. Voici leséquation définissantmpar un comptage récursif. 6 7 8 probabilités suivantes (à 0,001 près) : ✛ Trous noirs P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9 P 10 P 11 P 12 Que se passe-t-il quand notre graphe contient une t=000 0,000 0,0 0,000 0,0000 0,000000 0,000 0,000 0,000 0,000 0,000 0,00 0, t=100, 00001, 0000, 0000, 0000, 000, 0000, 0000, 0000, 000,000 0,000 0,000 page (ou un groupe de pages) sans issue ?Pour t=000 0,000 0,000 0,000 0,33000 0,2 0,30, 0000, 0000, 3330, 3330, 0000, 000 illustration, reportez-vous au graphique de la t=0,0, 0003 0,1670000 0,167 0,000 0,000 0,000 0,000 0,333 0,000 0,333 0,00 page suivante. t=042 0,042 0,417 0,111 0,111 0,111 04 0,042 0,000 0,,042 0,000 0,042042 0, L'interprétation comme marche aléatoire permet t=5 0,1180, 0210, 0210, 0210,1110,139 0,021021 0,021 0,250 0,139 0,118 0, …          de résoudre l'équation définissantmpar un comp- t=29 0,117 0,059 0,059 0,059 0,117 0,059 0,177 0,059059 0,0,117 0,059059 0, tage récursif sans aucun calcul. La page P 13 t=30 0,117 0,059 0,059 0059 0,,059 0,117 0,059 0,117 0,177 0,059059 0,059 0, absorbe toute la probabilité car notre surfeur aléa- toire tombera tôt ou tard sur cette page, où il On observe une diffusion qui converge assez rapi-demeurera pour le reste de sa vie. Ainsi la solu- dement vers une distribution stationnaire.tion estm= (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1). Vérifions cette observation par un secondNotre modèle n'est donc pas encore satisfaisant. exemple, partant cette fois-ci de la page P: 1 ✛ Téléportation P P P P P P P P P P P P 1 2 3 4 5 6 7 8 910 11 12 Pour échapper aux trous noirs, Google utilise un t=000 0,000 0,0 1,000 0,0000000 0,000 0,000 0,000 0,000 0,000 0,000 0,00 0, t=1000, 2500, 2500, 2500, 2500, 0000, 0000, 0000, 000, 000,000 0,000 0,000 modèle plus raffiné : avec une probabilité fixéec, t=08375 0,125 0,125 0,125 0,000 0,2 0,30, 0000, 0000, 0000, 0000, 0830, 083 le surfeur abandonne sa page actuelle P et recom- j t=229 0,156 0,3 0,156 0,156 0,177 0,042 0,000 0,083 0,000 0,0000 0,000 0,00 mence sur l’une desnpages du Web, choisie de t=234 0,135 0,135 0,135 0,151 0,4 0,059 0,059 0,059 0,000 0,010 0,010 0,010 manière équiprobable. Sinon, avec probabilité t=233 0,126 0,126 0,126 0,115 0,8005005 0,005 0,045 0,050 0,0,109 0,0, 050 …          1 –c, le surfeur suit l’un des liens de la page P, j choisi de manière équiprobable. Cette astuce de t=05059 0,059 0,059 0,177 0,059 0,117 0,69 0,117 0,90,117 0,059 0,059 0,059 t=70 0,117 0,059 0,059 0,059 0,059 0,117 0,059 0,117 0,177 0,059059 0,059 0, « téléportation » évite de se faire piéger par une page sans issue, et garantit d'arriver n'importe où Bien que la diffusion mette plus de temps, ladans le graphe, indépendamment des questions de mesure stationnaire est la même ! Elle coïncideconnexité. d'ailleurs avec notre solutionm= (2, 1, 1, 1, 3, 1,Dans ce modèle, la transition est donnée par : 2, 1, 2, 1, 1, 1), ici divisée par 17 pour normaliser la somme à 1. Les pages pour lesquellesmest le i plus grand sont les plus « fréquentées » ou les plus « populaires ». Dans la quête de classer les pages Web, c'est encore un argument pour utiliserLe premier termec/nprovient de la téléportation, la mesure m comme indicateur.le second terme est la marche aléatoire précéden- te. La mesure d'équilibre vérifie donc : ✛ Transition Comment formaliser la diffusion illustrée ci-des- sus ? Supposons qu'au tempstnotre surfeur aléa- toire se trouve sur la page Pavec une probabilitéLe paramètrecest encore à calibrer. Pourc= 0, j pnous obtenons le modèle précédent. Pour. La probabilité de partir de P et de suivre le liencdans j j j→iest alorsp/ll’intervalle ]0 ; 1], la valeur 1/. La probabilité d'arriver aucest le nombre j j

N°130 SeptembreOctobre2009

5

1 6 7 8 9

2 3 413 12 11 10

Modification du graphe.

DOSSIER

moyen de pages visitées, c'est-à-dire le nombre de P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9 P 10 P 11 P 12 liens suivis plus un, avant de recommencer sur t=0 1,000 0,000 0,000 0,0000 0,000 0,000 0,000 0,000 0,000 0,00000 0,000 0, t=10, 0130, 2250, 2250, 2250, 2250, 0130, 0130, 0130, 0130,013013 0,013 0, une page aléatoire (processus de Bernoulli). C’est t=028 0,072 0,305 0,111 0,111 0,111 0,60, 0200, 0870, 0200, 0200, 0760, 034 ce modèle qui est appelé PageRank. Par exemple, t=0,124 0,3 0,18610028 0,028 0,071 0,021 0,085 0,021 0,24 0,124 0,158 0,28 le choixc= 0,15 correspond à suivre environ six t=057 00,105 0,105 0,105 0,140 0,4 0,180075 0,057 0,,040 0,057 0,040040 0, liens en moyenne, ce qui semble une description t=0,120, 0950, 0950, 0955 0,1716042042 0,042 0,087 0,052 0,0,101 0,0, 052 réaliste.Pour conclure l'analyse de notre exemple, …          t=066 0,066 0,055 0,102 0,066 0,150 0,0529 0,120 0,5066066 0,066 0,0,120 0, le tableau de la marche aléatoire partant de la t=066 0066 0,066 0,30 0,120 0,,066 0,066055 0,120 0,066 0,150 0,055 0,102 0, page Ppeut être visualisé ci-contre.: 1 La mesure stationnaire est vite atteinte, et la page P arriveen tête avecm= 0,15, avant les pages Avec quelques outils mathématiques et 5 5 P etP avecm=m= 0,12. 1 91 9 une habile stratégie d’entreprise, Google avons utilisé des arguments heuristiques et desre de « po i pularité ». Le théorème du point fixe ❜ ✛ PageRank gagne des milliards. Afin de développer un modèle prometteur, nousla page P , le modèle PageRank définit une mesu- illustrations expérimentales. Fixons maintenantassure que cette équation admet une unique solu- ce modèle et posons-le sur un solide fondementtion, et justifie l’utilisation dep’ (méthode itérati- théorique. Nos calculs aboutissent bel et bienve) pour l'approcher. Cet algorithme itératif est dans notre exemple miniature, mais est-ce tou-facile à implémenter et assez efficace pour les jours le cas ? Le beau résultat suivant y répond engraphes de grandeur nature. Muni de ces outils toute généralité :mathématiques et d'une habile stratégie d'entre- Considérons un graphe fini quelconque et fixonsprise, Google gagne des milliards de dollars. Il le paramètrecdans ]0 ; 1]. Alors l'équation véri-fallait y penser ! fiée par la mesure d’équilibremadmet une unique solution vérifiantm+ …m= 1. Dans cette solu-M.E. 1n tion,m,…msont tous positifs. Pour toute dis- 1n tribution de probabilité initiale, le processus de diffusionp’ converge vers cette unique mesure R É F É R E N C E stationnairem. La convergence est au moins aussi n rapide que celle de la suite géométrique (1 –c) vers 0. • Jacques Bair,Comment La démonstration de ce résultat découle d’une Google classe les pages ?, o application du théorème du point fixe. Tangente Supn 44–45, pp. 10–13, sep- Pour être utile, un moteur de recherche doit non tembre–octobre 2008. seulement énumérer les résultats d'une requête, • Michael Eisermann, mais également les classer par ordre d'importan- Comment fonctionne ce. Or, estimer la pertinence des pages Web est un Google ?, profond défi de modélisation. En première www-fourier.ujf-gre- approximation, Google analyse le graphe formé noble.fr/~eiserm/enseigne par les liens entre pages Web. Interprétant un lien ment\\#google", 15 pages, j→ien faveur decomme « vote » de la page P 2008. j

SeptembreOctobre 2009N°130

47