290
9 Google et l’algorithme PageRank
Fig. 9.5. Trois points de vue du simplexe auquel appartiennent les vecteurs x = (a, b, c). Le
plan a + b + c = 1 est repr´ esent´ e par un carr´ e blanc, et le simplexe (a, b, c ≥ 0), par le triangle
gris.
1≤j≤n
x j = 1,
x>0
et
P x ≥ λx.
(9.4)
Par exemple, si n = 3, la condition x > 0 positionne le point x = (a, b, c) dans l’octant o` u
toutes les coordonn´ ees des points sont positives ou nulles, et la contrainte a + b + c = 1
est un plan. Sur la figure 9.5, ce plan est d´ enot´ e par un carr´ e blanc. La condition
suppl´ ementaire x > 0 restreint les points (a, b, c) de ce plan au triangle peint en gris.
Ces deux contraintes combin´ ees repr´ esentent donc l’ensemble des points de ce triangle.
Dans le cas de dimension n, l’objet ainsi construit est appel´ e un simplexe. ( `
A quoi
ressemble le simplexe si n = 2 ? Et si n = 4 ? Exercice !) La propri´ et´ e importante de cet
ensemble est qu’il est compact, c’est-` a-dire ferm´ e et born´ e. Pour chacun des points de
ce simplexe, on calcule P x qui, de par l’observation ci-dessus, est P x ≥ 0. Il est donc
possible de trouver λ ≥ 0 tel que P x ≥ λx. (Il peut bien arriver que λ = 0 ; par exemple,
si P = ( 0 1
0 0 ) et x = ( 0
1 ), alors P x = ( 1
0 ) ≥ λ ( 0
1 ), qui ne peut ˆ etre valide que si λ = 0.)
Proposition 9.6 Soit λ 0 = sup λ∈Λ λ. Alors, λ 0 < ∞. De plus, si P 0, alors λ 0 > 0.
Preuve Posons M = max i,j p ij , c’est-` a-dire que M est le plus grand ´ el´ ement de la
matrice P . Alors, pour tout x satisfaisant `
a
j x j = 1 et x > 0, on a
(P x) i =
1≤j≤n
p ij x j ≤
1≤j≤n
M x j = M
pour tout i,
et, puisque au moins une des composantes de x doit ˆ etre ≥
1
n , disons x i , alors P x ≥ λx
implique que M ≥ (P x) i ≥ λx i ≥ λ
1
n . Puisque ceci est vrai pour tout λ ∈ Λ, on a
λ 0 = sup Λ λ ≤ M n. Si maintenant P 0, alors posons m = min ij p ij , c’est-` a-dire
que m est le plus petit ´ el´ ement de la matrice P . Alors, pour x = (
1
n ,
1
n , . . . ,
1
n ), on a
(P x) i =
j p ij
1
n ≥ (mn)
1
n = (mn)x i et donc, P x ≥ (mn)x et λ 0 ≥ mn > 0.
Th´ eor` eme 9.7 (Frobenius) Soient P > 0 et λ 0 tel que d´ efini ci-dessus. Alors,
9 Google et l’algorithme PageRank
Fig. 9.5. Trois points de vue du simplexe auquel appartiennent les vecteurs x = (a, b, c). Le
plan a + b + c = 1 est repr´ esent´ e par un carr´ e blanc, et le simplexe (a, b, c ≥ 0), par le triangle
gris.
1≤j≤n
x j = 1,
x>0
et
P x ≥ λx.
(9.4)
Par exemple, si n = 3, la condition x > 0 positionne le point x = (a, b, c) dans l’octant o` u
toutes les coordonn´ ees des points sont positives ou nulles, et la contrainte a + b + c = 1
est un plan. Sur la figure 9.5, ce plan est d´ enot´ e par un carr´ e blanc. La condition
suppl´ ementaire x > 0 restreint les points (a, b, c) de ce plan au triangle peint en gris.
Ces deux contraintes combin´ ees repr´ esentent donc l’ensemble des points de ce triangle.
Dans le cas de dimension n, l’objet ainsi construit est appel´ e un simplexe. ( `
A quoi
ressemble le simplexe si n = 2 ? Et si n = 4 ? Exercice !) La propri´ et´ e importante de cet
ensemble est qu’il est compact, c’est-` a-dire ferm´ e et born´ e. Pour chacun des points de
ce simplexe, on calcule P x qui, de par l’observation ci-dessus, est P x ≥ 0. Il est donc
possible de trouver λ ≥ 0 tel que P x ≥ λx. (Il peut bien arriver que λ = 0 ; par exemple,
si P = ( 0 1
0 0 ) et x = ( 0
1 ), alors P x = ( 1
0 ) ≥ λ ( 0
1 ), qui ne peut ˆ etre valide que si λ = 0.)
Proposition 9.6 Soit λ 0 = sup λ∈Λ λ. Alors, λ 0 < ∞. De plus, si P 0, alors λ 0 > 0.
Preuve Posons M = max i,j p ij , c’est-` a-dire que M est le plus grand ´ el´ ement de la
matrice P . Alors, pour tout x satisfaisant `
a
j x j = 1 et x > 0, on a
(P x) i =
1≤j≤n
p ij x j ≤
1≤j≤n
M x j = M
pour tout i,
et, puisque au moins une des composantes de x doit ˆ etre ≥
1
n , disons x i , alors P x ≥ λx
implique que M ≥ (P x) i ≥ λx i ≥ λ
1
n . Puisque ceci est vrai pour tout λ ∈ Λ, on a
λ 0 = sup Λ λ ≤ M n. Si maintenant P 0, alors posons m = min ij p ij , c’est-` a-dire
que m est le plus petit ´ el´ ement de la matrice P . Alors, pour x = (
1
n ,
1
n , . . . ,
1
n ), on a
(P x) i =
j p ij
1
n ≥ (mn)
1
n = (mn)x i et donc, P x ≥ (mn)x et λ 0 ≥ mn > 0.
Th´ eor` eme 9.7 (Frobenius) Soient P > 0 et λ 0 tel que d´ efini ci-dessus. Alors,