Université de Technologie de Belfort Montbéliard par Sid Lamrous

Déroulement de l’algorithme de
PageRanking

1
 Université de Technologie de Belfort Montbéliard par Sid Lamrous

Exemple du cours
PageRanking Iter (0) Iter(1) Iter(2) Iter(3)
des pages

PR(A) ¼
PR(B) ¼
PR(C) ¼
PR(D) ¼

• Ici, à l’étape initiale les valeurs des PR sont équiprobables.

Mais dans la réalité, les valeurs initiales proviennent des
valeurs de l’indexation documentaire comme vue dans la
première partie du cours

2
 Université de Technologie de Belfort Montbéliard par Sid Lamrous

À l’itération 1
d étant le facteur d’amortissement = étant probabilité de suivre effectivement les liens proposés par une page

PR1(A)=(Probabilité d’arriver sur la page A sans suivre les liens) + (Probabilité d’arriver sur la page A en suivant les liens entrants vers A)

$%& (c)
!"# (A)=(1-d) + d #
On note !"( (X)
PageRanking de la
= (1-0.85)+0.85(1/4)=0.15+0.2125 page X à l’étape r

= 0.3625 !" (A) )

$%& (A) La notoriété que donne
!"# (B)=(1-d) + d 1 la page A à la page B
'
est à diviser par 2, car A
= (1-0.85)+0.85(1/8)=0.15+0.10625 référence une autre
page (page C)
= 0.25625
PageRanking des Iter (0) Iter(1) Iter(2) Iter(3)
pages

PR(A) ¼ 0.3625
PR(B) ¼ 0.25625
PR(C) ¼ ?
3
PR(D) ¼ ?
 Université de Technologie de Belfort Montbéliard par Sid Lamrous

À l’itération 1
$%& (A) $%& (B) $%& (D) - 2 liens sortants de A, C ne
!"# (C)=(1-d) + d '
+ # + # récupère que la moitié de la
notoriété donné par A…à
diviser par 2 donc.
= (1-0.85)+0.85(1/8+1/4+1/4) - Par contre, C récupère toute
la notoriété donnée par B et

= 0.15+0,53125=0.68125 D…à diviser par 1 !

!"# (D)=(1-d) + d )*+*, -./, !

Quand vous publiez une page sur le
= (1-0.85)+0.85(0)=0.15 WEB, votre seul score proviendrait
des termes d’indexation utilisés.

= 0.15 (restera à ce PR tant que D n’est pas référencé !!!!) D’où l’intérêt de faire de la
promotion …chercher des liens
entrants venant des réseaux sociaux
ou autres sites… Sinon, vous resterez
dans l’ombre !

PageRanking des Iter (0) Iter(1) Iter(2) Iter(3)

pages

PR(A) ¼ 0.3625
PR(B) ¼ 0.25625
PR(C) ¼ 0.68125
4
PR(D) ¼ 0.15 0.15 0.15
 Université de Technologie de Belfort Montbéliard par Sid Lamrous

À l’itération 2
$%& (c)
!"#(A)=(1-d) + d ' -Il faut prendre le PR
résultant de l’étape d’avant
= (1-0.85)+0.85(0.68125)=0.15+0.57906 -A est référencée par une
bonne page ! Son score
= 0.7290625 augmentera vite
$%& (A)
!"#(B)=(1-d) + d #

= (1-0.85)+0.85(0.3625/2)=0.15+0.1540625
= 0.3040625
$%& (A) $%& (B) $%& (D)
!"# (C)=(1-d) + d #
+ ' + '

= (1-0.85)+0.85((0.3625/2)+0.2562+0.15) = 0.15+ 0.4993=0.6493

PageRanking des Iter (0) Iter(1) Iter(2) Iter(3)
pages

PR(A) ¼ 0.3625 0.7290

PR(B) ¼ 0.2562 0.3040
PR(C) ¼ 0.68125 0.6493
5
PR(D) ¼ 0.15 0.15 0.15
 Université de Technologie de Belfort Montbéliard par Sid Lamrous

$%& (c)
À l’itération 3
!"#(A)=(1-d) + d
'
-Il faut prendre le PR
= (1-0.85)+0.85(0.6493)=0.15+0.57906 résultant de l’étape d’avant
-A est référencée par une
= 0.7290625 bonne page ! Son score
augmentera vite
$%& (A)
!"#(B)=(1-d) + d (

= (1-0.85)+0.85(0.7290/2)=0.15+0.309825 Tant que nous n’avons pas propager et

stabiliser la notoriété passée en liens
= 0.4598 dans le réseau, l’ordre peut changer. Il
faut conclure après convergence. C’est-
$%& (A) $%& (B) $%& (D) à-dire qu’on retrouve les mêmes
!"# (C)=(1-d) + d (
+ '
+ '
valeurs d’une colonne à l’autre…

= (1-0.85)+0.85((0.7290/2)+0.3040+0.15) = 0.15+ 0.695725=0.8457

PageRanking des Iter (0) Iter(1) Iter(2) Iter(3)
pages

PR(A) ¼ 0.3625 0.7290 0.7019

PR(B) ¼ 0.2562 0.3040 0.4598
PR(C) ¼ 0.68125 0.6493 0.8457
6
PR(D) ¼ 0.15 0.15 0.15