Google et l’algorithme PageRank
25 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Google et l’algorithme PageRank

-

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
25 pages
Français

Description

Les moteurs de recherche, google et son algorithme de pagerank

Sujets

Informations

Publié par
Nombre de lectures 17
Langue Français

Exrait

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ˆınes de Markov

9.2ToileetchaıˆnesdeMarkov277

4
LaToileconstitu´eedesmilliardsdepagesetdesliensquilesrelientpeuteˆtre
repr´esent´eeparungrapheoriente´,c’est-a`-direunecollectiondenœuds(lespages)reli´es
entreeuxpardesareˆtesorient´ees(lesliens).Parexemple,lafigure 9.2uetnese´rperne
(minuscule) toile qui ne contiendrait que cinq pages (A,B,C,DetE.)flseLch`ees
trac´eesentrecespagesindiquentque
•le seul lien partant de la pageApointe vers la pageB;
•les liens de la pageBpointent vers les pagesAetC;
•les liens de la pageCpointent vers les pagesA,BetE;
•le seul lien de la pageDpointe vers la pageA;
•les liens de la pageEpointent vers les pagesB,CetD.

Fig. 9.2.Une toile de cinq pages et ses liens

Pourde´terminerl’ordre`adonnera`chacunedecescinqpages,nousconside´reronsun
algorithmePageRanksimplifie´.Supposonsqu’unpromeneurimpartial(ouunautomate)
navigue sur cette toile en cliquant sans biais sur les liens qui lui sont offerts. Lorsqu’il
n’yaqu’unchoix(parexemple,quandilsetrouve`alapageD), il cliquera sur le seul
lien qui lui est offgelapane`aim`eileluqnecnodrus,erett(A`elaorvuslteS.i’)eagap
Cpagaela`tnanemneilelairisholc,iAfois,lelienmenanelitredssela`tgapaeBun
autretiersdesfoiset,enfin,lelienmenant`alapageEle reste du temps. En d’autres
mots,lorsqu’ilest`aunepagedonne´e(parexemple,lapageC), il choisira entre les pages
qui lui sont offertes (les pagesA,BetElorsqu’il est enCse´tilib)eciS.elpsorabvacee´ag
promeneurestlaiss´ea`sonjeu,changeantdepageunefois`alaminute,a`quellepagesera-
t-ildansuneheure,dansdeuxjours,apr`esunnombretr`esgranddesauts?Ou,puisque

4
LorsquePageetsescollaborateurspubli`erentleuralgorithmeen1998,ilsestimaienta`
environ150millionslenombredepageset`a1,7 milliard le nombre de liens. En 2006, le
nombredepagese´taitdel’ordredeladizainedemilliards.

278 9Google et l’algorithme PageRank
ladestinationdechacundesesmouvementsestd´etermine´edefac¸onprobabiliste,avec
quelleprobabilite´setrouvera-t-il`aunepagedonn´eeapr`escettelonguepromenade?

