Google et l’algorithme PageRank

Jean-Paul Delahaye

Description

Les moteurs de recherche, google et son algorithme de pagerank

Informations

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

Extrait

9
Google
etl’algorithmePageRank

Lestroispremi`eressectionsdecechapitrefontappel`al’alge`breline´aire(diago-
nalisation,valeursetvecteurspropres)etauxprobabilit´es´ele´mentaires(ycompris
l’ind´ependanced’e´ve´nementsetlaprobabilite´conditionnelle).Ellesconstituentlapar-
tie´ele´mentairedecechapitre,peuventˆetrecouvertesentroisheuresetdonnentune
fortbonneid´eedel’algorithmePageRank.Lasection 9.4c´an;eertpaavietitsaleunoc
ellerequiertuneconnaissancedebasedel’analysere´elle(pointd’accumulation,conver-
genced’unesuite)etpeutˆetrecouverteenuneoudeuxheuressuppl´ementaires.

9.1Lesmoteursderecherche

Danslemondenum´erique,lesnouveauxbesoinssonthabituellementrapidement
combl´espardenouveauxproduitsoudenouveauxalgorithmes.Ceuxquiutilisentla
grande Toile (World Wide Webd)uelqnnsauiepuesqes,8991s-paris,des´euiepsdon
pellerontsansdouteavoirutilis´elesmoteursderecherchepropose´sparlescompagnies
AltaVistaetYahoo.Maintenant,cesmeˆmespersonnesutilisentprobablementlemo-
teur de recherche de la compagnie Google. Parmi les moteurs de recherche tout usage
delaToile,lasupre´matiepre´sentedeGoogles’est´etablieenquelquesmois.Googlel’a
gagn´eegrˆace`aundesalgorithmesqu’elleutilisepourordonnerlespagestrouve´espar
sonmoteurderecherche;ils’agitdel’algorithmePageRank.Lebutdupre´sentchapitre
estdede´crirecetalgorithmeetlesmath´ematiquessurlesquellesilrepose,leschaˆınes
de Markov.
L’utilisationd’unmoteurderechercheestsimple.Quelqu’un,assis`aunordinateur
relie´a`laToile,de´sireconnaˆıtrelesmeilleuressourcesd’informationsurunsujetparti-
culier.Supposons,`atitred’exemple,qu’ilcherche`aconnaıˆtrelaquantit´edeneigeque
1
rec¸oitMontre´alannuellement.Ilchoisitd’interrogerlemoteurdeGoogle`al’aidedes

1
L’adresse de la page de Google estwww.google.com, ou encorewww.google.caet
www.google.fr.

274 9Google et l’algorithme PageRank

Fig. 9.1.ehcrreceGrooehusUnstomsedr´eenemgltiarape`ipice´rpatitno,neige,mnotr´ealet
si`ecle

9.1 Lesmoteurs de recherche275
motse´rpipicitatonneigemontr´ealise`lcemoerniereublemtsrte´uepn.egna.S(uellde
Mais l’utilisateur choisit d’ajouter ce mot afin d’obtenir des statistiques sur une plus
longuep´eriode.)Lemoteurre´ponda`l’aided’unepremie`repagedesuggestions(voirla
figure 9.1aftse’sepnuneetilaueeqqucherchree´irsepuniidueerrehoabarntalrizoeu).L
moinsd’undixie`medesecondeetqueGoogleatrouve´323pagesquipourraienteˆtre
pertinentes.Lapremi`ereprovientduServicedestravauxpublicsetdel’environnement
delaVilledeMontre´al,etonytrouvedesstatistiquesdebasesurlespre´cipitations
deneige`aMontr´eal.(Lerecorddepuisquedesstatistiquessontenregistr´eespeuty
ˆetrelu:353,3cmdurantl’hiver1946-1947.Mais,re´jouissez-vous,onyapprendquela
moyennedesdixdernie`resanne´esn’estquede206,7cm.)Lapremie`resuggestionde
Googleadoncbiendeschancesdere´pondre`alaquestiondel’utilisateur.Qu’enest-il
e
desautressuggestions?Ladernie`re,c’est-`a-direla323,me`neaute´l´echargementde
notesdecoursconc¸uesparl’Acad´emiecanadiennedelaDe´fenseetintitul´eesQualifica-
tioninterme´diaireenleadershipsteeenbiCe.xttee´tnteˆrniolisedlisateursdel’utic,ra
ilneparlepasdutoutdespre´cipitationssurMontr´eal.Maiscecoursdequelque240
pages contient effectivement les motsneige,omtn´raeletecles`i.
2
Cetteanecdoteenseigneune´l´ementimportant:Googleparvienta`ordonnerles
pages qu’il propose en mettant en premier celles qui sont les plus susceptibles de
r´epondreauxd´esirsdel’utilisateur.Larechercheseraitfortfastidieusesiildevaitre-
garderlesquelque300pagespourytrouvercequ’ilcherche.Lesmotspropos´espar
l’utilisateurauronte´videmmentunimpactsurlespagesqueGoogletrouvera.Mais
commentunordinateurpeut-ildevinerlesd´esirsoul’ordredepre´fe´rencedesutilisa-
teurs ?
Lesoutilsderechercheautomatise´edatentd´ej`adequelquesd´ecennies.Onpensera
auxcataloguesdebibliothe`ques,auxregistresgouvernementaux(desnaissances,maria-
ges,d´ec`es,dufisc,del’assurancemaladie. . .ou)coenaureasxbodnnseedrpfoe´seon-essi
nelles(delajurisprudencepourlesprofessionsjuridiques,desmaladies,m´edicaments
etproc´eduresme´dicalespourlesprofessionsdelasant´e. . .). Ces sources d’information
ontquelquespointsencommun.Toutd’abord,l’informationquiyestrassembl´eeest
biencirconscrite.Tousleslivresd’unebibliothe`queontuntitre,unoudesauteurs,
unemaisond’e´dition,unedatedeparution,etc.L’tie´uinofmredisr-aos`ontimaornf
ganiser est donc utile, tant pour la classification que pour la recherche. Lait´equalde
lapr´esentationestaussiunecaract´eristiquecommune.Habituellement,lesfichessi-
gnale´tiquesdeslivressontcr´ee´espardesprofessionnels,lesbibliothe´caires,etletaux
d’erreuresttr`esfaible.Etsiuneerreurestd´etect´ee,ellepeuteˆtreaise´mentcorrige´e.
L’et´miorfinudes utilisateurs et de leurs besoins est aussi un avantage. Le but des cata-
loguesdebibliothe`quesestavanttoutlerep´eragedesdocumentsdisponibles.Bienque

