282
9 Google et l’algorithme PageRank
p
0 =
⎛
⎜
⎜
⎜
⎜
⎝
p(X 0 = A)
p(X 0 = B)
p(X 0 = C)
p(X 0 = D)
p(X 0 = E)
⎞
⎟
⎟
⎟
⎟
⎠
=
⎛
⎜
⎜
⎜
⎜
⎝
0
0
1
0
0
⎞
⎟
⎟
⎟
⎟
⎠
.
Le vecteur de probabilit´ es p
1 apr` es le premier clic est simplement p
1 = P p
0 et donc,
p
1 =
⎛
⎜
⎜
⎜
⎜
⎝
p(X 1 = A)
p(X 1 = B)
p(X 1 = C)
p(X 1 = D)
p(X 1 = E)
⎞
⎟
⎟
⎟
⎟
⎠
=
⎛
⎜
⎜
⎜
⎜
⎝
0
1
2
1
3
1 0
1 0
1
3
0
1
3
0
1
2
0 0
1
3
0 0 0 0
1
3
0 0
1
3
0 0
⎞
⎟
⎟
⎟
⎟
⎠
⎛
⎜
⎜
⎜
⎜
⎝
0
0
1
0
0
⎞
⎟
⎟
⎟
⎟
⎠
=
⎛
⎜
⎜
⎜
⎜
⎝
1
3
1
3
0
0
1
3
⎞
⎟
⎟
⎟
⎟
⎠
comme nous l’avions calcul´ e. De la mˆ eme fa¸ con, le second clic donnera lieu ` a un vecteur
de probabilit´ es p
2 obtenu de p
1 par p
2 = P p
1 :
p
2 =
⎛
⎜
⎜
⎜
⎜
⎝
p(X 2 = A)
p(X 2 = B)
p(X 2 = C)
p(X 2 = D)
p(X 2 = E)
⎞
⎟
⎟
⎟
⎟
⎠
=
⎛
⎜
⎜
⎜
⎜
⎝
0
1
2
1
3
1 0
1 0
1
3
0
1
3
0
1
2
0 0
1
3
0 0 0 0
1
3
0 0
1
3
0 0
⎞
⎟
⎟
⎟
⎟
⎠
⎛
⎜
⎜
⎜
⎜
⎝
1
3
1
3
0
0
1
3
⎞
⎟
⎟
⎟
⎟
⎠
=
⎛
⎜
⎜
⎜
⎜
⎝
1
6
4
9
5
18
1
9
0
⎞
⎟
⎟
⎟
⎟
⎠
.
Le calcul des probabilit´ es apr` es les premier et second clics indiquent comment celles
apr` es le n-i` eme sont obtenues : elles le sont r´ ecursivement par p
n = P p
n−1 , ou encore
directement par
p
n = P p
n−1 = P (P p
n−2 ) = · · · = P P · · · P
n fois
p
0 = P
n p
0 .
Les contraintes (9.2) sur les matrices de transition de P ont des cons´ equences qui
sont vraies pour toutes les chaˆ ınes de Markov et qui sont capitales pour l’algorithme
PageRank.
Pour d´ ecouvrir la premi` ere propri´ et´ e ` a l’´ etude, nous prendrons quelques-unes des
puissances de la matrice P que nous venons d’introduire. Les puissances P
4 , P
8 , P
16 et
P
32 , arrondies ` a trois d´ ecimales pr` es, sont :
P
4 =
⎛
⎜
⎜
⎜
⎜
⎝
0,333 0,296 0,204 0,167 0,420
0,222 0,463 0,531 0,667 0,160
0,389 0,111 0,160 0,000 0,370
0,056 0,000 0,031 0,000 0,019
0,000 0,130 0,074 0,167 0,031
⎞
⎟
⎟
⎟
⎟
⎠
, P
8 =
⎛
⎜
⎜
⎜
⎜
⎝
0,265 0,313 0,294 0,323 0,279
0,420 0,360 0,409 0,372 0,381
0,217 0,233 0,191 0,201 0,252
0,031 0,022 0,018 0,012 0,035
0,067 0,072 0,088 0,092 0,052
⎞
⎟
⎟
⎟
⎟
⎠
,
P
16 =
⎛
⎜
⎜
⎜
⎜
⎝
0,294 0,291 0,293 0,291 0,294
0,388 0,392 0,389 0,391 0,391
0,220 0,219 0,221 0,221 0,218
0,024 0,025 0,025 0,025 0,024
0,074 0,073 0,072 0,072 0,074
⎞
⎟
⎟
⎟
⎟
⎠
, P
32 =
⎛
⎜
⎜
⎜
⎜
⎝
0,293 0,293 0,293 0,293 0,293
0,390 0,390 0,390 0,390 0,390
0,220 0,220 0,220 0,220 0,220
0,024 0,024 0,024 0,024 0,024
0,073 0,073 0,073 0,073 0,073
⎞
⎟
⎟
⎟
⎟
⎠
.
9 Google et l’algorithme PageRank
p
0 =
⎛
⎜
⎜
⎜
⎜
⎝
p(X 0 = A)
p(X 0 = B)
p(X 0 = C)
p(X 0 = D)
p(X 0 = E)
⎞
⎟
⎟
⎟
⎟
⎠
=
⎛
⎜
⎜
⎜
⎜
⎝
0
0
1
0
0
⎞
⎟
⎟
⎟
⎟
⎠
.
Le vecteur de probabilit´ es p
1 apr` es le premier clic est simplement p
1 = P p
0 et donc,
p
1 =
⎛
⎜
⎜
⎜
⎜
⎝
p(X 1 = A)
p(X 1 = B)
p(X 1 = C)
p(X 1 = D)
p(X 1 = E)
⎞
⎟
⎟
⎟
⎟
⎠
=
⎛
⎜
⎜
⎜
⎜
⎝
0
1
2
1
3
1 0
1 0
1
3
0
1
3
0
1
2
0 0
1
3
0 0 0 0
1
3
0 0
1
3
0 0
⎞
⎟
⎟
⎟
⎟
⎠
⎛
⎜
⎜
⎜
⎜
⎝
0
0
1
0
0
⎞
⎟
⎟
⎟
⎟
⎠
=
⎛
⎜
⎜
⎜
⎜
⎝
1
3
1
3
0
0
1
3
⎞
⎟
⎟
⎟
⎟
⎠
comme nous l’avions calcul´ e. De la mˆ eme fa¸ con, le second clic donnera lieu ` a un vecteur
de probabilit´ es p
2 obtenu de p
1 par p
2 = P p
1 :
p
2 =
⎛
⎜
⎜
⎜
⎜
⎝
p(X 2 = A)
p(X 2 = B)
p(X 2 = C)
p(X 2 = D)
p(X 2 = E)
⎞
⎟
⎟
⎟
⎟
⎠
=
⎛
⎜
⎜
⎜
⎜
⎝
0
1
2
1
3
1 0
1 0
1
3
0
1
3
0
1
2
0 0
1
3
0 0 0 0
1
3
0 0
1
3
0 0
⎞
⎟
⎟
⎟
⎟
⎠
⎛
⎜
⎜
⎜
⎜
⎝
1
3
1
3
0
0
1
3
⎞
⎟
⎟
⎟
⎟
⎠
=
⎛
⎜
⎜
⎜
⎜
⎝
1
6
4
9
5
18
1
9
0
⎞
⎟
⎟
⎟
⎟
⎠
.
Le calcul des probabilit´ es apr` es les premier et second clics indiquent comment celles
apr` es le n-i` eme sont obtenues : elles le sont r´ ecursivement par p
n = P p
n−1 , ou encore
directement par
p
n = P p
n−1 = P (P p
n−2 ) = · · · = P P · · · P
n fois
p
0 = P
n p
0 .
Les contraintes (9.2) sur les matrices de transition de P ont des cons´ equences qui
sont vraies pour toutes les chaˆ ınes de Markov et qui sont capitales pour l’algorithme
PageRank.
Pour d´ ecouvrir la premi` ere propri´ et´ e ` a l’´ etude, nous prendrons quelques-unes des
puissances de la matrice P que nous venons d’introduire. Les puissances P
4 , P
8 , P
16 et
P
32 , arrondies ` a trois d´ ecimales pr` es, sont :
P
4 =
⎛
⎜
⎜
⎜
⎜
⎝
0,333 0,296 0,204 0,167 0,420
0,222 0,463 0,531 0,667 0,160
0,389 0,111 0,160 0,000 0,370
0,056 0,000 0,031 0,000 0,019
0,000 0,130 0,074 0,167 0,031
⎞
⎟
⎟
⎟
⎟
⎠
, P
8 =
⎛
⎜
⎜
⎜
⎜
⎝
0,265 0,313 0,294 0,323 0,279
0,420 0,360 0,409 0,372 0,381
0,217 0,233 0,191 0,201 0,252
0,031 0,022 0,018 0,012 0,035
0,067 0,072 0,088 0,092 0,052
⎞
⎟
⎟
⎟
⎟
⎠
,
P
16 =
⎛
⎜
⎜
⎜
⎜
⎝
0,294 0,291 0,293 0,291 0,294
0,388 0,392 0,389 0,391 0,391
0,220 0,219 0,221 0,221 0,218
0,024 0,025 0,025 0,025 0,024
0,074 0,073 0,072 0,072 0,074
⎞
⎟
⎟
⎟
⎟
⎠
, P
32 =
⎛
⎜
⎜
⎜
⎜
⎝
0,293 0,293 0,293 0,293 0,293
0,390 0,390 0,390 0,390 0,390
0,220 0,220 0,220 0,220 0,220
0,024 0,024 0,024 0,024 0,024
0,073 0,073 0,073 0,073 0,073
⎞
⎟
⎟
⎟
⎟
⎠
.