9.4 Le th´ eor` eme de Frobenius
289
moteurs de recherche et particuli` erement sur PageRank, il faut lire [3].) Cette tˆ ache est
probablement faite tous les mois. Quel est l’algorithme utilis´ e ? Par ´ echelonnage de la
matrice (I − P ) ? Ou par it´ eration P
m p
0 pour un certain p
0 comme le sugg` ere la convergence de la propri´ et´ e 9.4 (m´ ethode d’it´ eration) ? Ou par un algorithme restreignant tout
d’abord le calcul `
a des parties de la Toile qui sont fortement connect´ ees par des liens
(m´ ethode d’agr´ egation) ? Et utilise-t-on le vecteur π du mois pr´ ec´ edent ? Il semble que
les m´ ethodes d’it´ eration et d’agr´ egation soient les plus prometteuses. Mais le secret des
am´ eliorations apport´ ees ` a PageRank depuis la fondation de Google ne permet pas de
trancher la question
5 .
L’ordre des ´ ev´ enements (invention de l’algorithme PageRank, diffusion de l’article
original, obtention du brevet, cr´ eation de la compagnie Google, adoption par le grand
public du moteur propos´ e par cette compagnie. . .) a ´ et´ e optimal : d’une part, la communaut´ e scientifique connaˆ ıt les rouages internes du moteur de recherche, et d’autre
part, les fondateurs de Google ont eu quelques mois d’avance pour mettre sur pied leur
compagnie et r´ ecolter les fruits de leur invention. Connaissant l’algorithme de base, les
chercheurs (` a l’exception de ceux de Google, qui travaillent maintenant dans le secret)
peuvent proposer des am´ eliorations `
a l’algorithme pour certaines fins particuli` eres et
en discuter librement, par exemple, comment prendre en compte efficacement les goˆ uts
d’un utilisateur particulier, comment profiter des pages qui sont fortement reli´ ees entre
elles, comment restreindre une recherche ` a un domaine de l’activit´ e humaine, etc.
9.4 Le th´ eor` eme de Frobenius
Pour ´ enoncer et d´ emontrer le th´ eor` eme de Frobenius, nous devons utiliser des matrices dont les ´ el´ ements sont non n´ egatifs
6 . Nous distinguerons trois cas. Si P est une
matrice n × n, alors nous ´ ecrirons
• P ≥ 0 si p ij ≥ 0 pour tout 1 ≤ i, j ≤ n ;
• P > 0 si P ≥ 0 et au moins un des p ij est positif ;
• P 0 si p ij > 0 pour tout 1 ≤ i, j ≤ n.
Nous utiliserons la mˆ eme notation pour les vecteurs x ∈ R
n . Enfin, x ≥ y signifiera
x − y ≥ 0. Ces « in´ egalit´ es » sont sans doute peu famili` eres. En guise de pratique,
voici deux ´ enonc´ es simples les mettant en jeu. Tout d’abord, si P ≥ 0 et x ≥ y, alors
P x ≥ P y ; en effet, puisque (x − y) ≥ 0 et que P ≥ 0, le produit matriciel de P et de
(x − y) ne contiendra que des sommes d’´ el´ ements positifs ou nuls, et les ´ el´ ements du
vecteur P (x − y) seront tous positifs ou nuls, d’o` u P x ≥ P y. Le deuxi` eme ´ enonc´ e est
laiss´ e en exercice : si P 0 et x > y, alors P x P y.
Lorsque P ≥ 0, on d´ efinit un ensemble Λ ⊂ R constitu´ e de tous les nombres r´ eels λ
qui ont la propri´ et´ e suivante. Il existe un vecteur x = (x 1 , x 2 , . . . , x n ) tel que
5 Les recherches des utilisateurs (nous !) sont trait´ ees par une grappe d’environ 22 000 ordinateurs (ce nombre est celui de d´ ecembre 2003) fonctionnant `
a l’aide du syst` eme d’exploitation
Linux. Le d´ elai de r´ eponse d´ epasse rarement une demi-seconde !
6 Rappel : l’expression « non n´ egatif » veut dire « positif ou nul ».
289
moteurs de recherche et particuli` erement sur PageRank, il faut lire [3].) Cette tˆ ache est
probablement faite tous les mois. Quel est l’algorithme utilis´ e ? Par ´ echelonnage de la
matrice (I − P ) ? Ou par it´ eration P
m p
0 pour un certain p
0 comme le sugg` ere la convergence de la propri´ et´ e 9.4 (m´ ethode d’it´ eration) ? Ou par un algorithme restreignant tout
d’abord le calcul `
a des parties de la Toile qui sont fortement connect´ ees par des liens
(m´ ethode d’agr´ egation) ? Et utilise-t-on le vecteur π du mois pr´ ec´ edent ? Il semble que
les m´ ethodes d’it´ eration et d’agr´ egation soient les plus prometteuses. Mais le secret des
am´ eliorations apport´ ees ` a PageRank depuis la fondation de Google ne permet pas de
trancher la question
5 .
L’ordre des ´ ev´ enements (invention de l’algorithme PageRank, diffusion de l’article
original, obtention du brevet, cr´ eation de la compagnie Google, adoption par le grand
public du moteur propos´ e par cette compagnie. . .) a ´ et´ e optimal : d’une part, la communaut´ e scientifique connaˆ ıt les rouages internes du moteur de recherche, et d’autre
part, les fondateurs de Google ont eu quelques mois d’avance pour mettre sur pied leur
compagnie et r´ ecolter les fruits de leur invention. Connaissant l’algorithme de base, les
chercheurs (` a l’exception de ceux de Google, qui travaillent maintenant dans le secret)
peuvent proposer des am´ eliorations `
a l’algorithme pour certaines fins particuli` eres et
en discuter librement, par exemple, comment prendre en compte efficacement les goˆ uts
d’un utilisateur particulier, comment profiter des pages qui sont fortement reli´ ees entre
elles, comment restreindre une recherche ` a un domaine de l’activit´ e humaine, etc.
9.4 Le th´ eor` eme de Frobenius
Pour ´ enoncer et d´ emontrer le th´ eor` eme de Frobenius, nous devons utiliser des matrices dont les ´ el´ ements sont non n´ egatifs
6 . Nous distinguerons trois cas. Si P est une
matrice n × n, alors nous ´ ecrirons
• P ≥ 0 si p ij ≥ 0 pour tout 1 ≤ i, j ≤ n ;
• P > 0 si P ≥ 0 et au moins un des p ij est positif ;
• P 0 si p ij > 0 pour tout 1 ≤ i, j ≤ n.
Nous utiliserons la mˆ eme notation pour les vecteurs x ∈ R
n . Enfin, x ≥ y signifiera
x − y ≥ 0. Ces « in´ egalit´ es » sont sans doute peu famili` eres. En guise de pratique,
voici deux ´ enonc´ es simples les mettant en jeu. Tout d’abord, si P ≥ 0 et x ≥ y, alors
P x ≥ P y ; en effet, puisque (x − y) ≥ 0 et que P ≥ 0, le produit matriciel de P et de
(x − y) ne contiendra que des sommes d’´ el´ ements positifs ou nuls, et les ´ el´ ements du
vecteur P (x − y) seront tous positifs ou nuls, d’o` u P x ≥ P y. Le deuxi` eme ´ enonc´ e est
laiss´ e en exercice : si P 0 et x > y, alors P x P y.
Lorsque P ≥ 0, on d´ efinit un ensemble Λ ⊂ R constitu´ e de tous les nombres r´ eels λ
qui ont la propri´ et´ e suivante. Il existe un vecteur x = (x 1 , x 2 , . . . , x n ) tel que
5 Les recherches des utilisateurs (nous !) sont trait´ ees par une grappe d’environ 22 000 ordinateurs (ce nombre est celui de d´ ecembre 2003) fonctionnant `
a l’aide du syst` eme d’exploitation
Linux. Le d´ elai de r´ eponse d´ epasse rarement une demi-seconde !
6 Rappel : l’expression « non n´ egatif » veut dire « positif ou nul ».