Chapitre 6 — BackRank

– You’ve got to come back with me!
– Where?
– Back to the future.

La vraie nouveauté naît toujours dans le retour aux sources.

Nous venons de voir les principes théoriques généraux qui régissent les différents algorithmes de PageRank. En particulier, il est apparu que le problème de la complétion stochastique et celui de la diffusion du PageRank peuvent, voire doivent, être traités indépendamment. Dans ce chapitre, qui est le prolongement d’une série d’articles co-écrits avec Mohamed Bouklit [BM03, MB04], nous allons étudier une manière d’effectuer la complétion stochastique tout en perfectionnant le modèle du surfeur aléatoire : prendre en compte la possibilité qu’a l’utilisateur de pouvoir à tout instant de sa navigation revenir en arrière grâce à la touche Back de son navigateur¹. Comme nous allons le voir, l’algorithme de PageRank qui résulte de cette modélisation présente de nombreux avantages par rapport aux PageRanks classiques.

6.1 De l’importance de la touche Back

En 1995, Catledge et Pitkow publient une étude dans laquelle il apparaît que la touche Back représente de l’ensemble des actions de navigation recueillies ( des actions étant l’usage d’hyperliens) [CP95]. Une autre étude, par Tauscher et Greenberg, datant de 1997, rend compte de d’hyperliens et de de Back [TG97]. Citons enfin une étude plus récente (2004) de Milic et al. [Mil+04], dont les principaux résultats sont portés dans le Tableau 6.1.

De toutes ces études, il semble émerger un certain recul de l’emploi de la touche Back entre 1995 et 2004, mais selon [CM01], il faut tenir compte des évolutions survenues pendant cet intervalle³, ainsi que de changements dans les protocoles expérimentaux utilisés.

L’autre information intéressante que nous donnent ces chiffres est le fait que dans tous les cas, on constate que l’emploi de la touche Back arrive très largement en deuxième position, derrière l’utilisation des hyperliens qui reste le mode de navigation privilégié. Il faut en particulier retenir que selon toutes les études, pour clics sur un hyperlien, il y a au moins utilisation de la touche Back. Pourtant, l’utilisation de la touche Back n’a pas d’équivalent dans les PageRank(s) « classiques », alors que des modes de navigation quantitativement moins importants comme les URLs tapées à la main et les Bookmarks peuvent être pris en compte dans les algorithmes de calcul à travers le vecteur de zap.

Même si l’on ne sait pas vraiment à ce jour si un modèle plus proche du surfeur réel donne forcément un meilleur PageRank, l’importance de la touche Back dans le comportement des internautes réels nous est apparu comme une motivation suffisante pour étudier les possibilités de l’incorporer dans un nouveau modèle de PageRank.

6.2 Travaux antérieurs et contemporains

Kleinberg, dans l’algorithme HITS [Kle98], utilise aussi la matrice des liens entrants, et travaille donc sur un modèle où remonter les hyperliens est implicitement pris en compte. Néanmoins, le but de l’algorithme HITS n’est pas de modéliser la touche Back mais de voir le graphe du Web comme une superposition de « hubs » et d’« autorités », les premiers pointant vers les secondes.

D’un autre côté, Fagin et al., dans [Fag+00] proposent une étude très complète de l’influence de l’introduction de retours arrières dans une marche aléatoire, et proposent une modélisation stochastique du surfeur aléatoire tenant compte de la touche Back. Dans ce modèle une chaîne de Markov initiale classique est considérée, à laquelle on adjoint un historique de capacité infinie des pages visitées. À chaque page est associée une probabilité de revenir en arrière, à condition que l’historique soit non vide. Les principaux résultats obtenus sont :

• Suivant les probabilités de retour arrière, le processus peut être transitoire (asymptotiquement, la page de départ est « oubliée » et fini par ne plus influer sur la distribution de probabilité) ou ergodique (les retours arrières ramènent le surfeur infiniment souvent sur la page de départ), avec une transition de phase entre les deux.
• Dans le cas particulier où la probabilité de retour ne dépend pas de la page, si , le processus converge vers la même distribution que la chaîne de Markov classique (sans retour possible).
• Les autres cas sont caractérisés, différents types de convergence sont considérés, et les valeurs limites (si elles existent) sont données.

Le principal inconvénient du modèle de Fagin et al. est le coût prohibitif⁴ du calcul des distributions asymptotiques.

Dans [Syd04], Sydow propose de réduire la complexité en limitant la taille de l’historique. Il introduit ainsi un modèle où seule la dernière page visitée est conservée en mémoire (on ne peut pas utiliser deux fois de suite la touche Back), et où la probabilité de Back est uniforme⁵. L’algorithme résultant présente des performances comparables à celles d’un PageRank standard, en termes de vitesse de convergence et de besoin en ressources. Le classement obtenu par la distribution de probabilité asymptotique reste similaire à celui d’un PageRank standard, avec des différences significatives au niveau du classement des pages dominantes.

Par rapport à l’algorithme de Sydow, notre prise en compte de la touche Back présente l’avantage de supprimer de nombreux problèmes liés aux PageRanks classiques (complétion stochastique, effeuillage et remplumage, vitesse de convergence).

6.3 Modélisation de la touche Back

Adoptant une approche similaire à [Syd04]⁶, nous choisissons d’introduire la possibilité de revenir en arrière avec un historique limité. Potentiellement, pour ramener un processus stochastique à mémoire à une chaîne de Markov sans mémoire, on peut être amené à considérer l’ensemble des chemins de longueur dans . Dans le cas où , qui est celui que nous allons étudier, l’espace de travail canonique est l’ensemble des hyperliens. Nous allons introduire deux modèles intuitifs de touche Back pour le cas où , et montrer que pour l’un d’entre eux, il est possible de réduire l’espace de travail de à . Nous verrons également que ce dernier cas est compatible avec l’emploi d’un facteur zap.

6.3.1 Modèle réversible

Dans ce modèle, nous supposons qu’à chaque étape, l’utilisateur peut soit choisir un lien sortant de la page où il se trouve, soit appuyer sur la touche Back, ce qui va le ramener à l’étape précédente. La touche Back est considérée comme un hyperlien comme les autres. En particulier, la probabilité d’utiliser la touche Back est la même que celle de cliquer sur un lien donné, s’il en existe au moins , et vaut en l’absence de lien sortant. Nous pensons que cette approche présente deux avantages par rapport au choix d’une probabilité de retour uniforme fait dans [Syd04] :

• Intuitivement, il semble logique que l’usage de la touche Back dépende du choix disponible sur la page considérée, c’est-à-dire du nombre de liens sortants. Ceci est partiellement confirmé par les comportements observés dans [Mil+04].
• Tout comme la page virtuelle de complétion introduite dans la Section 5.6, la touche Back que nous venons de modéliser assure une échappatoire même dans les pages sans liens, et crée une forme de complétion stochastique.

Précisons enfin que le terme réversible est dû au fait que deux emplois consécutifs de la touche Back s’annulent.

Formellement, le processus stochastique que nous venons d’introduire peut se décrire ainsi : pour chaque , nous définissons comme la probabilité de présence en à l’instant . Nous introduisons également le terme , pour , probabilité d’être passé de à entre les instants et . est non nul dès que ou est dans , et il existe une relation très simple entre et :

où signifie pointé par ou pointant vers . On remarque que l’usage de la touche Back implique de travailler sur le graphe non-orienté induit par .

De la même façon, il est possible d’écrire une équation décrivant les termes : si , pour aller de à entre les instants et , on peut soit suivre le lien qui relie à (il faut pour cela être en à l’instant et choisir parmi les possibilités), soit utiliser la touche Back (il faut alors être allé de à entre les instants et , et choisir parmi les possibilités). Si , mais , alors la transition de à ne peut être effectuée que via l’emploi de la touche Back. Il n’y a pas de transition dans les autres cas. Nous pouvons donc écrire :

Grâce aux Équations (6.1) et (6.2), il est possible de réaliser un processus itératif de calcul de , que l’on pourra par exemple initier par la distribution

Si est le graphe non-orienté induit par , il semble donc nécessaire d’utiliser variables, contre pour le PageRank standard. En injectant Équation (6.1) dans Équation (6.2), il est possible de réduire le nombre de variables à , mais cela reste très important. Ceci nous a amené à considérer le modèle du Back irréversible⁷.

6.3.2 Modèle irréversible

Dans ce nouveau modèle, nous supposons qu’il n’est pas possible d’utiliser la touche Back deux fois d’affilée : celle-ci est grisée après utilisation, et il faut d’abord utiliser au moins une fois un lien réel avant de pouvoir en faire usage à nouveau. Bien que plus complexe en apparence, ce modèle présente des avantages certains sur le modèle réversible :

• Il est plus proche du comportement de la touche Back des navigateurs réels, qui se désactive effectivement lorsque l’historique est épuisé. L’usage d’une touche Back après épuisement de l’historique dans le modèle réversible se rapproche plus de l’usage de la touche Forward dans les navigateurs réels. Or, si l’on en croit [Mil+04] (cf Tableau 6.1), le rôle de la touche Forward reste relativement anecdotique.
• Il est compatible avec l’introduction effective d’un facteur zap (cf Section 6.3.3).
• Le calcul de la distribution asymptotique, même avec un facteur zap, ne nécessite pas plus de ressources que dans le cas d’un PageRank classique (cf Section 6.4.1).
• L’emploi de la touche Back introduit forcément une sorte d’« effet de serre » au niveau des pages sans liens, qui peut s’avérer gênant (effet similaire à celui des composantes fortement connexes récurrentes décrites dans le chapitre précédent). Le modèle irréversible réduit cet effet par rapport au modèle réversible. Considérons l’exemple de la Figure 6.1 : une page possède liens, l’un vers une page sans lien , l’autre vers une page d’échappement d’où tout le graphe est accessible. Si le surfeur aléatoire se retrouve en , il va forcément revenir en par la touche Back. Retourner à nouveau en va alors créer un début d’effet de serre, or le retour en se fait avec une probabilité dans le modèle réversible (2 cas favorables sur 3), contre dans le cas irréversible : la probabilité de rester « coincé » en est plus faible dans le modèle irréversible.

Afin de calculer l’évolution dans un tel modèle, nous allons introduire :

probabilité d’aller de la page à la page entre les instants et à l’aide d’hyperlien.

probabilité d’être arrivé sur la page à l’instant par l’emploi de la touche Back.

Il est possible de décrire en fonction de la situation à l’instant : pour suivre le lien qui va de à , soit on est arrivé à en suivant un lien réel, et il faut choisir parmi possibilités, soit on est arrivé en par la touche Back, ce qui a grisé cette dernière et limite les possibilités à . Nous avons ainsi, pour ,

On remarquera que comme , il n’y a aucune ambiguïté à effectuer une division par . On notera également que le sommet d’arrivée n’intervient en aucune façon dans l’expression de . Si est l’ensemble des pages possédant au moins un lien, et l’ensemble des pages sans lien, on parlera donc à partir de maintenant de , avec , plutôt que de , avec .

De même, pour être arrivé sur une page grâce à la touche Back, il faut précédemment être allé de vers une page pointée par grâce à un hyperlien, puis avoir choisi la touche Back parmi les possibilités. En particulier, on ne peut pas être arrivé sur une page de par la touche Back, et est nul pour . Pour , nous pouvons écrire :

où signifie pointé par .

Si on définit la Back-attractivité d’un sommet appartenant à par

il est alors possible de réécrire les Équations (6.5) et (6.4) comme suit :

En fusionnant l’Équation (6.7) et l’Équation (6.8), on obtient l’Équation (6.9)

Et le PageRank dans tout ça ? La probabilité de présence en une page est la somme de la probabilité d’y être arrivé par la touche Back et de celle d’y être arrivé en suivant un lien. En posant, par convention, pour , on a :

6.3.3 Incorporation du facteur zap

L’ajout de la touche Back irréversible nous garantit un processus stochastique quel que soit le graphe initial, à la seule condition que le support de la distribution initiale ne contienne aucune page sans lien. Le problème des impasses à courte distance, comme la page de la Figure 6.1, est résolu, mais les problèmes d’irréductibilité restent présents. Pire encore, la touche Back transforme les impasses à moyenne et longue distance en puits de rang (cf Figure 6.2).

Il est donc nécessaire d’introduire du zap dans le processus. Nous avons choisi un zap classique, avec un facteur et une distribution . Nous imposons que le fait de « zapper » désactive la touche Back : après un zap, il n’est pas possible de revenir en arrière. Cela présente l’avantage pratique de ne pas avoir à considérer toutes les transitions implicitement générées par le zap, à savoir . On peut aussi interpréter ce choix au niveau de la modélisation du surfeur : selon le Tableau 6.1, beaucoup de zaps réels correspondent en fait au démarrage d’une nouvelle session, et donc à un historique remis à .

Maintenant que le cadre est défini, il est possible de récrire , pour :

De la même façon, nous pouvons récrire la probabilité de se trouver à un instant sur une page avec un historique nul. En posant, par convention, pour , on a :

Et là, un problème se pose : que se passe-t-il si ? Nous allons avoir une probabilité non nulle d’être dans une page de sans retour en arrière possible. Dans cette situation, avec une probabilité , notre surfeur va « zapper » ailleurs, et avec une probabilité … il ne saura pas quoi faire !

Nous envisageons deux méthodes pour contourner ce problème :

• Choisir tel que . Puisque la seule condition que l’on demande à une distribution de zap est d’être recouvrante, c’est tout à fait possible. Une distribution sur les pages d’accueil conviendra, à la condition qu’il n’existe pas de page d’accueil d’un site réduit à une page sans lien. On peut aussi choisir de prendre la distribution uniforme sur définie par

• Compléter le processus stochastique à la volée. On connaît en effet la probabilité de ne pas savoir quoi faire entre les instants et : . Il suffit alors de répartir cette probabilité, par exemple en zap selon . L’équation Équation (6.12) devient alors :

6.4 Algorithme pratique : BackRank

Nous venons de définir un processus stochastique, qui grâce au facteur zap est irréductible et apériodique. Le théorème de Perron-Frobenius s’applique donc⁸ et nous permet d’affirmer que des itérations successives des Équations (6.12) et (6.11) vont converger vers un point fixe unique (à renormalisation près). Les conditions initiales peuvent par exemple être une distribution selon avec un historique nul ( et ).

6.4.1 Optimisation

Nous supposerons ici que nous avons choisi tel que si .

D’après l’Équation (6.12) et l’Équation (6.11), peut se définir récursivement, pour par :

L’Équation (6.15) est une récurrence à deux termes, dont on sait qu’elle converge vers un point fixe. Comme seul le point fixe nous intéresse, on peut remplacer par en gardant une convergence vers le même point fixe (méthode de Gauss-Seidel). On obtient ainsi l’Équation (6.16).

On remarquera au passage que les itérations se font sur les sommets de degré sortant non nul : il y a un effeuillage implicite, semblable à ce qui se pratique pour les PageRanks standards (cf Section 5.4.4.3).

Après que le vecteur a convergé vers un vecteur , il reste à effectuer le « remplumage » pour obtenir la distribution asymptotique de présence :

Nous avons maintenant tous les éléments constitutifs de BackRank (Algorithme 6.1). On remarquera au passage qu’il n’y a pas besoin d’effectuer de renormalisation, puisqu’il y a convergence vers un point fixe.

6.4.2 Résultats

Une fois un algorithme complètement défini, il faut le soumettre à l’épreuve du feu. Afin d’effectuer des comparaisons, il nous fallait un baril de lessive , et c’est le PageRank -compensé défini dans l’Algorithme 5.3 qui a été choisi. C’est en effet le PageRank le plus simple garantissant un contrôle stochastique total, mis à part le PageRank non-compensé bien sûr⁹. La technique d’effeuillage-remplumage a été rajoutée par souci d’équité par rapport à BackRank, qui la réalise implicitement, et aussi afin d’être plus réaliste (c’est la méthode qui semble être employée en pratique pour les calculs off-line sur de très gros graphes, et BackRank est conçu pour supporter de très gros graphes.). Pour les deux algorithmes, nous avons pris (sauf indication contraire) et est la distribution uniforme sur la rafle .

Le test a porté sur un crawl de 8 millions d’URLs qui, pour des raisons techniques¹⁰ est scindé en deux échantillons de millions d’URLs.

Convergence

Un des premiers critères de viabilité d’un algorithme de type PageRank est sa vitesse de convergence. La Figure 6.3 compare, sur une échelle semi-logarithmique, la valeur du paramètre de convergence au bout de itérations. Pour BackRank, la condition est atteinte au bout de itérations dans les deux échantillons, alors que pour PageRank, il faut entre et itérations. Nous avons mesuré la raison de la décroissance géométrique observée à , et trouvé pour le PageRank standard (la convergence est toujours inférieure à , mais tend asymptotiquement vers ) contre pour BackRank. Nous supposons que cet écart, qui explique les performances de BackRank, est du au fait qu’à la différence de PageRank, BackRank utilise implicitement une méthode de Gauss-Seidel partielle. Or, il a été montré que l’utilisation d’une méthode de type Gauss-Seidel améliore considérablement la convergence d’un PageRank [Ara+01].

Nous nous devons de préciser que les algorithmes utilisés sont, aux jeux de réécriture près¹¹, exactement ceux décrits dans cet ouvrage. En particulier, les méthodes de la puissance employées sont vraiment des méthodes de la puissance. Pour une étude plus complète des performances de convergence de BackRank, il faudrait étudier comment il se comporte soumis aux nombreuses méthodes d’accélération de la convergence qui existent [Ara+01, Hav99, Kam+03a].

Pour conclure cette étude de la convergence, précisons que sur les échantillons considérés, une itération de BackRank prend en moyenne secondes contre secondes pour PageRank. Cette différence vient du fait que toutes les constantes de calcul, y compris la matrice d’adjacence, tiennent en mémoire vive. La -compensation a donc un coût non négligeable dans une itération. En fait, même par rapport à un PageRank non-compensé avec estimation de , BackRank ne présente qu’un faible surcoût, de l’ordre de .

Le remplumage

La finalisation du calcul du PageRank, que nous appelons remplumage, est une phase assez peu décrite. Selon [Pag+98], après convergence du PageRank sur le graphe restreint aux sommets de degré sortant non nul, les pages sans lien sont rajoutées au processus, sans affecter les choses de manière significative¹². Mais afin d’attribuer à ces nouvelles pages une importance, il faut bien réaliser au moins une itération de PageRank, ce qui implique de modifier la plupart des constantes. Dans notre essai, nous avons choisi d’effectuer quatre itérations sur le graphe complet après convergence sur le graphe effeuillé. Outre des itérations plus lentes ( secondes, sachant qu’environ des pages des échantillons étaient des pages sans lien), on constate, comme dans la Section 5.4.4.3 page Section 5.4.4.3, la réinitialisation du paramètre (cf Figure 6.3) : au bout de quatre itérations, on est au même niveau qu’après huit itérations de la boucle principale, c’est-à-dire loin d’un état stationnaire…

Pour BackRank, le remplumage est beaucoup moins problématique, puisqu’il se limite à l’application de Équation (6.17) une seule et unique fois. Inutile donc de démarrer une nouvelle série d’itérations. Précisons quand même pour être honnête que puisque se rapporte à et non , les variations sur peuvent être plus grandes que . Expérimentalement, il semble effectivement que lorsque est aux alentours de , les variations au niveau de sont de l’ordre de (légèrement inférieures en fait). Ce résultat reste malgré tout plus qu’acceptable, surtout au regard des variations de générées par le remplumage du PageRank.

Classement

Les performances techniques ne sont que la moitié des critères d’évaluation d’un algorithme de type PageRank. Il faut aussi tester la pertinence du classement par importance induit par la distribution de probabilité obtenue. Une première approche consiste à comparer quantitativement les résultats renvoyés par BackRank et ceux renvoyés par le PageRank de référence. La Figure 6.4 présente une telle comparaison, en donnant le pourcentage de pages communes aux premières pages renvoyées respectivement par BackRank et PageRank. On observe des fluctuations importantes sur les toutes premières pages. Au fur et à mesure que le nombre de pages considérées augmente, le chevauchement se stabilise, pour arriver à une valeur relativement stable de lorsque le nombre de pages considérées s’approche de de la taille de l’échantillon ( pages). Ceci tend à prouver que BackRank offre des résultats assez proches de ceux renvoyés par PageRank, avec quelques spécificités.

Ce chevauchement à stabilisé valant pour les deux échantillons nous a intrigués. En étudiant le phénomène de plus près, nous avons remarqué que le taux de chevauchement à est une variable qui ne dépend que de (sur nos échantillons en tout cas). La Figure 6.5 montre ce lien entre et chevauchement à pour . On remarquera en particulier que :

• Le chevauchement est une fonction décroissante de . On retrouve l’idée, évoquée dans la Section 5.3.5, du rôle lisseur du facteur zap.
• En particulier, le chevauchement tend vers lorsque tend vers , ce qui signifie que BackRank tend, tout comme PageRank, vers la distribution par degré entrant (cf Section 5.3.5).
• Le chevauchement tend vers lorsque tend vers , ce qui semble indiquer que BackRank est intrinsèquement à moitié différent (ou à moitié semblable ?) du PageRank standard. Il ne faut cependant pas oublier que lorsque , le classement est sclérosé par les puits de rang et n’a plus forcément de sens. Vérification sur quelques URLs faite, ce chevauchement de veut en effet seulement dire que BackRank ne se fait pas piéger sur exactement les même puits que PageRank.

Nous sommes conscients de ne donner ici quelques indices de la qualité du classement par BackRank. En toute rigueur, une validation complète nécessiterait d’incorporer BackRank dans un moteur de recherche et d’effectuer une série de tests de satisfaction sur une population témoin. À défaut, nous nous contenterons d’utiliser le lecteur comme population témoin, qui pourra comparer dans les listes Liste 6.1, Liste 6.2, Liste 6.3 et Liste 6.4 les 10 premières pages renvoyées par BackRank et PageRank sur les deux échantillons considérés. On remarquera par exemple que la page principale du CNRS est classé par BackRank, mais pas par PageRank (en fait, elle est 16^ème), alors que pour l’Éducation Nationale, c’est l’inverse (page classée également 16^ème, mais par BackRank cette fois).

http://messagerie.business-village.fr:80/svc/jpro/search
http://server.moselle.cci.fr:80/Fichier/index.html
http://messagerie.business-village.fr:80/svc/jpro/aide
http://backstage.vitaminic.fr:80/add_artist.shtml
http://backstage.vitaminic.fr:80/
http://vosdroits.service-public.fr:80/Index/IndexA.html
http://emploi.cv.free.fr:80/index.htm
http://server.moselle.cci.fr:80/Fichier/listenaf.html
http://ec.grita.fr:80/isroot/fruitine/blank.html
http://www.adobe.fr:80/products/acrobat/readstep.html

http://backstage.vitaminic.fr:80/
http://backstage.vitaminic.fr:80/add_artist.shtml
http://forums.grolier.fr:8002/assemblee/nonmembers/
http://server.moselle.cci.fr:80/Fichier/listenaf.html
http://server.moselle.cci.fr:80/Fichier/index.html
http://messagerie.business-village.fr:80/svc/jpro/search
http://www.adobe.fr:80/products/acrobat/readstep.html
http://mac-texier.ircam.fr:80/index.html
http://mac-texier.ircam.fr:80/mail.html
http://bioscience.igh.cnrs.fr:80//current/currissu.htm

http://www.fcga.fr:80/
http://www.moselle.cci.fr:80/Fichier/index.html
http://www.lhotellerie.fr:80/Menu.htm
http://www.ima.uco.fr:80/
http://www.info-europe.fr:80/europe.web/document.dir/actu.dir/
http://www.moselle.cci.fr:80/Fichier/listenaf.html
http://www.machpro.fr:80/sofetec.htm
http://www.cnrs.fr:80/
http://www.quartet.fr:80/ce/
http://www.gaf.tm.fr:80/espace-pro.htm

http://www.moselle.cci.fr:80/Fichier/index.html
http://www.moselle.cci.fr:80/Fichier/listenaf.html
http://www.lhotellerie.fr:80/Menu.htm
http://www.machpro.fr:80/sofetec.htm
http://www.education.gouv.fr:80/default.htm
http://www.infini.fr:80/cgi-bin/lwgate.cgi
http://www.proto.education.gouv.fr:80/cgi-bin/ELLIB/Lire/Q1
http://www.dma.utc.fr:80/~ldebraux/Genealogie/Whole_File_Report.html
http://www.ldlc.fr:80/
http://www.ldlc.fr:80/contact.shtml