9.2 Toile et chaˆ ınes de Markov
285
Les deux expressions doivent ˆ etre ´ egales en vertu de l’associativit´ e de la multiplication
matricielle. Pour i ≥ 2, la valeur propre λ i est diff´ erente de 1, et cette ´ egalit´ e ne peut
avoir lieu que si u
t v i = 0 ou, si nous ´ ecrivons cette relation en coordonn´ ees,
u
t v i =
N
j=1
(v i ) j = 0
o` u (v i ) j repr´ esente la coordonn´ ee j du vecteur v i . Cette relation veut dire que la somme
des composantes de chacun des vecteurs v i , i ≥ 2, est ´ egale `
a z´ ero. Si nous faisons la
somme des composantes de p
0 , nous obtiendrons 1 par hypoth` ese. Or,
1 =
N
j=1
p
0
j =
N
j=1
N
i=1
a i (v i ) j =
N
i=1
a i
N
j=1
(v i ) j = a 1
N
j=1
(v 1 ) j = a 1
N
j=1
π j = a 1 .
(Pour la seconde ´ egalit´ e, nous avons utilis´ e l’expression de p
0 dans la base des vecteurs
propres ; pour la quatri` eme, nous avons utilis´ e le fait que les sommes des composantes
des v i sont toutes nulles sauf celle de v 1 .)
Afin d’obtenir le comportement apr` es plusieurs clics, appliquons la matrice de transition P de fa¸ con r´ ep´ et´ ee (m fois) au vecteur de d´ epart p
0 :
P
m p
0 =
N
j=1
a j P
m v j =
N
j=1
a j λ
m
j v j = a 1 v 1 +
N
j=2
λ
m
j a j v j = π +
N
j=2
λ
m
j a j v j .
Ainsi, le carr´ e de la distance entre les deux vecteurs P
m p
0 et π est
||P
m p
0
− π||
2 = ||
N
j=2
λ
m
j (a j v j )||
2 .
La somme au membre de droite est une somme de vecteurs fix´ es (les a j v j ) dont les
coefficients diminuent exponentiellement comme λ
m
j . (Rappelons que les λ j , j ≥ 2, sont
tous de norme inf´ erieure `
a 1.) Puisque cette somme est finie, elle tend vers z´ ero lorsque
m → ∞. Donc, p
m = P
m p
0
→ π lorsque m → ∞.
Revenons au promeneur impartial. Ce que disent les trois propri´ et´ es, c’est que, s’il
poursuit suffisamment longtemps sa promenade al´ eatoire, il visitera chacune des pages
de la toile avec une probabilit´ e de plus en plus proche du r´ egime stationnaire π de P , et
que ce r´ egime stationnaire est le vecteur propre de valeur propre 1 normalis´ e de fa¸ con
que la somme de ses composantes soit 1.
Nous sommes prˆ ets ` a faire le lien entre le vecteur π et l’ordre PageRank.
D´ efinition 9.5 1. Le rang donn´ e `
a la page i de la Toile par l’algorithme PageRank
(simplifi´ e) est la composante π i correspondant `
a cette page dans le vecteur π.
285
Les deux expressions doivent ˆ etre ´ egales en vertu de l’associativit´ e de la multiplication
matricielle. Pour i ≥ 2, la valeur propre λ i est diff´ erente de 1, et cette ´ egalit´ e ne peut
avoir lieu que si u
t v i = 0 ou, si nous ´ ecrivons cette relation en coordonn´ ees,
u
t v i =
N
j=1
(v i ) j = 0
o` u (v i ) j repr´ esente la coordonn´ ee j du vecteur v i . Cette relation veut dire que la somme
des composantes de chacun des vecteurs v i , i ≥ 2, est ´ egale `
a z´ ero. Si nous faisons la
somme des composantes de p
0 , nous obtiendrons 1 par hypoth` ese. Or,
1 =
N
j=1
p
0
j =
N
j=1
N
i=1
a i (v i ) j =
N
i=1
a i
N
j=1
(v i ) j = a 1
N
j=1
(v 1 ) j = a 1
N
j=1
π j = a 1 .
(Pour la seconde ´ egalit´ e, nous avons utilis´ e l’expression de p
0 dans la base des vecteurs
propres ; pour la quatri` eme, nous avons utilis´ e le fait que les sommes des composantes
des v i sont toutes nulles sauf celle de v 1 .)
Afin d’obtenir le comportement apr` es plusieurs clics, appliquons la matrice de transition P de fa¸ con r´ ep´ et´ ee (m fois) au vecteur de d´ epart p
0 :
P
m p
0 =
N
j=1
a j P
m v j =
N
j=1
a j λ
m
j v j = a 1 v 1 +
N
j=2
λ
m
j a j v j = π +
N
j=2
λ
m
j a j v j .
Ainsi, le carr´ e de la distance entre les deux vecteurs P
m p
0 et π est
||P
m p
0
− π||
2 = ||
N
j=2
λ
m
j (a j v j )||
2 .
La somme au membre de droite est une somme de vecteurs fix´ es (les a j v j ) dont les
coefficients diminuent exponentiellement comme λ
m
j . (Rappelons que les λ j , j ≥ 2, sont
tous de norme inf´ erieure `
a 1.) Puisque cette somme est finie, elle tend vers z´ ero lorsque
m → ∞. Donc, p
m = P
m p
0
→ π lorsque m → ∞.
Revenons au promeneur impartial. Ce que disent les trois propri´ et´ es, c’est que, s’il
poursuit suffisamment longtemps sa promenade al´ eatoire, il visitera chacune des pages
de la toile avec une probabilit´ e de plus en plus proche du r´ egime stationnaire π de P , et
que ce r´ egime stationnaire est le vecteur propre de valeur propre 1 normalis´ e de fa¸ con
que la somme de ses composantes soit 1.
Nous sommes prˆ ets ` a faire le lien entre le vecteur π et l’ordre PageRank.
D´ efinition 9.5 1. Le rang donn´ e `
a la page i de la Toile par l’algorithme PageRank
(simplifi´ e) est la composante π i correspondant `
a cette page dans le vecteur π.