background image

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

8

pages

Français

Documents

Écrit par

Publié par

Lire un extrait
Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

8

pages

Français

Documents

Lire un extrait
Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

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

Publié par

Langue

Français

Poids de l'ouvrage

1 Mo

Preprint version available at http://www-fourier.ujf-grenoble.fr/˜eiserm
L’ALGORITHME PAGERANK DE GOOGLE: UNE PROMENADE SUR LA TOILE
MICHAEL EISERMANN
DepuisplusdunedecennieGoogledomine lemarchedesmoteursderecherchesurinter-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 desameliorationsdemeurentdessecretsbien gardes.Lideeprincipale,parcontre,aetepu-bliee [1] : le pilier de son succe`s est une judi-cieusemodelisationmathematique.
QUE FAIT UN MOTEUR DE RECHERCHE?
LE 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 immensehyper-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 predeniequipermetdenextrairedesinfor-mations, par exemple«nom, rue, code pos-tal,telephone,...». L’internet, par contre, est peu structure : c’est une immense collection de textesdenaturevariee.Toutetentativedeclas-sicationsemblevouee`alechec,dautantplus quelewebevoluerapidement:unemultitude d’auteurs ajoutent constamment de nouvelles pages et modifient les pages existantes. Dans la suite je note les pages web par P1,P2,P3, . . . ,Pnrisetjecjisi la pagePjcite Pour trouver une information dans ce tas la pagePi. Dans notre graphe nous avons un amorphe, l’utilisateur pourra lancer une re-lien 15, par exemple, mais pas de lien 51. cherchedemots-cles.Cecinecessiteunecer-tainepreparationpoureˆtreefcace:lemo-teur de recherche copie prealablement les pages web en memoire locale et trie les mots par COMMENT EXPLOITER CE GRAPHE? ordrealphabetique.Leresultatestunannuaire demots-clesavecleurspageswebassociees.Leslienssurinternetnesontpasaleatoires maisonteteeditesavecsoin.Quelsrenseigne-Pourunmot-cledonneilyatypiquementdes 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- mentaiderlutilisateura`repererlesresultatslienjiest une recommandation de la pagePj potentiellement interessants ? C’est ici que d’aller lire la pagePi. C’est ainsi un vote dePj Googleaapportesagrandeinnovation.enfaveurdelautoritedelapagePi. Date: premie`re version juin 2009.Dnierre`esemioja`:ru17 juillet 2009. DocumentensupportdemonexposeauxJourneesAPMEPa`Rouenenoctobre2009.
Voir icon more
Alternate Text