294
9 Google et l’algorithme PageRank
Fig. 9.7. Une toile avec deux paires reli´ ees par un seul lien (exercice 5)
tous les ´ el´ ements sont
1
4 . Pour quelle valeur de β le promeneur passera-t-il le tiers
de son temps `
a visiter la paire (C, D) ?
6. a) Donner la matrice de transition repr´ esentant le comportement d’un promeneur
impartial sur la toile repr´ esent´ ee ` a la figure 9.8.
b) Si, au clic n, les probabilit´ es de trouver le promeneur ` a l’une ou l’autre des
quatre pages sont ´ egales (P (X n = A) = P (X n = B) = P (X n = C) = P (X n =
Z) =
1
4 ), quelle est la probabilit´ e de le trouver ` a la page Z au clic n + 1 suivant ?
c) Obtenir le r´ egime stationnaire π. Le promeneur impartial s´ ejournera-t-il plus
souvent en A ou en Z ?
Fig. 9.8. Une toile de quatre pages et ses liens (voir l’exercice 6)
9 Google et l’algorithme PageRank
Fig. 9.7. Une toile avec deux paires reli´ ees par un seul lien (exercice 5)
tous les ´ el´ ements sont
1
4 . Pour quelle valeur de β le promeneur passera-t-il le tiers
de son temps `
a visiter la paire (C, D) ?
6. a) Donner la matrice de transition repr´ esentant le comportement d’un promeneur
impartial sur la toile repr´ esent´ ee ` a la figure 9.8.
b) Si, au clic n, les probabilit´ es de trouver le promeneur ` a l’une ou l’autre des
quatre pages sont ´ egales (P (X n = A) = P (X n = B) = P (X n = C) = P (X n =
Z) =
1
4 ), quelle est la probabilit´ e de le trouver ` a la page Z au clic n + 1 suivant ?
c) Obtenir le r´ egime stationnaire π. Le promeneur impartial s´ ejournera-t-il plus
souvent en A ou en Z ?
Fig. 9.8. Une toile de quatre pages et ses liens (voir l’exercice 6)