L'algorithme PageRank de Google

Paul Jolissaint

Description

L'ensemble des pages web peut être modelisé par un graphe orienté : chaque page est representée par un point (appelé sommet du graphe) et on dessine une fleche d'un sommet.

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

L’algorithme PageRank de Google

Paul Jolissaint

Un moteur de recherche tel que Google doit faire trois choses :
1.Naviguersurlewebetlocaliser(sipossible)touteslespagesayantunacce`spublic.
2.Indexerlesdonn´eesci-dessuspourqu’ellespuissenteˆtreretrouve´esefficacementparmots-cle´sougroupes
de mots significatifs.
3.Classerl’importancedechaquepagedanslabasededonne´esdesortequelorsqu’uninternautefaitune
rechercheetquelesous-ensembledespagescorrespondantesdanslabasededonn´eesae´te´trouve´,les
pageslesplusimportantessoientpre´sent´eesenpremier.
Lebutdel’algorithmePageRankestder´esoudreletroisie`meproble`meci-dessus,etnousallonsexpliquercom-
mentonproc`edepoure´laborerleclassementdespageswebaveccetalgorithme.
L’ensembledespageswebpeutˆetremod´elise´parunpheoriene´tgraapeuseeg:qahct´enpaeeeptresr´nru
point(appel´esommetu’snhcdetmoemessitondefl`eneunude)ehpargAvers un sommetBsi et seulement si
la pageAcontient un lien hypertexteversla pageBeunleelpp’aesche`flelletenU.aeˆrtee´)eeitn(ro.
Notonsquelenombredepagesdanslewebestestim´e`aplusde60milliards,etGoogleenr´epertorieenviron
35milliards.Aussi,silapartieduwebindexe´eparGooglecontientn,oncagesp´rserepenedtnoivequharcteen
pageparunnume´roicompris entre 1 etne,otnd´esigneraparxilescorede la pagei. Il s’agit d’un nombre
compris entre 0 et 1 qui doit indiquer l’importance de la pageiau sens du point 3 ci-dessus : plusxiele´,e´vtse
plus l’URL de la pageieredruetomelesoproepquteisalslanapeguelaorsqchelcherıˆttoˆdtpaaparicontient
lesmots-cl´esdemand´es.Commepremi`erecondition,ondoitavoirxi> xjsi la pageiest plus importante que
la pagejnsisleconiitr`adt´eerfiaparpU.enispmcoehxiafa¸delnsonottn:eiuavocsnmile nombre de liens vers
la pagei, alorsxiorppturraitˆepopiraelarrtdee´nfimi/n.
Cette formule ignore toutefois un point crucial :une page est importante si d’autres pages importantes pointent
vers elle.Ainsi, si la pagejsepmitatro(etnesc’`at-ir-diesxjest grand) et s’il existe un lien de la pagejvers la
pageiuaaten’ddanoc,leega`ecapalpoimanrtplntd’usieidnvear’dnuetllissementl’´etabl,cnodnemguatiret
xievecalsregapsanspagertanimpoutlnbailu’eneidnqugetaanetn´ioesvadiefuts,oiveon´eutivetqreuoT.
des pages sans grande importance obtiennent un grand score par des moyens artificiels comme par exemple la
cre´ationd’ungrandnombredepagesfictivescontenantchacuneunlienverslapageenquestion.Ainsi,sila
pagejcontientnjliens vers d’autres pages, dont la pagei, on veut que la contribution de la pagejau scorexi
de la pageiitsoga´eal`xj/njontesapnage´a`lxj.
LesconcepteursdeGoogle,LarryPageetSergeyBrin,alorse´tudiantseninformatique`aStanford,ontadopte´
en1998lade´finitionsuivantedelasuitedesscoresx1, x2, . . . , xn: rappelons quenjengise´dsenliderembnole
contenus dans la pagejpour toutj(donc issus de la pagejvers d’autres pages, et on convient qu’un lien d’une
pageverselle-mˆemeestignore´),etsoitLi⊂ {1,2n. . ,, .}l’ensemble des pages qui ont un lien vers la pagei.
On demande alors que pour touti,
X
xj
xi=
nj
j∈Li
 
x1
P
 T
e que= 1.
et que les composantes de~x= =: (x1, . . . , xnalrm´eisiesonont)rtsodeesixi
.
xn
T
(SiMest une matrice quelconque, on noteMeess´.)snoptaar
Leproble`meaveclade´finitionci-dessusestquelecalculdexifait intervenir les autresxjqui sont a priori
eux aussi inconnus. On peut par exemple calculer des valeurs approximatives desxieunitil´ethodesantunem
(k)
it´erative:notonsxla valeur dexiaprasl`ekerextnapopassunecesseproiseltialO.noinine´tiitar-ime`elemp
i
(0)
x= 1/npour touti,)ocerni’siuqec(lantqu’aud´epartetpr`rteeesnitup`essntdemˆleesemtuotelsegapsopse
i
(k)
Px
(k+1)j
puisend´efinissantx= pourtout 1≤i≤net pour toutk≥0. On simplifie les notations en
i j∈Linj
1
introduisant la matriceAr1ou:pitsumeomects´dfieinuqei≤j≤n, on remplit la colonnejen posantdans
nj
(k)
la ligneisij∈Lie’c(-tsed-a`esirly’inlaundiejversi) et 0 sinon, et on note comme ci-dessus~xle vecteur
(k)
dont les composantes sont lesx.
i
De la sorte, on a
(k) (k+1)
A~x=~xetA~x=x~∀k≥0.

1

IlsemblequeGooglerecalculelesscoresunefoisparsemaine,enite´rantunprocessusprochedeceluid´ecrit
ci-dessuscarcedernierposequelquesproble`mesquenousallonsd´ecrireplusloin.
Enattendant,voiciunexemplesimplequipermetdesefaireuneid´eedelasituation:
Exemple.aviusehpargelrap:ntis´dCnonn´eebdosleweron

Celaconduitausyst`emelin´eaire:

x1=x3/1 +x4/2


x2=x1/3
x3=x1/3 +x2/2 +x4/2


x4=x1/3 +x2/2.
 
0 01 1/2
1/3 0 0 0
T

On posex~= (x1, x2, x3, x4atamtlesyduceriseeme`ts)tAsorte que= deAx~=x~.
 
1/3 1/2 0 1/2
1/3 1/2 00
Enr´esum´e,onchercheunvecteurx~comme ci-dessus dont les composantesxjsont positives, de somme 1,
T
etquisatisfaitl’e´quationA~x=~x. Elle admet une solution : c’est un multiple du vecteur~v= (12,4,9,6) ,donc
12 49 6T T
~x= (, , ,)≈(0.387,0.129,0.290,0.194) .
31 31 31 31
Remarque importante.Dans la description ci-dessus, on n’a pas tenu compte des ”pages cul-de-sac” (en
anglais : ”dangling nodes”) : ce sont les pages qui n’ont aucun lien vers une autre page, donc ce sont les pages
jpour lesquellesnj=Br0.etingePatronose´elulborpme`lreorecnnlocoueaqhctnac¸alpmerneea`adtnpsno
T
une page cul-de-sac par la colonne (1/n, . . . ,1/nteinr`rp)On.rnteinunteau:lorsqu’ionainsiomidcfitateceteet
visiteunepagecul-de-sac,laprobabilite´devisiterlesautrespagesduwebenquittantcelle-ciestuniforme.
Lese´quationsci-dessusposentuncertainnombredequestions:
P
–l’e´quation~xA=~xavecxi= 1 admet-elle une solution avecxi>0 pour touti?
i
–siunesolution`al’´equationci-dessusexiste,est-elleunique?
(k)
– dans le calcul de la suite (x~iuq)ehrproceeapens´estcx~? et sous quelles, le processus converge-t-il
conditions ?
Afindegarantirl’existenceetl’unicit´ede~xauit´’qeno,etlaconvergencedssecorpuenirB,sunteoagtPelfi´dimo
ci-dessus : le vecteur de score~xastlutolesauqenoitdnoi´’le

~x= ((1−m)A+mS)~x

o`u0< m <teetr`eamseutpnra1Sest la matricen×ntssociencoeffislesa`1agxutne´uottnod/n. On
P
d´emontreraquecettee´quationadmettoujoursuneuniquesolution~xtelle quexi= 1 et que tous lesxisont
i
strictement positifs. En 2005, Google utilisait la valeurm= 0.ronoisngN.uo51ee´silituruelavlarecoenst’eicss
aujourd’hui ;de plus, les diverses valeurs desxine sont pas publiques.
 