Fig. 9.3.enruocmmnec¸nastemierspasdupromeLedserpxugeapala`elpire´pnoC

Lafigure 9.3uxpresdeourlionpeutsttqea`ecopdn´ermerournedscipnu’eimelcsr
commen¸cant`alapageC. Cette page offre trois liens, et le promeneur ne pourra aller
qu’aux pagesA,BetEea,isniA.pelse`rpremierclic,ilserteorvure`alapagaAavec
1 1
probabilite´,a`lapageBe´litibobacerpgelapaevta`aEbaborpcevatnemel´ega,´eitil
3 3
1
.C’estcequiestindique´danslacolonnem´edianedelafigure 9.3par les trois relations
3
1 1 1
p(A) =, p(B) =, p(E) =,
3 3 3
alors que les deux relations

9.2ToileetchaıˆnesdeMarkov279
p(C) = 0, p(D) = 0
indiquentqu’apre`slepremierclic,lepromeneurnepourrapaseˆtreauxpagesCouD,
caraucunlienn’ym`enedelapageCo`uiait`l´etpate´’lae´ce´rpeChe.ntdestdeiusnraoc
1
cheminsestindique´paruntraitauquelnousavonsajoute´lenombrepourindiquer
3
laprobabilite´decechemin.Et,commeilsedoit,
p(A) +p(B) +p(C) +p(D) +p(E) = 1,
c’est-`a-dire:lepromeneursetrouvesuˆrementenunedescinqpagesdelatoile.
Lere´sultatdecepremierclic´etaitsimpleetpr´evisible.Celuidusecondclicl’est
moins. Lafigure 9.3ittaneme´eurotcejartselennodiblesdusirespossS.lipeorcenopdsa
enAaimerlcree`rppelsslrecii,rue´aassenmentBnE.dnoceeaslespr`effet, il n’a qu’un
1
choixpossiblea`partirdeAn.Puisqu’il´etaiteAvaninuceorpeibabt´lieedce,emch
3
1
contribuerapour`alaprobabilit´edeseretrouverenBaM.cilcdalsiapr`eslesecon
3
1
probabilit´ep(Bpaptsaeces`rsecliccondunau,caresn’)inn,epd´ectrmiheadneuatn
3
sensdesprobabilit´es,ym`ene.C’estceluiquivientdelapageE.erimerpelse`rpa,iS
clic,lepromeneursetrouvea`lapageEreaborilibse´ttne,sir,avec´egalesp,liopruarhcio
1 11
les trois pagesB,CetD. Chacun de ces chemins contribuera pour×= aux
3 39
probabilit´esp(B),p(C) oup(D) de se trouver aux pagesB,CouD.cnoceilcd`epressla
Quoiquelespossibilit´essoientplusnombreusesetlesprobabilite´squiysontrattache´es,
pluscompliqu´ees,lebilanestrelativementsimple.Apr`eslesecondclic,lepromeneurse
retrouveraauxpagesdelatoileaveclesprobabilite´ssuivantes:
1 45 1
p(A) =, p(B) =, p(C) =, p(D) =, p(E) = 0.
6 9 18 9
`
Anouveau,ilestrassurantdeve´rifierque
1 45 13 + 8 + 5 + 2 + 0
p(A) +p(B) +p(C) +p(D) +p(E+ +) =0 =+ += 1.
6 9 18 918
Ouf!Les´etapessontclaires,etpeut-ˆetrepourrions-nousencorecalculerlesproba-
bilite´spourlesquelquesprochainsclics.Maisilestutiledeformaliserlecomportement
du promeneur impartial. L’outil naturel est la chaˆıne de Markov.
Uneri´lasotaeocprsues{Xn, n= 0,1,2,3. . .}taioerslbselae´utseevediaarfanellmi
param´etr´eesparl’entiern. Nous supposerons que chacune de ces variablesXnprend
ses valeurs dans un ensembleTfini. Dans l’exemple du promeneur,Test l’ensemble
des pages de la toileT={A, B, C, D, E}. Pour chaque minuten∈{0,1,2,3, . . .}, la
position du promeneur estXnetd´miersaounsvoialun,ervecsbacojoursdan.Tou´ne
ci-dessuslesprobabilit´esquelesvariablesale´atoiresX1etX2prennent une des cinq
valeurspossiblese´tantdonn´equelepromeneurcommenceenCra´mpeCeci.xprieste
uneprobabilite´conditionnelleP(I|Jeuqe´tililbtasbeiourqp)atenemenv´´el’Ise produise
sil’e´v´enementJs’est produit. Par exemple,P(X1=A|X0=Cbobalitigienalrp)esd´´e
quelepromeneursetrouve`alapageA(cliclse`rpareimerpeX1=A) s’il se trouvait
enCrtpa(due´aX0=C). Ainsi,

280 9Google et l’algorithme PageRank
1 1
p(X1=A|X0=C) =, p(X1=B|X0=C) =, p(X1=C|X0=C) = 0,
3 3
1
p(X1=D|X0=C) = 0, p(X1=E|X0=C) =,
3
et
1 45
p(X2=A|X0=C) =, p(X2=B|X0=C) =, p(X2=C|X0=C) =,
6 9 18
1
p(X2=D|X0=C) =, p(X2=E|X0=C) = 0.
9
Lamarcheale´atoiredupromeneurimpartialposs`edelaproprie´te´-cl´ed´efinissantles
chaıˆnesdeMarkov.Voicitoutd’abordlad´efinitiondeceschaıˆnes.

D´efinition9.1Soit{Xn, n= 0,1,2,3, . . .}ursavelstsenenaerrpoiat´ealusssceropnu
dansT={A, B, C, . . .}. On dit que{Xn}litie´Markovsilaprobabtsecenuıˆaheden
p(Xn=i),i∈Ttate´’lepd´ne,deuedqenXn−1noedetnti’la`sntprnstaeden´ec´
valeursant´erieuresXn−2, Xn−3, . . .Nous noterons parN <∞lmoneme´esntedbrel’´
de l’ensembleT.

