Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

Du même publieur

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.
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin