9.2 Toile et chaˆ ınes de Markov
277
9.2 Toile et chaˆ ınes de Markov
La Toile constitu´ ee des milliards de pages
4 et des liens qui les relient peut ˆ etre
repr´ esent´ ee par un graphe orient´ e, c’est-` a-dire une collection de nœuds (les pages) reli´ es
entre eux par des arˆ etes orient´ ees (les liens). Par exemple, la figure 9.2 repr´ esente une
(minuscule) toile qui ne contiendrait que cinq pages (A, B, C, D et E). Les fl` eches
trac´ ees entre ces pages indiquent que
• le seul lien partant de la page A pointe vers la page B ;
• les liens de la page B pointent vers les pages A et C ;
• les liens de la page C pointent vers les pages A, B et E ;
• le seul lien de la page D pointe vers la page A ;
• les liens de la page E pointent vers les pages B, C et D.
Fig. 9.2. Une toile de cinq pages et ses liens
Pour d´ eterminer l’ordre `
a donner ` a chacune de ces cinq pages, nous consid´ ererons un
algorithme PageRank simplifi´ e. Supposons qu’un promeneur impartial (ou un automate)
navigue sur cette toile en cliquant sans biais sur les liens qui lui sont offerts. Lorsqu’il
n’y a qu’un choix (par exemple, quand il se trouve `
a la page D), il cliquera sur le seul
lien qui lui est offert (et donc, sur le lien qui m` ene ` a la page A). S’il se trouve `
a la page
C, il choisira le lien menant ` a la page A le tiers des fois, le lien menant ` a la page B un
autre tiers des fois et, enfin, le lien menant ` a la page E le reste du temps. En d’autres
mots, lorsqu’il est ` a une page donn´ ee (par exemple, la page C), il choisira entre les pages
qui lui sont offertes (les pages A, B et E lorsqu’il est en C) avec ´ egales probabilit´ es. Si ce
promeneur est laiss´ e `
a son jeu, changeant de page une fois `
a la minute, `
a quelle page serat-il dans une heure, dans deux jours, apr` es un nombre tr` es grand de sauts ? Ou, puisque
4 Lorsque Page et ses collaborateurs publi` erent leur algorithme en 1998, ils estimaient ` a
environ 150 millions le nombre de pages et ` a 1,7 milliard le nombre de liens. En 2006, le
nombre de pages ´ etait de l’ordre de la dizaine de milliards.
277
9.2 Toile et chaˆ ınes de Markov
La Toile constitu´ ee des milliards de pages
4 et des liens qui les relient peut ˆ etre
repr´ esent´ ee par un graphe orient´ e, c’est-` a-dire une collection de nœuds (les pages) reli´ es
entre eux par des arˆ etes orient´ ees (les liens). Par exemple, la figure 9.2 repr´ esente une
(minuscule) toile qui ne contiendrait que cinq pages (A, B, C, D et E). Les fl` eches
trac´ ees entre ces pages indiquent que
• le seul lien partant de la page A pointe vers la page B ;
• les liens de la page B pointent vers les pages A et C ;
• les liens de la page C pointent vers les pages A, B et E ;
• le seul lien de la page D pointe vers la page A ;
• les liens de la page E pointent vers les pages B, C et D.
Fig. 9.2. Une toile de cinq pages et ses liens
Pour d´ eterminer l’ordre `
a donner ` a chacune de ces cinq pages, nous consid´ ererons un
algorithme PageRank simplifi´ e. Supposons qu’un promeneur impartial (ou un automate)
navigue sur cette toile en cliquant sans biais sur les liens qui lui sont offerts. Lorsqu’il
n’y a qu’un choix (par exemple, quand il se trouve `
a la page D), il cliquera sur le seul
lien qui lui est offert (et donc, sur le lien qui m` ene ` a la page A). S’il se trouve `
a la page
C, il choisira le lien menant ` a la page A le tiers des fois, le lien menant ` a la page B un
autre tiers des fois et, enfin, le lien menant ` a la page E le reste du temps. En d’autres
mots, lorsqu’il est ` a une page donn´ ee (par exemple, la page C), il choisira entre les pages
qui lui sont offertes (les pages A, B et E lorsqu’il est en C) avec ´ egales probabilit´ es. Si ce
promeneur est laiss´ e `
a son jeu, changeant de page une fois `
a la minute, `
a quelle page serat-il dans une heure, dans deux jours, apr` es un nombre tr` es grand de sauts ? Ou, puisque
4 Lorsque Page et ses collaborateurs publi` erent leur algorithme en 1998, ils estimaient ` a
environ 150 millions le nombre de pages et ` a 1,7 milliard le nombre de liens. En 2006, le
nombre de pages ´ etait de l’ordre de la dizaine de milliards.