288
9 Google et l’algorithme PageRank
cette partie du graphe pourrait contenir des milliers de pages qu’il faut aussi ordonner.
Et on peut imaginer que le promeneur impartial r´ ealisera que sa promenade est devenue
ennuyeuse (F → G → F → G → . . . ) et qu’il voudra visiter une autre partie de la toile.
Les concepteurs de l’algorithme PageRank sugg` erent donc d’ajouter `
a la matrice de
transition P une matrice Q qui repr´ esente le goˆ ut du promeneur. La matrice Q doit ˆ etre
elle-mˆ eme une matrice de transition, et la nouvelle matrice dont le r´ egime stationnaire
sera `
a trouver est
P
= βP + (1 − β)Q,
β ∈ [0, 1].
Notons que la matrice P
est elle-mˆ eme une matrice de transition : les ´ el´ ements de
chacune de ses colonnes ont pour somme 1. (Exercice !) La pond´ eration relative entre
les goˆ uts et humeurs du promeneur (repr´ esent´ es par la matrice Q) et la structure des
liens de la Toile (repr´ esent´ ee par la matrice P ) se fait par un param` etre β entre 0 et
1. Lorsque β = 1, les goˆ uts du promeneur (et donc, Q) sont ignor´ es et les pi` eges de la
toile (comme la paire (F, G) ci-dessus) peuvent le capturer. `
A l’autre extr´ emit´ e, lorsque
β = 0, les choix du promeneur seront maˆ ıtres, il ne visitera que les pages qu’il a choisies,
et l’ordre naturel que les liens de la Toile cr´ eent sera compl` etement ignor´ e.
Mais comment Google peut-il deviner les int´ erˆ ets du promeneur ? Comment peutil choisir la matrice Q ? Dans l’algorithme PageRank, la matrice Q est choisie le plus
« d´ emocratiquement » possible. Elle accorde ` a toutes les pages de la Toile la mˆ eme
probabilit´ e de transition. Si N est le nombre de pages de la Toile, tous les ´ el´ ements de
la matrice Q sont
1
N : q ij =
1
N . Ceci veut dire que, si le promeneur est coinc´ e dans
la paire (F, G) de la toile de la figure 9.4, il a une probabilit´ e
5
7 × (1 − β) d’en sortir
` a chaque clic. Dans leur article original, les inventeurs de PageRank avaient fait leurs
exp´ eriences avec une pond´ eration β = 0,85, for¸ cant le promeneur ` a ignorer les liens de
la page o` u il se trouvait 3 fois sur 20.
C’est cette variation de l’algorithme de la section pr´ ec´ edente, avec la matrice Q
et la pond´ eration β, que les concepteurs ont appel´ ee PageRank. Quelques-unes de ses
propri´ et´ es seront ´ etudi´ ees en exercice.
Depuis que l’algorithme PageRank a ´ et´ e propos´ e par des universitaires, il a ´ et´ e
brevet´ e. Deux des concepteurs, Sergey Brin et Larry Page, alors dans la vingtaine,
ont fond´ e la compagnie Google en 1998. Cette compagnie est maintenant inscrite en
Bourse et g´ en` ere des profits. Il est donc difficile de connaˆ ıtre les am´ eliorations qu’a
subies l’algorithme original, puisqu’elles sont prot´ eg´ ees par les imp´ eratifs commerciaux.
On connaˆ ıt (ou on peut deviner) quelques bribes d’information. PageRank est un des
algorithmes ordonnant les pages trouv´ ees lors d’une recherche, mais il n’est probablement pas le seul. Puisque Google se targue d’avoir catalogu´ e pr` es de dix milliards de
pages, on imagine que le nombre de lignes N est de cet ordre. Pour trouver l’ordre
PageRank des pages de la Toile, il faut donc trouver un vecteur propre d’une matrice
N × N o` u N ≈ 10 000 000 000. Mais r´ esoudre l’´ equation π = P π (ou plutˆ ot π = P
π)
o` u P est une matrice approximativement 10
10
× 10
10 n’est pas une mince tˆ ache. En
fait, selon C. Moler, le fondateur de Matlab, il se pourrait bien que cet exercice soit
parmi les plus gros probl` emes matriciels r´ esolus par ordinateur. (Pour le point sur les
9 Google et l’algorithme PageRank
cette partie du graphe pourrait contenir des milliers de pages qu’il faut aussi ordonner.
Et on peut imaginer que le promeneur impartial r´ ealisera que sa promenade est devenue
ennuyeuse (F → G → F → G → . . . ) et qu’il voudra visiter une autre partie de la toile.
Les concepteurs de l’algorithme PageRank sugg` erent donc d’ajouter `
a la matrice de
transition P une matrice Q qui repr´ esente le goˆ ut du promeneur. La matrice Q doit ˆ etre
elle-mˆ eme une matrice de transition, et la nouvelle matrice dont le r´ egime stationnaire
sera `
a trouver est
P
= βP + (1 − β)Q,
β ∈ [0, 1].
Notons que la matrice P
est elle-mˆ eme une matrice de transition : les ´ el´ ements de
chacune de ses colonnes ont pour somme 1. (Exercice !) La pond´ eration relative entre
les goˆ uts et humeurs du promeneur (repr´ esent´ es par la matrice Q) et la structure des
liens de la Toile (repr´ esent´ ee par la matrice P ) se fait par un param` etre β entre 0 et
1. Lorsque β = 1, les goˆ uts du promeneur (et donc, Q) sont ignor´ es et les pi` eges de la
toile (comme la paire (F, G) ci-dessus) peuvent le capturer. `
A l’autre extr´ emit´ e, lorsque
β = 0, les choix du promeneur seront maˆ ıtres, il ne visitera que les pages qu’il a choisies,
et l’ordre naturel que les liens de la Toile cr´ eent sera compl` etement ignor´ e.
Mais comment Google peut-il deviner les int´ erˆ ets du promeneur ? Comment peutil choisir la matrice Q ? Dans l’algorithme PageRank, la matrice Q est choisie le plus
« d´ emocratiquement » possible. Elle accorde ` a toutes les pages de la Toile la mˆ eme
probabilit´ e de transition. Si N est le nombre de pages de la Toile, tous les ´ el´ ements de
la matrice Q sont
1
N : q ij =
1
N . Ceci veut dire que, si le promeneur est coinc´ e dans
la paire (F, G) de la toile de la figure 9.4, il a une probabilit´ e
5
7 × (1 − β) d’en sortir
` a chaque clic. Dans leur article original, les inventeurs de PageRank avaient fait leurs
exp´ eriences avec une pond´ eration β = 0,85, for¸ cant le promeneur ` a ignorer les liens de
la page o` u il se trouvait 3 fois sur 20.
C’est cette variation de l’algorithme de la section pr´ ec´ edente, avec la matrice Q
et la pond´ eration β, que les concepteurs ont appel´ ee PageRank. Quelques-unes de ses
propri´ et´ es seront ´ etudi´ ees en exercice.
Depuis que l’algorithme PageRank a ´ et´ e propos´ e par des universitaires, il a ´ et´ e
brevet´ e. Deux des concepteurs, Sergey Brin et Larry Page, alors dans la vingtaine,
ont fond´ e la compagnie Google en 1998. Cette compagnie est maintenant inscrite en
Bourse et g´ en` ere des profits. Il est donc difficile de connaˆ ıtre les am´ eliorations qu’a
subies l’algorithme original, puisqu’elles sont prot´ eg´ ees par les imp´ eratifs commerciaux.
On connaˆ ıt (ou on peut deviner) quelques bribes d’information. PageRank est un des
algorithmes ordonnant les pages trouv´ ees lors d’une recherche, mais il n’est probablement pas le seul. Puisque Google se targue d’avoir catalogu´ e pr` es de dix milliards de
pages, on imagine que le nombre de lignes N est de cet ordre. Pour trouver l’ordre
PageRank des pages de la Toile, il faut donc trouver un vecteur propre d’une matrice
N × N o` u N ≈ 10 000 000 000. Mais r´ esoudre l’´ equation π = P π (ou plutˆ ot π = P
π)
o` u P est une matrice approximativement 10
10
× 10
10 n’est pas une mince tˆ ache. En
fait, selon C. Moler, le fondateur de Matlab, il se pourrait bien que cet exercice soit
parmi les plus gros probl` emes matriciels r´ esolus par ordinateur. (Pour le point sur les