Le BlockRank

Olivier Duffez, Mercredi 19 mars 2003

Cette petite étude est un résumé (et une traduction libre) de l'article Exploiting the Block Structure of the Web for Computing PageRank, écrit par Sepandar D. Kamvar, Taher H. Haveliwala, Christopher D. Manning et Gene H. Golub, publié le 4 mars 2003 sur http://dbpubs.stanford.edu:8090/pub/2003-17. Le texte complet et les figures sont disponibles dans la version PDF téléchargeable ici.

Introduction

Le calcul du PR prend plusieurs jours (le graphe possède plusieurs milliards de noeuds). D'une part accélérer ce calcul est indispensable si l'on souhaite augmenter la fréquence des mises à jour de l'index du moteur. D'autre part les dernières voies d'explorations dans la recherche d'algorithmes plus pertinents requièrent le calcul de nombreuses versions du PageRank.

Environ 79% des liens restent dans le même sous-domaine (host). De même, environ 84% des liens restent dans le même domaine (domain).
Pour analyser la structure des liens, les URL sont classées par ordre lexicographique, sauf que les composants du domaine sont inversés (l'URL www.stanford.edu/home/students/ est traitée comme edu.stanford.www/home/students/
Les pages (noeuds du graphe) sont numérotées selon cet ordre lexicographique modifié.
Ensuite on construit une matrice dont l'élément (i,j) vaut 1 si la page i fait un lien vers la page j, et 0 sinon.

Si on affiche une image de cette matrice, on observe que :

• le web possède une réelle structure en blocs
• les blocs sont bien plus petits que le web en entier
• on distingue nettement des blocs imbriqués correspondants aux domaines, sous-domaines et sous-répertoires.

Les blocs denses correspondent à des groupes de pages fortement inter-connectées.
Les blocs en forme de L correspondent à des groupes de pages peu inter-connectées, où la page à la racine fait un lien vers toutes les autres pages, qui elles-mêmes font également un lien vers cette page à la racine.
Autour de la diagonale, la matrice est assez dense : ceci correspond à une forte interconnection à l'intérieur d'un bloc, surtout dans les petits blocs.

Le calcul de PageRank locaux (par bloc)

L'idée principale de l'algorithme du BlockRank est de calculer des PageRank locaux par blocs et de les regrouper pour former le PageRank global classique. L'algorithme du BlockRank est le suivant :

1. découper le web en blocs selon les domaines
2. calculer le PageRank local de chaque bloc
3. estimer l'importance relative de chaque bloc (notée BlockRank)
4. pondérer le PageRank local de chaque bloc par son BlockRank, et les regrouper pour former une estimation du PageRank global.
5. utiliser l'algorithme classique du PageRank initialisé par le PageRank estimé à l'étape 4

Remarque : l'algorithme classique du PageRank est itératif. Il a pour but de calculer le PageRank de chaque page du web. Quelle que soit la configuration de départ (la valeur initiale de chaque PageRank), l'algorithme convergera. Par contre, le nombre d'itérations (et donc le temps de calcul) dépend de cette configuration de départ. Plus celle-ci est proche de la réalité, plus l'algorithme convergera rapidement.

Pour un bloc donné, l'algorithme du PageRank local converge d'autant plus lentement que les pages du bloc sont fortement interconnectées. Pour accélérer le calcul de l'algorithme du BlockRank, il est donc nécessaire de choisir avec soin les blocs. Par exemple si un bloc correspondant à un sous-domaine est très dense, il peut être découpé en blocs correspondant aux répertoires. Cependant, il est possible de calculer le PageRank local en parallèle, et ce en même temps que l'indexation  !

Les atouts du BlockRank

Les 4 avantages principaux de l'algorithme du BlockRank sont les suivants :

1. L'accélération du calcul vient principalement du fait que le calcul du PageRank local (par bloc) peut être fait en mémoire, et non pas avec de nombreux accès à un disque dur.
2. Le calcul du PageRank local converge très rapidement pour la majorité des blocs. Dans l'algorithme classique, le calcul est ralenti à cause de quelques blocs qui ne convergent pas rapidement; ceux-ci ralentissent le calcul global.
3. Le calcul du PageRank local peut être largement parallélisé. De plus, il peut même être prévu lors de l'indexation de chaque bloc (le calcul peut démarrer dès que tout un sous-domaine a été totalement indexé).
4. Dans certains cas, il est nécessaire de recalculer le PageRank global alors que peu de changements ont eu lieu. Avec l'algorithme du BlockRank, il suffit de recalculer le PageRank local du bloc qui a changé. Par exemple, on peut recalculer le PageRank global en tenant compte des mises à jour fréquentes d'un site d'information, sans avoir à recalculer le PageRank local de tous les autres sites.

Commentaires

Si vous souhaitez réagir à cette étude, rejoignez la discussion sur le BlockRank.

Formation référencement et webmarketing

Vous souhaitez sans doute améliorer votre référencement, avez-vous pensé à suivre une formation spécialisée sur le référencement naturel ? En 2008, plus de 700 entreprises ont assisté à nos différentes sessions, la plupart faisant financer ces journées par la formation professionnelle (OPCA). Orange Labs nous a décerné un taux de satisfaction des participants de 90% (octobre 2008).

Préparés et animés par Olivier Duffez (WebRankInfo) et Fabien Faceries (AgentWebRanking), 2 professionnels reconnus dans la profession, nos modules sur le référencement naturel sont très complets tout en laissant une grande place à l'interactivité pour répondre à toutes les questions des participants.

Pour connaître le plan détaillé de chaque module, le prix, les dates et les lieux, cliquez ici pour consulter le site de Ranking Metrics (organisme de formation agréé).

Lectures recommandées sur ce thème :

Laisser une réponse