9
Google
et l’algorithme PageRank
Les trois premi` eres sections de ce chapitre font appel ` a l’alg` ebre lin´ eaire (diagonalisation, valeurs et vecteurs propres) et aux probabilit´ es ´ el´ ementaires (y compris
l’ind´ ependance d’´ ev´ enements et la probabilit´ e conditionnelle). Elles constituent la partie ´ el´ ementaire de ce chapitre, peuvent ˆ etre couvertes en trois heures et donnent une
fort bonne id´ ee de l’algorithme PageRank. La section 9.4 constitue la partie avanc´ ee ;
elle requiert une connaissance de base de l’analyse r´ eelle (point d’accumulation, convergence d’une suite) et peut ˆ etre couverte en une ou deux heures suppl´ ementaires.
9.1 Les moteurs de recherche
Dans le monde num´ erique, les nouveaux besoins sont habituellement rapidement
combl´ es par de nouveaux produits ou de nouveaux algorithmes. Ceux qui utilisent la
grande Toile (World Wide Web) depuis quelques ann´ ees, disons depuis 1998, se rappelleront sans doute avoir utilis´ e les moteurs de recherche propos´ es par les compagnies
AltaVista et Yahoo. Maintenant, ces mˆ emes personnes utilisent probablement le moteur de recherche de la compagnie Google. Parmi les moteurs de recherche tout usage
de la Toile, la supr´ ematie pr´ esente de Google s’est ´ etablie en quelques mois. Google l’a
gagn´ ee grˆ ace ` a un des algorithmes qu’elle utilise pour ordonner les pages trouv´ ees par
son moteur de recherche ; il s’agit de l’algorithme PageRank. Le but du pr´ esent chapitre
est de d´ ecrire cet algorithme et les math´ ematiques sur lesquelles il repose, les chaˆ ınes
de Markov.
L’utilisation d’un moteur de recherche est simple. Quelqu’un, assis `
a un ordinateur
reli´ e ` a la Toile, d´ esire connaˆ ıtre les meilleures sources d’information sur un sujet particulier. Supposons, `
a titre d’exemple, qu’il cherche `
a connaˆ ıtre la quantit´ e de neige que
re¸ coit Montr´ eal annuellement. Il choisit d’interroger le moteur de Google
1 ` a l’aide des
1 L’adresse de la page de Google est www.google.com, ou encore www.google.ca et
www.google.fr.
et l’algorithme PageRank
Les trois premi` eres sections de ce chapitre font appel ` a l’alg` ebre lin´ eaire (diagonalisation, valeurs et vecteurs propres) et aux probabilit´ es ´ el´ ementaires (y compris
l’ind´ ependance d’´ ev´ enements et la probabilit´ e conditionnelle). Elles constituent la partie ´ el´ ementaire de ce chapitre, peuvent ˆ etre couvertes en trois heures et donnent une
fort bonne id´ ee de l’algorithme PageRank. La section 9.4 constitue la partie avanc´ ee ;
elle requiert une connaissance de base de l’analyse r´ eelle (point d’accumulation, convergence d’une suite) et peut ˆ etre couverte en une ou deux heures suppl´ ementaires.
9.1 Les moteurs de recherche
Dans le monde num´ erique, les nouveaux besoins sont habituellement rapidement
combl´ es par de nouveaux produits ou de nouveaux algorithmes. Ceux qui utilisent la
grande Toile (World Wide Web) depuis quelques ann´ ees, disons depuis 1998, se rappelleront sans doute avoir utilis´ e les moteurs de recherche propos´ es par les compagnies
AltaVista et Yahoo. Maintenant, ces mˆ emes personnes utilisent probablement le moteur de recherche de la compagnie Google. Parmi les moteurs de recherche tout usage
de la Toile, la supr´ ematie pr´ esente de Google s’est ´ etablie en quelques mois. Google l’a
gagn´ ee grˆ ace ` a un des algorithmes qu’elle utilise pour ordonner les pages trouv´ ees par
son moteur de recherche ; il s’agit de l’algorithme PageRank. Le but du pr´ esent chapitre
est de d´ ecrire cet algorithme et les math´ ematiques sur lesquelles il repose, les chaˆ ınes
de Markov.
L’utilisation d’un moteur de recherche est simple. Quelqu’un, assis `
a un ordinateur
reli´ e ` a la Toile, d´ esire connaˆ ıtre les meilleures sources d’information sur un sujet particulier. Supposons, `
a titre d’exemple, qu’il cherche `
a connaˆ ıtre la quantit´ e de neige que
re¸ coit Montr´ eal annuellement. Il choisit d’interroger le moteur de Google
1 ` a l’aide des
1 L’adresse de la page de Google est www.google.com, ou encore www.google.ca et
www.google.fr.