286
9 Google et l’algorithme PageRank
2. On ordonne les pages i selon la grandeur de leur rang. La page i a l’ordre j si j − 1
pages ont un rang plus grand que π i .
L’exemple initial de la petite toile ` a cinq pages (figure 9.2) permet de comprendre ce
rang. Les valeurs propres de la matrice P donn´ ee en (9.3) ont comme norme les valeurs
1, 0,70228, 0,70228, 0,33563, 0,33563, et seule la valeur propre 1 est un nombre r´ eel.
Un vecteur propre associ´ e ` a cette valeur 1 est (12, 16, 9, 1, 3), ce qui donne, si on divise
par la somme des composantes,
π =
1
41
⎛
⎜
⎜
⎜
⎜
⎝
12
16
9
1
3
⎞
⎟
⎟
⎟
⎟
⎠
.
Ceci veut dire que, durant une promenade infiniment longue, c’est la page B que le
promeneur impartial visitera le plus souvent, en fait 16 fois sur 41 en moyenne, et il
ignorera presque la page D, la visitant une seule fois sur 41 en moyenne.
Quel est l’ordre de chaque page ? La page B obtient l’ordre 1, ce qui traduit qu’elle
est la plus importante. La page A a l’ordre 2, la page C, l’ordre 3, la page E, l’ordre 4,
et finalement, la page D, l’ordre 5. Cette derni` ere est donc la moins importante.
Quant au rang, voici une autre fa¸ con de le comprendre : chacune des pages redonne son rang aux pages vers lesquelles elle pointe. Revenons au vecteur π =
(
12
41 ,
16
41 ,
9
41 ,
1
41 ,
3
41 ). La page D ne re¸ coit un lien que de la page E. Puisque le rang
de E est
3
41 et qu’il doit ˆ etre divis´ e entre les trois pages vers lesquelles E pointe, la page
D doit avoir un rang trois fois moindre, soit
1
41 . Trois pages pointent vers la page B ; ce
sont les pages A, C et E. Ces trois pages ont un rang respectif de
12
41 ,
9
41 et
3
41 . Or, A
pointe vers une seule page, C et E vers trois chacune. Le rang de B est donc
rang (B) = 1 ·
12
41
+
1
3
·
9
41
+
1
3
·
3
41
=
16
41
.
Pourquoi l’ordre choisi par le promeneur impartial donne-t-il un ordre raisonnable aux
milliards de pages de la Toile ? Avant tout parce qu’il laisse les utilisateurs d´ ecider de
ce qui est important. Et il ignore ce que le cr´ eateur d’une page en particulier pense de
l’importance de sa page. De plus, l’effet est cumulatif. Une page importante qui pointe
vers peu de pages transmettra ` a ces derni` eres son rang important. Ainsi, les utilisateurs
mettent leur confiance en certaines pages, et ces pages transmettent cette confiance aux
pages vers lesquelles elles pointent, un ph´ enom` ene que les inventeurs nomment « the
collaborative trust ».
9.3 PageRank am´ elior´ e
L’algorithme d´ ecrit ` a la section pr´ ec´ edente n’est pas utilisable tel quel. Deux difficult´ es assez ´ evidentes doivent ˆ etre corrig´ ees.
9 Google et l’algorithme PageRank
2. On ordonne les pages i selon la grandeur de leur rang. La page i a l’ordre j si j − 1
pages ont un rang plus grand que π i .
L’exemple initial de la petite toile ` a cinq pages (figure 9.2) permet de comprendre ce
rang. Les valeurs propres de la matrice P donn´ ee en (9.3) ont comme norme les valeurs
1, 0,70228, 0,70228, 0,33563, 0,33563, et seule la valeur propre 1 est un nombre r´ eel.
Un vecteur propre associ´ e ` a cette valeur 1 est (12, 16, 9, 1, 3), ce qui donne, si on divise
par la somme des composantes,
π =
1
41
⎛
⎜
⎜
⎜
⎜
⎝
12
16
9
1
3
⎞
⎟
⎟
⎟
⎟
⎠
.
Ceci veut dire que, durant une promenade infiniment longue, c’est la page B que le
promeneur impartial visitera le plus souvent, en fait 16 fois sur 41 en moyenne, et il
ignorera presque la page D, la visitant une seule fois sur 41 en moyenne.
Quel est l’ordre de chaque page ? La page B obtient l’ordre 1, ce qui traduit qu’elle
est la plus importante. La page A a l’ordre 2, la page C, l’ordre 3, la page E, l’ordre 4,
et finalement, la page D, l’ordre 5. Cette derni` ere est donc la moins importante.
Quant au rang, voici une autre fa¸ con de le comprendre : chacune des pages redonne son rang aux pages vers lesquelles elle pointe. Revenons au vecteur π =
(
12
41 ,
16
41 ,
9
41 ,
1
41 ,
3
41 ). La page D ne re¸ coit un lien que de la page E. Puisque le rang
de E est
3
41 et qu’il doit ˆ etre divis´ e entre les trois pages vers lesquelles E pointe, la page
D doit avoir un rang trois fois moindre, soit
1
41 . Trois pages pointent vers la page B ; ce
sont les pages A, C et E. Ces trois pages ont un rang respectif de
12
41 ,
9
41 et
3
41 . Or, A
pointe vers une seule page, C et E vers trois chacune. Le rang de B est donc
rang (B) = 1 ·
12
41
+
1
3
·
9
41
+
1
3
·
3
41
=
16
41
.
Pourquoi l’ordre choisi par le promeneur impartial donne-t-il un ordre raisonnable aux
milliards de pages de la Toile ? Avant tout parce qu’il laisse les utilisateurs d´ ecider de
ce qui est important. Et il ignore ce que le cr´ eateur d’une page en particulier pense de
l’importance de sa page. De plus, l’effet est cumulatif. Une page importante qui pointe
vers peu de pages transmettra ` a ces derni` eres son rang important. Ainsi, les utilisateurs
mettent leur confiance en certaines pages, et ces pages transmettent cette confiance aux
pages vers lesquelles elles pointent, un ph´ enom` ene que les inventeurs nomment « the
collaborative trust ».
9.3 PageRank am´ elior´ e
L’algorithme d´ ecrit ` a la section pr´ ec´ edente n’est pas utilisable tel quel. Deux difficult´ es assez ´ evidentes doivent ˆ etre corrig´ ees.