Dansl’exempledupromeneurimpartial,lesvariablesale´atoiressontlespositionsXn
apr`esleclicnEn.fareanisnemtelattnem´sels´eitesduetapuldocalcltsennnabalirpbo
des diffener´uelavsetedsrX1etX2irenbtroou,puesqnotatsnocsuon,´tseibilorabelps
apre`slepremierclic,nousn’avonsutilise´quelefaitquelepromeneurcommen¸cait`ala
pageCecrinetb`rpasellsqoralroou,puelsseueelbalirpbosecoesleic,sndcl´eitsp(X1=
A), p(X1=B), . . . , p(X1=Enireetmrdee´´)tdela.ueCttpesoisibilsontentr´eesenje
probabilit´edechaquee´tatapre`sleclicnibil´tseedpsorabclicapr`esleirrtpa`an−
1estlaproprie´te´deMarkov.Maistouslesprocessusal´eatoiresnesont-ilspasdes
chaˆınesdeMarkov?Certainementpas.Nouspouvonschangerl´ege`rementlesr`eglesde
lamarcheale´atoiredupromeneurpourqu’elleperdelapropri´et´edeMarkov.Supposons,
parexemple,quenousvoulionsempeˆcherlepromeneurderetournerimm´ediatementaux
pagesd’o`uilvient.Parexemple,apre`slepremierclic,lepromeneursetrouveauxpages
A,BetE`airaevneecv´gepalababotililagerpseutpesrpas.´eneIlCdritrapaegapale`
Aesaptrera`psgariedsilp,maiefaieutlBetE. Nous pouvons interdire au promeneur
derebrousserchemina`partirdecespagesBetE. Ainsi, pour cette nouvelle marche,
lepromeneurn’auraitqu’unchoixa`partirdeBr`leaal(A),`apartirartiedxutelineua
deEr`a(uanleldeespagesBetD¸cortlanroepnemea`ruive´,retis.)eCttmerahcfe
possible,lesretoursimme´diatsviolelapropri´ete´deMarkov:elleaunem´emioer. En
effe´tisborplibae,topminerlesurd´eterP(X2onevonsc,n)sdoulumenoesrtneanıˆesentl
probabilite´sapre`sleclic1,maisaussilapage(oulespages)ou`lepromeneurimpartial
setrouvaitavantlepremierclic.Lesr`eglesquenousavonsutilise´esjusqu’`apr´esentsont
doncparticulie`resausensmath´ematique:unechaıˆnedeMarkovn’apasdem´emoire.
Ellen’utilisequelasituationpr´esentedupromeneurpourd´eterminercelle`al’instant
suivant.

9.2ToileetchaıˆnesdeMarkov281
LeschaˆınesdeMarkovontlegrandavantagequeleur´etata`toutinstantntrepeutˆe
d´etermine´a`l’aidedel’´etatinitial(p(C) = 1 dans l’exemple de lafigure 9.3) et d’une
matrice de transitionrpa´needno
p(Xn=i|Xn−1=j) =pij.(9.1)
Une matricePˆahcenu’dnoitisntsievskoareMedın-ueelrepr´esentueenamrtcidetear
ment si
!
pij∈[0,tout1] pouri, j∈Tetpij= 1pour toutj∈T .(9.2)
i∈T
Pourlepromeneursurlatoile,les´el´ementspij, i, j∈T, de la matricePntsetenerrpe´
donclaprobabilit´edeseretrouver`alapageiegap´eilt,enla`aittalcci,iua´cderpe´s
j∈Tecavishoseisuqtucli’´nnoeveessommesdenousnoutraieluqgeelmiap.`ralsiaM
´egalesprobabilit´esentretouslesliensquecettepageluidonne.Silapagejoffre le
1
choix entremliens, alors la colonnejde la matricePlignes quicontiendra aux
m
repre´sententlespagesverslesquellesjpoiet0ttnneuesriallelice´’delI.aftsircrael
matrice de transition pour la (minuscule) toile de lafigure 9.2. La voici :
A B C D E
 
1 1
0 10A
2 3
1 1
1 00B
3 3
P=1 1(9.3)
0 00C
2 3
1
 
0 0 0 0D
3
1
0 00 0E
3
Lese´l´ementsnonnulsd’unecolonneindiquentlesdestinationspossibles:delapage
E, le promeneur ne peut aller qu’aux pagesB,CetDnonnents’uneulsdL.´lmesee´
lignedonne´eindiquentlesoriginespossibles.Parexemple,lefaitqu’unseule´l´ementde
la ligneDstnoinuonepnn’oquueiqndlittecerdniettatueantvenayequ’epage´alsiti
pageEauparavant.
Que veut dire la seconde contrainte de(9.2)virce´?eP´oa`al-snoerdnerr,ruelocpm
l’aidedelade´finition(9.1):
! !
pij=p(Xn=i|Xn−1=j) = 1,
i∈T i∈T
quiselitcommesuit:si`al’instantn−,1elysts`emeestdaatnsl’´etjibil´teslaproba,alor
qu’ilsetrouve`al’instantnte´spstasnadednuro,eeucn1tO.emsest`edusyblesossi
dansl’exemplepre´ce´dent,lepromeneurquisetrouvesurunedespagesdelatoilea`
l’instantn−1 tombera certainement sur une autre page deT`esaaprqilcriovnuruse´u
lien.C’estdoncunee´quationassez´evidente.
Cette formalisation a de grands avantages. Nous pouvons par simples multipli-
cations matricielles reproduire l’exercice laborieux des deux premiers clics. Comme
pre´c´edemment,noussupposeronslepromeneur`alapageCsni.tiAarepd´au

282 9Google et l’algorithme PageRank
  
p(X0=A) 0
p(X0=B) 0
0
p=p(X0=C) = 1.
  
  
p(X0=D) 0
p(X0=E) 0
1 10
Levecteurdeprobabilit´esplpmistsecilcreimreepsl`epratemenp=P pet donc,
    