m1,1. . .m1,n
 
.
Afin d..leElsspode`euxde
e simplifier les notations, posons (1−m)A+mS=:M=...
mn,1m. . .n,n
proprie´t´escruciales:elleeststochastiqueparrapporta`sescolonnes,i.e.la somme des coefficients de chaque
n
colonne vaut 1, et tous les coefficientsmi,j>Ond´esigenapr0.V1(M) ={x~∈R|~Mx=x~}le sous-espace
~
propreassocie´a`lavaleurpropre1deM. Remarquons queV1(Msruelavsel,teffen0:eit`a´edupasre’tsn)
T
propres deMexntsoponsees´qseueclldesetaaractementlesmˆemeMedet`inraeretemd,eettcmeva1comleur
T
propre avec le vecteur propre constant (1, . . . ,puisque1) ,Mcieteditsa.euqstsehcott´vitrespoLatisiMadmet
lacons´equenceimportantesuivante:

2

Proposition 1SoitMcomme ci-dessus. Alors tout vecteur propre dansV1(M)a ses composantes soit toutes
positives,soittoutesn´egatives.
P P
Preuve.Observons d’abord que siy~ar`euctveunstencomposantesy1, y2y, ...n, alors|yi|| ≤yi|et que
i i
l’in´egalit´eeststrictesietseulementsicertainsyirusba’lredonosppSuparslosase´nuartfi.sgetaposisontetd’tifs
qu’il existe~x∈V1(Me´gnec(siatrpsendentigsssmnela´eltseocpmsonaetos)don).ivesegatesn´uartte’dvisesoti
P
Del’e´quationx~=~Mxuetquiedd´on,xi=mi,jxjpour touti, et commemi,j>0 pour tousietj, on a :
j
n
X X
|xi|=mi,jxj< mi,j|xj|.

j=1j
Ensommantcesine´galit´essuria`d1en, puis en intervertissant les sommes suriet surjon obtient
 !
n nn nn n
X XX XX X
|xi|< mi,j|xj|=mi,j|xj|=|xj|
i=1i=1j=1j=1i=1j=1
qui donne une contradiction.
n
Proposition 2Soient~vet~wdvaenusxdesriltcuerime´naend´eentiantspendRlauerre´sietnuvelorsilexleel.A
stelle que le vecteurx~=v~+sw~ou le vecteur~x=s~v+~wadmet des composantes positives et des composantes
ne´gatives.
P
Preuve.Comme~vet~wsonss.Posontsuedtnotnnluxuonpe´eannd,itssols´nilriaenemednitd=vi. Sid= 0,
i
alorsv~ees,cgdnesdieu`eeanqtcshapdoeoemsrdnerpedtsffisuosplites= 0 et donc de poser~x=v~. Sid6= 0,
P
P
wi
~
i
posonss=−et~x=v~s+w~, de sorte quexi= 0 et~x6= 0. Par suite,x~eriasseccsedtnemntsapnoaoem´es
d i
positivesetdescomposantesn´egatives.
Corollaire 3SiMest une matrice stochastique et positive, alorsV1(M)est de dimension1formetse´ed
P
multiples d’un vecteurx~dont les composantesxi>0pour toutiet telles quexi= 1.
i
Preuve.Supposons par l’absurde que dim(V1(M))≥2, et soient~