Chapitre 7 — Décomposition fine du PageRank
Je composerai jusqu’à la décomposition
It’s a psychofrakulator. It creates a cloud of radically fluctuating free-deviant chaotrons which penetrate the synaptic relays. It’s concatenated with a synchronous transport switch that creates a virtual tributary. It’s focused onto a biobolic reflector. And what happens is that hallucinations become reality and the brain is literally fried from within.
L'objet de ce chapitre, qui est une extension de [MV03b] et de [MV04], est d’étudier comment le PageRank se comporte en regard de la structure de site présentée lors de la Partie I, Section 3.3. Nous allons montrer qu’il existe une décomposition naturelle du PageRank en deux termes, le PageRank interne et le PageRank externe. Cette décomposition permet de mieux comprendre les rôles joués par les liens internes et externes. Une première application est un algorithme d’estimation du PageRank local à l’intérieur d’un site. Nous allons également montrer quelques résultats quantitatifs sur les possibilités offertes à un site d’augmenter son propre PageRank.
Plus précisément, la Section 7.1 présente sommairement les différentes contributions existantes quant à l’utilisation de la structure en sites du Web pour calculer un PageRank. La Section 7.2 précise quelles seront les hypothèses et conventions utilisées. Les notions de PageRank interne et externe seront introduites lors de la Section 7.3, et appliquées à un algorithme théorique décomposé de PageRank dans la Section 7.4. Enfin, après avoir profité dans la Section 7.5 de l’étude des variations locales du PageRank pour introduire le facteur zap dans notre modélisation, nous donnerons dans la Section 7.6 des algorithmes applicables aux graphes réels.
7.1 Travaux antérieurs et contemporains
Sur l’ensemble des études publiées sur le PageRank, seules quelques unes essaient de prendre avantage de la structure de site. [Kam+03b] donne une méthode pour calculer rapidement une bonne approximation du PageRank à l’aide d’une partition en sites.
Bianchini et al. décomposent le PageRank en liens internes, liens entrants, liens sortants et fuites [BGS02, BGS03]. Cette décomposition permet entre autres d’apporter une certaine compréhension de la manière dont un site peut changer son propre PageRank, tout en donnant des résultats de stabilité du PageRank face à des changements dans la structure en liens internes d’un site.
Enfin, Arasu et al. ont montré qu’un calcul de PageRank sur le graphe quotienté selon les serveurs convergeait plus vite que sur les pages, et encore plus vite en prenant en compte la multiplicité des liens (cf [Ara+01]).
Par rapport à ces travaux, notre approche consiste à utiliser, comme dans [BGS02, BGS03], une décomposition exacte en flots du PageRank, avec des hypothèses plus flexibles sur la distribution de zap. De cette décomposition, nous déduisons un algorithme semi-distribué exact de calcul de PageRank, que nous hybridons avec l’algorithme proposé dans [Kam+03b] afin d’obtenir un algorithme semi-distribué rapide et avec peu d’approximations.
7.2 Hypothèses
Nous avons vu qu’une définition structurelle d’un site pouvait être un ensemble de pages étroitement reliées entre elles par des hyperliens. La structure en blocs de la matrice d’adjacence (cf Figure 3.5 et Figure 3.6) nous permet d’espérer de nombreuses méthodes pour décomposer un graphe du Web en sites, et le Section 3.3, nous en donne une. Pour la suite de ce chapitre, nous supposerons donc que notre graphe du Web est muni d’une partition qui permet de le décomposer en sites, notée , avec .
Dans un premier temps, nous nous placerons dans le cas idéal où le graphe du Web considéré est fortement connexe et apériodique. Nous supposerons également l’absence de lien d’une page vers elle-même.
Comme il a été vu lors de la Section 5.3.1, si l’on considère la matrice définie par
on sait qu’il existe une unique distribution de probabilité, notée , vérifiant
Nous allons chercher à mettre en évidence les liens entre et .
7.3 PageRank interne, PageRank externe
7.3.1 Notations
Pour dans , nous désignons par l’élément de tel que . Nous définissons également comme suit :
Nous appellerons la restriction de aux éléments internes aux composantes de :
Nous avons également besoin de définir le degré interne (resp. degré externe ) d’un sommet comme son degré sortant dans le graphe induit par (resp. induit par ).
Nous sommes maintenant en mesure de définir les notions de PageRank interne et externe, et de les relier au PageRank défini par l’Équation (7.2).
-
Le PageRank entrant interne (resp. PageRank entrant externe ) d’une page de est la probabilité, lorsque le surfeur aléatoire est en régime stationnaire, de venir en à partir d’une page de (resp. à partir d’une page de ). De cette définition sont déduites les Équation (7.5) et Équation (7.6) :
-
Le PageRank sortant interne (resp. PageRank sortant externe ) d’une page de est la probabilité, lorsque le surfeur aléatoire est en régime stationnaire, d’aller de à une page de (resp. à une page de ). L’Équation (7.7) et l’Équation (7.8) formalisent cette définition :
7.3.2 Lois de conservation
On peut définir un PageRank (éventuellement interne, sortant, …) sur un site comme étant la somme des PageRanks de ses pages : . Cette convention étant prise, nous pouvons énoncer les lois de conservation interne et externe d’un site :
Théorème 7.1.
Soit un site. Les PageRanks entrant externe et sortant externe de sont égaux :
Il en est de même des PageRanks entrant interne et sortant interne :
Preuve.
Commençons par prouver la loi de conservation interne (Équation (7.10)) :
Ensuite, les Équation (7.6) et Équation (7.8) nous permettent d’écrire :
L’Équation (7.12) associée à la loi de conservation interne Équation (7.10) nous donne la loi de conservation externe :
□
La loi de conservation externe Équation (7.9) nous montre qu’un site restitue, à travers le PageRank sortant externe, exactement le PageRank qu’il reçoit (le PageRank entrant externe). Comme disait Lavoisier, rien ne se perd, rien ne se crée, tout se transforme. Si l’on considère le flot de PageRank sur le graphe quotient , il y a donc conservation du flot (cf Figure 7.1). Cette remarque est à la base du calcul décomposé du PageRank.
Remarque 7.1.
Une autre façon, peut-être plus simple, de prouver Théorème 7.1 aurait été de considérer directement le PageRank en tant que flot stationnaire. Il est alors évident que le flot sur tout sous-ensemble de est également stationnaire. Nous avons préféré l’approche matricielle car c’est celle que nous continuerons d’utiliser par la suite, même si nous essaierons toujours d’interpréter les résultats en terme de flot quand cela sera possible.
7.4 Décomposition du calcul du PageRank
7.4.1 Relation entre PageRank externe et PageRank
À partir des Équation (7.5) et Équation (7.6), nous pouvons écrire que , et donc que , où est la matrice identité.
Lemme 7.1.
La matrice est inversible.
Preuve.
Il nous suffit de montrer que est sous-irréductible. Cela prouvera que son rayon spectral est strictement inférieur à (Théorème 4.5, Remarque 4.3), et donc que est inversible.
Raisonnons par l’absurde : si n’est pas sous-irréductible, il existe au moins une composante fortement connexe stochastique dans le graphe des transitions associé à . Cette composante est forcément interne à un site puisqu’il n’y a aucun lien externe. Elle existe donc aussi dans , qui ne peut alors être irréductible que si la composante est tout entier, ce qui est impossible (nous avons fait l’hypothèse que était irréductible et que contenait au moins deux sites).
□
Le lemme Lemme 7.1 nous permet alors d’exprimer comme une fonction du PageRank entrant externe :
Pour calculer le PageRank d’un site , il suffit donc de connaître sa structure interne, à travers la matrice , et le PageRank entrant externe qu’il reçoit des autres.
Remarque 7.2.
La matrice , qui est tout comme une matrice diagonale par blocs, peut s’interpréter comme la matrice de transition de tous les chemins internes possibles. En effet, pour , représente la probabilité d’aller de à par un chemin de longueur qui ne suit que des liens internes (en particulier, si .)
7.4.2 Matrice de transition du PageRank externe
Nous voulons formaliser l’intuition d’une propagation du PageRank de site à site donnée par la loi de conservation du PageRank externe (cf Figure 7.1), et trouver une description des relations entre les différentes composantes de . En combinant les Équation (7.6) et Équation (7.14), nous obtenons :
Nous pouvons ainsi définir la matrice de transition du PageRank externe :
Cette matrice possède quelques propriétés très intéressantes :
Lemme 7.2.
La matrice est stochastique.
Preuve.
est de toute évidence positive, il nous suffit donc de montrer que la somme de chaque colonne de vaut . Pour cela, nous commençons par réécrire :
Considérons la somme de la colonne de associée à la page :
Ainsi, la somme de chaque colonne de est nulle, ce qui montre que est stochastique, puisque la somme de chaque colonne vaut .
□
Lemme 7.3.
Soit l’ensemble des pages sans lien entrant externe, et celui des pages possédant au moins un lien entrant externe. Si l’on réordonne les pages selon , alors peut s’écrire
où est une matrice stochastique irréductible.
Preuve.
Les colonnes de correspondant à des pages de sont nulles. Il en est donc de même de celles de , ce qui montre que peut s’écrire sous la forme
est stochastique, puisque l’est. Il reste à montrer qu’elle est irréductible. Considérons deux sommets et de , et un chemin qui mène de à dans . Soit la suite de sommets obtenue en ne conservant dans que les sommets de ( et ). Alors, est un chemin dans le graphe induit par . En effet, entre et , il existe un sous-chemin de constitué d’un chemin interne à , puis d’un saut externe menant à . D’après la définition de , nous avons donc
est donc bien un chemin dans le graphe induit par , ce qui montre que est irréductible.
C.Q.F.D.
□
possède donc un PageRank unique, qui est nul sur 1 et est égal au PageRank de sur . Sous réserve d’apériodicité, il peut être calculé de manière itérative. Seuls les coefficients de sont nécessaires pour calculer ce PageRank. Bien que nous n’ayons pas fait de recherches poussées d’estimation de la taille de , les quelques analyses que nous avons pu effectuer, autant sur des crawls que sur des logs de serveurs (en particulier ceux de l’INRIA) semblent indiquer que l’on peut espérer .
7.4.3 Calcul décomposé théorique du PageRank
À partir de Équation (7.14) et de Équation (7.15), nous pouvons établir une méthode théorique semi-distribuée de calcul du PageRank.
- Chaque site calcule, à partir de son bloc de la matrice des transitions internes , son bloc de la matrice .
- Les différentes lignes de peuvent alors être reconstituées et centralisées.
- Le PageRank externe associé à est alors calculé (il faut ici faire une hypothèse d’apériodicité sur ).
- Chaque site S obtient son propre PageRank , , en appliquant , , à sa matrice .
Lemme 7.4.
Le vecteur ainsi obtenu est homogène au PageRank associé à .
Preuve.
Comme est irréductible, il nous suffit de montrer que est égal à :
C.Q.F.D.
□
7.5 Intermezzo : modifier son propre PageRank
Avant d’attaquer la pièce centrale de ce chapitre, l’algorithme FlowRank, nous voulons montrer que notre décomposition du PageRank permet d’expliquer dans quelle mesure un site peut modifier son propre PageRank, ce qui sera l’occasion d’introduire en douceur le facteur zap dans notre modèle.
Les résultats que nous allons présenter prennent du sens si l’on accepte l’idée qu’un site modifie très difficilement son PageRank externe, alors qu’il en est tout autrement du PageRank interne. De fait, les échanges de PageRank entre sites sont étroitement surveillés par Google, qui n’hésite pas à sanctionner les sites qui échangent des liens dans le seul but d’augmenter leur PageRank externe. De telles usines à PageRank, baptisées farm links ou pouponnières, se voient généralement gratifiées d’un PageRank nul, et se retrouvent donc classées derrière toutes les autres pages2.
7.5.1 Coefficient d’amplification
Considérons un site , son PageRank et son PageRank entrant externe . Nous définissons le coefficient d’amplification de comme le rapport entre PageRank et PageRank entrant externe :
Puisque , dépend seulement de la structure de et de la distribution du PageRank externe sur 3.
La seule connaissance de nous donne une estimation de :
Lemme 7.5.
Un encadrement du coefficient d’amplification est
avec et .
Preuve.
Si l’on considère l’espace vectoriel associé à , pour tout vecteur élémentaire , , nous avons , et donc pour tout vecteur défini sur .
On en déduit la première inégalité de Équation (7.24) :
ainsi que la seconde :
□
La conséquence de Équation (7.24) est que dès que , rien n’empêche un site d’amplifier arbitrairement un PageRank. Dans le cas limite où (site sans lien sortant externe, par exemple un site commercial n’ayant pas envie que l’internaute aille voir ailleurs), on a une amplification infinie et un phénomène de court-circuit. Nous retrouvons le phénomène bien connu du puits de rang (cf [Pag+98]), vu cette fois du point de vue de l’amplification : un ensemble de pages sans lien sortant va absorber et accumuler tout le PageRank externe reçu jusqu’à épuisement du flot.
Heureusement, la sur-amplification est contrôlée par le facteur zap.
7.5.2 Introduction du facteur zap
Nous allons à partir de maintenant quitter le cadre idéal où est fortement connexe et apériodique pour considérer un graphe du Web quelconque. Il nous faut donc en particulier choisir quel modèle de PageRank adopter, et notre choix s’est naturellement porté sur le PageRank non-compensé avec facteur zap. Grâce au Théorème 5.4, nous savons en effet que c’est un modèle strictement équivalent au PageRank -compensé généralement utilisé, à la différence près qu’il permet de travailler avec un flot de zap constant.
est donc maintenant l’unique vecteur vérifiant , étant une distribution recouvrante et le facteur zap.
Nous avons également besoin d’étiqueter le flot de zap. Nous pourrions le répartir en flot externe et interne, selon que le zap nous fasse sortir du site où l’on est ou non, mais nous avons jugé plus judicieux de considérer le flot de zap comme un flot externe dans sa totalité, et de séparer le flot externe en flot externe de clic et flot externe de zap. Nous allons continuer à réserver les termes de PageRank externe entrant et PageRank externe sortant au flot externe de clic, et nous allons par analogie avec l’électricité définir deux nouveaux flots de PageRank liés au zap : le PageRank induit, noté , qui est la probabilité4 de venir sur une page par zap, et le PageRank dissipé, noté , qui est la probabilité5 de quitter une page par zap.
Nous avons maintenant un bestiaire constitué de six PageRanks, ou plutôt de six flots, qui sont récapitulés dans le Tableau 7.1 (rappel : est le défaut stochastique, définit par ).
| flot | entrant | sortant |
| interne | ||
| externe (clic) | ||
| externe (zap) |
On remarquera au passage que .
Les lois de conservation interne et externe sont toujours valables. Nous ne chercherons pas cette fois à le prouver par un calcul matriciel, et nous nous contenterons de les justifier par le fait que l’on est présence d’un flot stationnaire. En particulier, la loi de conservation externe sur un site s’écrit maintenant :
L’équation nous donne un résultat intéressant : si un site possède un PageRank supérieur à , son PageRank sortant externe est inférieur à son PageRank entrant externe, avec égalité si, et seulement si, et . Cela signifie qu’un site ne peut espérer avoir un PageRank supérieur au PageRank par défaut qu’à la condition de donner moins que ce qu’il reçoit.
7.5.3 Zap et coefficient d’amplification
Avec l’introduction du facteur zap, l’Équation (7.14) devient maintenant
L’encadrement vu lors de la Section 7.5.1 est toujours valable en remplaçant par et par le PageRank entrant externe total , et en posant par convention si . On obtient ainsi le Lemme 7.6.
Lemme 7.6.
Le facteur d’amplification défini par vérifie
Preuve.
On procède exactement comme pour la preuve du Lemme 7.5. Si l’on considère un site fixé , et si l’on restreint et à leurs valeurs sur , la première inégalité s’obtient en écrivant
et la deuxième de manière similaire :
□
Valeur numérique
Pour un site réel, il est tout à fait possible d’avoir (site dépourvu de lien interne), ou au contraire (site sans lien externe, et dont toutes les pages possèdent au moins un lien). Ainsi, le coefficient d’amplification peut varier entre (le site ne tire aucun profit du PageRank qu’il reçoit) et (utilisation maximale du PageRank reçu). Comme est une constante universelle qui vaut , on en conclut qu’à PageRank entrant externe total fixé, le PageRank d’un site peut selon sa structure varier avec un facteur . Par exemple un site très mal structuré peut en se restructurant avoir un nouveau PageRank égal à environ 6 fois l’ancien PageRank.
Robustesse du PageRank
Bianchini et al. [BGS02, BGS03] montrent que l’effet que peut produire un site sur le Web est contrôlé par le PageRank de ce site. Plus précisément, si l’on considère un graphe dynamique entre deux instants et , ils ont prouvé que :
Ce résultat peut également se déduire du Lemme 7.6 : si un site change entre et , la plus grande variation relative possible est celle où l’on passe de à . Cette modification de la structure du site, qui correspond à la création d’un puits de rang, ne pouvant se faire qu’au détriment du PageRank externe, et donc du PageRank entrant externe, on a alors forcément , d’où une variation d’au plus . Comme Bianchini et al. travaillent ici dans un modèle compensé (la somme des PageRanks est constante), une variation de dans génère la même variation hors de , ce qui nous donne l’inégalité Équation (7.32).
7.5.4 Amplification d’une page donnée
Pour un site, l’intérêt du PageRank est avant tout d’être visible par les internautes. En particulier, l’administrateur d’un site sera vraisemblablement moins intéressé par un PageRank élevé sur tout son site que par un PageRank très élevé sur quelques pages, voire sur une page. Mieux vaut donc concentrer son PageRank sur une page d’accueil généraliste plutôt que de le répartir entre plusieurs pages spécialisées. Nous allons donc considérer le problème suivant : considérons un site de pages alimenté par un PageRank entrant externe . Comment maximiser le PageRank d’une page donnée ?
La réponse n’est pas difficile une fois que l’on a remarqué que la structure optimale est celle où toutes les pages de autre que pointent vers (et seulement ) et pointe sur au moins une autre page de . récupère ainsi, aux dissipations près, tout le PageRank des autres pages, et récupère son propre PageRank à un facteur près, ce qui est le maximum possible dans un graphe où, rappelons-le, les liens d’une page vers elle-même ne sont pas pris en compte. On a alors
Dans le cas particulier où est la distribution uniforme, on obtient ainsi
avec égalité si, et seulement si, tout le PageRank entrant externe est concentré sur , c’est-à-dire .
On déduit de tout cela quelques stratégies pour améliorer le PageRank d’une page , qui recoupent les recommandations que l’on peut trouver sur de nombreux sites destinés à l’amélioration de son PageRank :
- Demander aux administrateurs d’autres sites de toujours pointer, dans la mesure du possible, sur la page principale plutôt que sur une page spécifique. Éventuellement, mettre des scripts qui redirigent vers la page d’accueil tout accès d’une page extérieure au site7.
- Toujours penser à mettre des liens de retour vers la page d’accueil, et limiter autant que possible la profondeur du site (et donc la dissipation). Dans le cas particulier des sites à frames, mettre des balises
<noframe>à l’intérieur desquelles la structure en étoile est explicitement représentée.
Concluons enfin par quelques remarques valables si est la distribution uniforme :
- Avec la stratégie optimale, un site formé simplement de deux pages qui pointent l’une sur l’autre possède un PageRank qui est au moins égal au PageRank moyen, même si le PageRank entrant externe est nul : .
- Si (par exemple un site qui génère dynamiquement des pages pointant sur , comme un site de consultation d’une base donnée avec des liens autres que des formulaires), le rapport vaut approximativement . Il est donc possible d’augmenter linéairement son PageRank sur . Dans la réalité, ceci est valable à condition que les robots de Google prennent la peine d’explorer toutes les pages8, et que le but de toutes ces pages ne soit pas uniquement d’augmenter son PageRank9.
7.6 Cas réel : FlowRank et BlowRank
L’objectif de cette section est d’adapter le calcul théorique vu lors de la Section 7.4.3 aux situations réelles.
7.6.1 Relations à l’équilibre avec le facteur zap
Maintenant que nous avons eu le temps de nous familiariser avec les flots induits et dissipés, nous pouvons réécrire les équations vues au cours de Section 7.4.
Avec l’introduction du facteur zap, l’Équation (7.14), qui décrit le lien entre PageRank entrant externe et PageRank, devient comme nous l’avons vu
La relation d’équilibre du PageRank externe, équivalent de Équation (7.15), s’obtient quant à elle en fusionnant Équation (7.35) avec la définition de . On obtient ainsi :
Lemme 7.7.
Le rayon spectral de est inférieur à .
Preuve.
La preuve est similaire à celle du Lemme 7.2 : nous montrons en effet que est sous-stochastique (au sens large). Nous allons pour cela montrer que le rayon spectral de est inférieur à . Comme est positive, il suffit, d’après le théorème de Perron-Frobenius, de montrer que pour tout vecteur positif, . Pour cela, nous commençons par réécrire :
Considérons maintenant un vecteur positif. Comme , , et sont tous des vecteurs positifs, on a
Le rayon spectral de étant inférieur à , on a , d’où
C.Q.F.D.
□
Remarque 7.3.
L’inégalité utilisée dans la preuve du Lemme 7.7 est très grossière. Dans la pratique, on peut donc légitimement s’attendre à ce que le rayon spectral de soit plus petit que , et donc que l’Équation (7.36) permette de trouver avec une raison de convergence plus petite que . Les résultats présentés par Arasu et al. (cf [Ara+01]) vont dans ce sens et nous autorisent à espérer une convergence très rapide en pratique.
Application : estimation du PageRank d’un site
Pour l’administrateur d’un site , pouvoir estimer l’importance de ses pages sans faire appel à une aide extérieure ni chaluter le Web indexable peut être d’un intérêt certain. Par exemple, cette importance pourrait être incorporée à un moteur de recherche interne. Or, d’après l’Équation (7.35), il suffit pour cela d’arriver à estimer le PageRank entrant externe sur .
En effet, si on définit la fonction , inspirée de l’Algorithme 5.4, comme une fonction qui renvoie, pour positive de rayon spectral strictement inférieur à et positif, le vecteur vérifiant , alors
Pour estimer ce PageRank entrant externe, deux approches locales sont possibles :
- Nous avons vu que le PageRank est censé, dans une certaine mesure, essayer de représenter le comportement des internautes réels (cf Section 5.2.2). On peut alors prendre, comme estimation du PageRank externe entrant, le nombre de clics réels de l’extérieur du site vers une page du site, mesuré à partir de l’analyse des logs du serveur Web.
- Grâce, ou à cause, du facteur , le classement par degré entrant est une approximation du classement par PageRank (cf Section 5.3.5). En comptant le nombre de références externes associé à chaque page, obtenu là aussi grâce à une analyse des logs du serveur Web, on obtient donc une autre estimation de .
Une fois que l’on a une estimation de , il faut l’équilibrer par rapport à . Une manière, parmi beaucoup d’autres, de réaliser cet équilibrage est de faire une moyenne pondérée des deux vecteurs. On pourra par exemple renvoyer comme estimation normalisée du PageRank sur
On remarquera au passage que la source de rang est alors normalisée à quelque soit l’envergure du site considéré. Comme il s’agit juste d’estimer l’importance relative des pages à l’intérieur de , cela ne pose aucun problème.
7.6.2 Une première approche : FlowRank
Nous avons maintenant toutes les données en main pour construire l’algorithme FlowRank. Constatons tout d’abord que grâce au facteur zap, est complètement défini par l’Équation (7.36), alors que l’Équation (7.15) garantissait seulement d’obtenir un vecteur homogène. Afin d’éviter d’inverser explicitement les matrices , pour , nous allons avoir recours à la fonction définie précédemment. Grâce à cette fonction, toutes les valeurs que nous avons besoin de connaître peuvent être calculées :
- , où est le vecteur valant sur , ailleurs, donne la colonne de associée à . Ce calcul peut se limiter, en entrée comme en sortie, aux pages de . On obtient ainsi la matrice que nous avons précédemment appelée , et que nous continuerons par abus d’écriture à appeler . Notons également que ce calcul peut s’effectuer localement au sein de chaque site .
- vaut quant à lui . Ce calcul peut lui aussi être réparti sur l’ensemble des sites. Notons que est nul en dehors de , nous pouvons donc nous contenter de considérer , restriction de à .
- Une fois calculé et , il est possible de calculer , restriction de à : .
- Le PageRank non-compensé est alors donné par . Encore une fois, cette étape peut se faire à l’échelle d’un site.
Toutes ces opérations sont résumées dans l’Algorithme 7.1.
L’algorithme FlowRank possède de nombreux avantages :
- En fractionnant les calculs de SpeedRank au niveau des sites, on a la possibilité de stocker la matrice en mémoire vive, ce qui permet un calcul extrêmement rapide, d’autant plus rapide que SpeedRank ne fait aucun calcul de norme.
- Mis à part le calcul de , qui est global, tous les autres calculs peuvent être effectués de manière décentralisée à l’échelle des sites. Il est ainsi possible de paralléliser une grande partie des calculs.
- Pour prendre un compte la mise à jour d’un site donné, il n’est pas nécessaire de relancer l’intégralité de l’algorithme (contrairement au cas d’un algorithme totalement centralisé). Il suffit de relancer les calculs de SpeedRank au niveau du site en question, et de réactualiser . Utiliser les précédentes valeurs comme valeurs initiales pour les SpeedRank peut rendre l’opération très rapide.
Mais il a aussi des inconvénients. Ainsi, il faut effectuer calculs de SpeedRank. Même si SpeedRank, comme son nom l’indique, est très rapide, ce nombre reste élevé. De même, le calcul de est un SpeedRank sur une matrice . Si cette matrice ne tient pas en mémoire vive, on perd une grande partie de l’intérêt pratique du calcul décomposé. Pour résoudre ces problèmes, nous allons nous inspirer d’un algorithme concurrent du nôtre, l’algorithme BlockRank.
7.6.3 Algorithme distribué de Kamvar et al. : BlockRank
Parallèlement à nos travaux sur la structure en blocs des graphes du Web [MV02, MV03a] et les applications possibles au PageRank [MV03b, MV04], Kamvar et al. ont fait des recherches très similaires. Dans [Kam+03b], ils utilisent une décomposition en sites pour proposer un algorithme semi-distribué de calcul d’une estimation du PageRank : BlockRank. Cet algorithme est basé sur le calcul d’un PageRank local, qui avec nos notations est le PageRank sur , et d’un PageRank de site, basé sur une matrice sous-stochastique de BlockRank, notée , définie sur le graphe quotient . L’estimation du PageRank d’une page est alors donnée par le produit du PageRank local de par le PageRank de , également appelé BlockRank10. Bien que FlowRank et BlockRank se ressemblent au premier coup d’oeil, il existe d’importantes différences que nous voulons souligner :
- Aux erreurs introduites par près, FlowRank donne le PageRank non-compensé11, et non une approximation. Ainsi, le problème de sous-estimation du PageRank des pages principales rencontré avec l’algorithme BlockRank [Kam+03b] ne se pose pas. Il y a évidemment un prix à payer au niveau de la complexité de l’algorithme.
- La clé de voûte de FlowRank est le PageRank non-compensé, et l’algorithme SpeedRank qui en découle, alors que BlockRank reste sur l’idée du PageRank -compensé, qui est trois fois plus lent sur les « petits » graphes.
- Si le PageRank local dans un site vaut, à normalisation près, , la matrice globale de FlowRank, , et celle de BlockRank, , n’ont quasiment aucun point commun. Par exemple, possède des transitions d’un site vers lui-même. On constatera aussi qu’alors que FlowRank utilise un zap externe adapté à , le PageRank sur utilise un zap uniforme.
7.6.4 Algorithme hybride : BlowRank
Le principal avantage de BlockRank sur FlowRank est ce passage de à rendu possible par les approximations. Ce gain se fait tout autant pour le nombre de calculs locaux que pour la taille de la matrice globale. Nous sommes donc tentés de réduire à une matrice . Pour cela nous devons réduire l’information de flot externe à un scalaire par site , en remplaçant par exemple par . Il nous faut alors définir la façon dont le PageRank entrant externe est injecté à l’intérieur de chaque site. Nous supposerons donc que chaque site est muni d’une distribution de probabilité qui estime la distribution du PageRank entrant externe. Cette distribution, que nous noterons , pourra être la distribution uniforme sur , ou plus finement une distribution sur les pages d’entrée du site, qui sont les plus susceptibles d’être pointées.
Nous pouvons maintenant considérer l’algorithme hybride BlowRank (7.2), qui diffère de FlowRank par une réorganisation imposée du flot externe à l’entrée de chaque site : tout se passe comme si à l’entrée de chaque site, le PageRank entrant externe (par clic) était collecté et redistribué selon .
On obtient ainsi un algorithme qui ne nécessite que appels locaux à , plus un appel global sur une matrice , ce qui le place en terme de performances au même niveau que BlockRank, alors que les approximations faites sont moindres, ce qui permet d’obtenir un PageRank moins perturbé par rapport au modèle global.
- 1Ce résultat est naturel : une page qui n’a pas de lien entrant externe ne peut pas recevoir du PageRank entrant externe.
- 2Notons que cette politique a été l’objet de nombreux procès opposant Google à des sociétés de référencement. En dépit de soupçons quant à l’impartialité de Google quand il s’agit de définir une pouponnière, la société Google n’a jamais été reconnue coupable : un moteur de recherche classe ses résultats comme il l’entend.
- 3Notons que cette distribution peut dans une certaine mesure être influencée par des modifications de la structure de . Mais comme nous l’avons vu, des variations trop importantes peuvent être le signe d’une pouponnière.
- 4Même si le modèle non-compensé fait que l’on ne devrait plus parler de probabilité, nous nous permettrons sporadiquement de continuer à utiliser ce terme, même si il est plus correct de parler de flot.
- 5Voir note de bas de page précédente.
- 6Ce joli chiffre est une preuve supplémentaire de la nécessité d’avoir comme valeur de .
- 7Cette recommandation est à prendre avec précaution : la façon dont Google considère les redirections n’est pas très claire. De plus, cela peut rendre la navigation moins ergonomique pour l’internaute.
- 8À mon grand regret, Google n’a pas encore fini d’explorer la page qui pointe vers toutes les pages (cf Section 1.4 page Section 1.4), ce qui explique que cette dernière n’ait pas encore un PageRank maximal…
- 9Dans le cas contraire, attention à la sanction.
- 10Pour les détails complets, voir [Kam+03b].
- 11Rappelons encore une fois que du point de vue théorique, il n’y a strictement aucune différence entre le PageRank non-compensé et le PageRank -compensé traditionnellement utilisé.