1 11
p(X1=A) 01 00
2 33
1 11
p(X1=B) 10 00
3 33
1 11
p=p(X1=C1 = 0) = 00 0
 2 3  
1
    
p(X1=D0 00 0 0) 0
3
1 1
p(X1=E0 00 0) 0
3 3
commenousl’avionscalcul´e.Delamˆemefa¸con,lesecondclicdonneralieua`unvecteur
2 12 1
deprobabilite´spobtenu depparp=P p:
    
1 11 1
p(X2=A1 0) 0
2 33 6
1 11 4
p(X2=B0 0) 1
3 33 9
2 11 5
p=p(X2=C0 =) = 00 0.
 2 3 18
1 1
    
p(X2=D00 0 0) 0
3 9
1 1
p(X2=E0 00 0) 0
3 3
Lecalculdesprobabilit´esapre`slespremieretsecondclicsindiquentcommentcelles
n n−1
apr`eslenmeneptraslesontr´ecursivotnonetb:seuellei`-esemp=P p, ou encore
directement par
n n−1n−2 0n0
p=P p=P(P p) =∙ ∙ ∙=P P∙ ∙ ∙P p=P p.
) +
nfois
Les contraintes(9.2)sur les matrices de transition dePquencesqui´enscoestdon
sont vraies pour toutes les chaˆınes de Markov et qui sont capitales pour l’algorithme
PageRank.
Pourde´couvrirlapremie`reproprie´te´a`l’e´tude,nousprendronsquelques-unesdes
4 8 16
puissances de la matricePque nous venons d’introduire. Les puissancesP ,P ,Pet
32
P,se`tnos:isroecd´alimpress`atndiearro,
  
0,333 0,296 0,204 0,167 0,420 0,265 0,313 0,294 0,323 0,279
0,222 0,463 0,531 0,667 0,160 0,420 0,360 0,409 0,372 0,381
4 8
P= 0,389 0,111 0,160 0,000 0,370, P= 0,217 0,233 0,191 0,201 0,252,

  
0,056 0,000 0,031 0,000 0,019 0,031 0,022 0,018 0,012 0,035
0,000 0,130 0,074 0,167 0,031 0,067 0,072 0,088 0,092 0,052
  
0,294 0,291 0,293 0,291 0,294 0,293 0,293 0,293 0,293 0,293
0,388 0,392 0,389 0,391 0,391 0,390 0,390 0,390 0,390 0,390
16 32
P= 0,220 0,219 0,221 0,221 0,218, P= 0,220 0,220 0,220 0,220 0,220.
  
  
0,024 0,025 0,025 0,025 0,024 0,024 0,024 0,024 0,024 0,024
0,074 0,073 0,072 0,072 0,074 0,073 0,073 0,073 0,073 0,073

  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents