L'algorithme PageRank de Google - une promenade sur la toile

Michael Eisermann

Description

L'algorithme PageRank de Google - une promenade sur la toile

Sujets

• Informatique
• Marketing et communication

Informations

• Publié par: ejegatuz
• Nombre de lectures: 184
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

Preprint version available at http://www-fourier.ujf-grenoble.fr/˜eiserm

L’ALGORITHME PAGERANK DE GOOGLE: UNE PROMENADE SUR LA TOILE

MICHAEL EISERMANN

Depuisplusd’uned  ecennieGoogledomine lemarch  edesmoteursderecherchesurinter- net. Son point fort est qu’il trie intelligemment ses resultats par ordre de pertinence. Com- ment est-ce possible ? Depuis sa conception en 1998,Googlecontinuea ` evolueretlaplupart desam  eliorationsdemeurentdessecretsbien gard  es.L’ide  eprincipale,parcontre,ae  te  pu- bliee [1] : le pilier de son succe`s est une judi- cieusemod  elisationmath  ematique.

Q UE FAIT UN MOTEUR DE RECHERCHE ?

L E WEB EST UN GRAPHE !

Profitons du peu de structure qui soit dis- ponible. L’internet n’est pas une collection de textes independants mais un immense hyper- texte: les pages se citent mutuellement.

Afin d’analyser cette structure nous allons negliger le contenu des pages et ne tenir compte que des liens entre elles. Ce que nous obtenons est la structure d’un graphe. La figure suivante montre un exemple en miniature.

Une base de donnees a une structure pr  ed  efiniequipermetd’enextrairedesinfor- mations, par exemple«nom, rue, code pos- tal,te  l  ephone,...». L’internet, par contre, est peu structure : c’est une immense collection de textesdenaturevari  ee.Toutetentativedeclas- sificationsemblevou  ee ` al’e  chec,d’autantplus queleweb  evoluerapidement:unemultitude d’auteurs ajoutent constamment de nouvelles pages et modifient les pages existantes. Dans la suite je note les pages web par P 1 ,P 2 ,P 3 , . . . ,P n risetj’  ecj→isi la pageP j cite Pour trouver une information dans ce tas la pageP i . Dans notre graphe nous avons un amorphe, l’utilisateur pourra lancer une re- lien 1→5, par exemple, mais pas de lien 5→1. cherchedemots-cl  es.Cecine  cessiteunecer- tainepr  eparationpoure ˆ treefficace:lemo- teur de recherche copie prealablement les pages web en memoire locale et trie les mots par C OMMENT EXPLOITER CE GRAPHE ? ordrealphab  etique.Lere  sultatestunannuaire demots-cle  savecleurspageswebassocie  es.Leslienssurinternetnesontpasal  eatoires maisont  et  ee  dite  savecsoin.Quelsrenseigne- Pourunmot-cl  edonne  ilyatypiquementdes ments pourrait nous donner ce graphe ? milliers de pages correspondantes (plus d’un million pour«tangente» L’idee de base, encore a` formaliser, est qu’un , par exemple). Com- mentaiderl’utilisateura ` rep  ererlesre  sultatslienj→iest une recommandation de la pageP j potentiellement interessants ? C’est ici que d’aller lire la pageP i . C’est ainsi un vote deP j Googleaapporte  sagrandeinnovation.enfaveurdel’autorit  edelapageP i . Date : premie`re version juin 2009. Dnierre ` esemioja ` :ru17 juillet 2009. Documentensupportdemonexpos  eauxJourn  eesAPMEPa ` Rouenenoctobre2009.