9.3 PageRank am´ elior´ e
287
La premi` ere est l’existence de pages qui n’ont aucun lien. L’absence de liens peut
venir du fait que l’outil de d´ epistage de Google n’a pas encore recens´ e les pages vers
lesquelles la page donn´ ee pointe ou, simplement, que cette page ne m` ene effectivement
nulle part. Alors, le promeneur impartial arrivant `
a cette page n’en sortira plus. Une
fa¸ con simple de sortir de cette impasse consiste ` a effacer de la toile T ou du graphe qui
la repr´ esente cette page et tous les liens qui y m` enent. Le r´ egime stationnaire peut alors
ˆ etre calcul´ e. Il est possible, cela fait, de donner ` a une page effac´ ee le rang que lui aurait
donn´ e la page ou les pages (en nombre n) qui pointent vers elle, c’est-` a-dire
n
i=1
1
li r i o` u
l i est le nombre de liens issus de la i-` eme page qui y m` ene et r i son rang. La prochaine
difficult´ e montrera que, en plus d’ˆ etre bancale, cette solution n’est que partielle.
Fig. 9.4. Une toile de sept pages
La seconde difficult´ e ressemble ` a la premi` ere, mais elle n’est pas aussi simple ` a
corriger. Elle est d´ epeinte sur une petite toile de sept pages ` a la figure 9.4. Cette toile est
constitu´ ee des cinq pages de notre premier exemple plus deux autres qui ne seront reli´ ees
` a la toile originale que par un lien partant de D. Nous avons vu `
a la section pr´ ec´ edente
que le promeneur impartial visite rarement la page D de la toile ` a cinq pages. Il y passe
tout de mˆ eme
1
41 de son temps. Qu’arrivera-t-il dans cette nouvelle toile de sept pages ?
`
A chaque visite en D, le promeneur choisira la moiti´ e du temps la page A et l’autre
moiti´ e du temps la page F . S’il choisit cette derni` ere, il ne pourra plus jamais revenir
aux pages A, B, C, D ou E. Il n’est pas surprenant, donc, que le r´ egime stationnaire
pour cette nouvelle toile, c’est-` a-dire son vecteur π, soit π = (0, 0, 0, 0, 0,
1
2 ,
1
2 )
t . En
d’autres termes, la paire F et G « aspire » toute l’importance que devraient avoir les
autres pages ! (Mais attention ! (−1) est aussi une valeur propre si bien que la matrice
P
n ne tend pas, quand n → ∞, vers la matrice dont toutes les colonnes sont π.) Peut-on
solutionner cette difficult´ e comme pr´ ec´ edemment, en effa¸ cant toute la partie du graphe
qui agit comme « aspirateur » ? Ceci n’est pas une tr` es bonne id´ ee, car, dans les cas r´ eels,
287
La premi` ere est l’existence de pages qui n’ont aucun lien. L’absence de liens peut
venir du fait que l’outil de d´ epistage de Google n’a pas encore recens´ e les pages vers
lesquelles la page donn´ ee pointe ou, simplement, que cette page ne m` ene effectivement
nulle part. Alors, le promeneur impartial arrivant `
a cette page n’en sortira plus. Une
fa¸ con simple de sortir de cette impasse consiste ` a effacer de la toile T ou du graphe qui
la repr´ esente cette page et tous les liens qui y m` enent. Le r´ egime stationnaire peut alors
ˆ etre calcul´ e. Il est possible, cela fait, de donner ` a une page effac´ ee le rang que lui aurait
donn´ e la page ou les pages (en nombre n) qui pointent vers elle, c’est-` a-dire
n
i=1
1
li r i o` u
l i est le nombre de liens issus de la i-` eme page qui y m` ene et r i son rang. La prochaine
difficult´ e montrera que, en plus d’ˆ etre bancale, cette solution n’est que partielle.
Fig. 9.4. Une toile de sept pages
La seconde difficult´ e ressemble ` a la premi` ere, mais elle n’est pas aussi simple ` a
corriger. Elle est d´ epeinte sur une petite toile de sept pages ` a la figure 9.4. Cette toile est
constitu´ ee des cinq pages de notre premier exemple plus deux autres qui ne seront reli´ ees
` a la toile originale que par un lien partant de D. Nous avons vu `
a la section pr´ ec´ edente
que le promeneur impartial visite rarement la page D de la toile ` a cinq pages. Il y passe
tout de mˆ eme
1
41 de son temps. Qu’arrivera-t-il dans cette nouvelle toile de sept pages ?
`
A chaque visite en D, le promeneur choisira la moiti´ e du temps la page A et l’autre
moiti´ e du temps la page F . S’il choisit cette derni` ere, il ne pourra plus jamais revenir
aux pages A, B, C, D ou E. Il n’est pas surprenant, donc, que le r´ egime stationnaire
pour cette nouvelle toile, c’est-` a-dire son vecteur π, soit π = (0, 0, 0, 0, 0,
1
2 ,
1
2 )
t . En
d’autres termes, la paire F et G « aspire » toute l’importance que devraient avoir les
autres pages ! (Mais attention ! (−1) est aussi une valeur propre si bien que la matrice
P
n ne tend pas, quand n → ∞, vers la matrice dont toutes les colonnes sont π.) Peut-on
solutionner cette difficult´ e comme pr´ ec´ edemment, en effa¸ cant toute la partie du graphe
qui agit comme « aspirateur » ? Ceci n’est pas une tr` es bonne id´ ee, car, dans les cas r´ eels,