2
Cetexemplenousenseigneautrechose.Silelecteurrefaitaujourd’huilarecherche`a
partirdesquatremˆemesmots,lere´sultatserafortprobablementdiffre´.tneepereagprLai`em
reproduite`alafigure 9.1irce´’dtnemomuasleets,neigslcerenombredepagesepluxistn’e
trouve´esserasansdouteplusgrand.IlfautdoncconclurequelaToileestununiverschangeant
constamment.

276 9Google et l’algorithme PageRank
lesmotstechniquesabondentenm´edecine,touslesm´edecins,infirmiersetprofessionnels
delasant´elesconnaissent.Touspourrontdoncfouillerdanslesbasesdedonn´eeseffi-
cacement. Lerythme de progressions,elpmexesecsuotruladesebaodede´nnseseop,t
relativementlent.Dansunebiblioth`eque,peudelivresdisparaissentchaqueanne´e,et
lesajoutsd´epassentrarement10%delacollectionenplace.Ajoutonsa`celaquele
titredeslivres,leurcote,leursauteurs,etc.,nechangentpas!Lamise`ajourdelabase
dedonne´espeutdonceˆtrefaitepardeshumains.Enfin,unconsensustrˆeacefi-tuep
lemente´tablisurlaqualit´edel’informationa`re´pertorier.Danstouslesd´epartements
d’universit´e,uncomite´estcharge´derecommanderlesachatsdesbiblioth`equesquiles
desservent.Deplus,lesprofesseursaiguillerontleurse´tudiantsverslesmeilleurslivres
pour leurs cours.
Aucunedecescaracte´ristiquesn’existesurlaToile.Lespagesquis’ycˆotoientontles
fonctions les plus diverses : information technique ou professionnelle, promotionnelle,
commerciale,culturelle,etc.Laqualit´evadunec plus ultrat´eaocriue:obsol`ne´idlama
peuts’attendrea`beaucoupdefautesd’orthographeet`adeserreursdanslesinformations
mˆemesquisontdisponibles(queceserreurssoientvolontairesounon).Lesutilisateurs
sont aussi nombreux que les fonctions des diverses pages qui se trouvent sur la Toile,
eteluaevinrulimifadeav´eitarostuceelrecelidsheeshercrˆemtextnemeravtlbaiaL.e
Toilecontinuedesede´veloppera`unrythmeeffogGot,enemlluecteugolatacelr´en´e.A
des dizaines de milliards de pages. Un grand nombre apparaissent chaque jour. Et quoi
deplus´eph´eme`requelespagesproduitesparunseulindividu.Enfin,ilsembleillusoire
d’´etablirunconsensussurlaqualit´eoul’ordredespagese´tantdonne´leurnombre,leur
diversit´eetcelledesint´ereˆtsdescentainesdemillionsd’utilisateurs.Lespagesdela
Toile n’ont rien en commun!
En fait, ceci est faux. Les pages de la Toileontquelque chose en commun. Elles
sont´ecritesdanslelangagedecodageHTML(hypertext markup language) ou dans un
desesdialectes.Etellesontreli´eesl’unea`l’autredemani`ereuniforme;lesliensentre
pagessonttoujoursannonce´sdanslecodeHTMLparquelquessymbolespr´ece´dant
leuradresse,c’est-`a-direleurURL(uniform resource locatortpones.C)emtnecs´rcesie´
liens qu’un humain peut suivre pour se promener sur la Toile et qu’un ordinateur peut
diffpmroattnpsuolrsentles´el´ementsineic´reciuqsegaeutitsnoxtteduerimesudeo
humains.Enjanvier1998,quatrechercheursdel’Universite´Stanford,L.Page,S.Brin,
R. Motwani et T. Winograd [1], proposaient un algorithme pour ordonner les pages de
la Toile. Cet algorithme, le PageRank, utilise, non pas le contenu textuel ou visuel des
3
pages, mais la structure des liens entre elles.

3
Lesquatrepremie`reslettresdunomPageRank´erre`fatneerpureimauteurdecerapport
technique et non aux pages de la Toile que l’algorithme ordonne.

9.2 Toile et chaˆı