Annonces Google

Vous êtes ici : Dossiers référencement > R&D référencement, réseaux sociaux

Le BlockRank

Par , le 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.

Cet article vous a-t-il plu ?
Cliquez pour voter !

A propos de l'auteur : Olivier Duffez Olivier Duffez sur Google+ Olivier Duffez sur Twitter Olivier Duffez sur Facebook Olivier Duffez sur Pinterest Olivier Duffez sur LinkedIn

Consultant en référencement, Olivier Duffez a travaillé pour les plus grands sites (Doctissimo, FNAC,...). Il édite le site WebRankInfo qu'il a créé en 2002, devenu la + grande communauté francophone sur le SEO (+300.000 membres, 1,5 million de posts). Il est aussi cofondateur de Ranking Metrics, leader des formations webmarketing en France (SEO, AdWords, Analytics, réseaux sociaux) et éditrice de la plateforme MyRankingMetrics (crawler et audit SEO en ligne).

Article (Etude du BlockRank, un algorithme de calcul rapide du PageRank) publié par WebRankInfo dans la rubrique R&D référencement, réseaux sociaux. Si vous souhaitez publier un extrait de cet article sur votre site, assurez-vous de respecter les conditions générales d'utilisation de WebRankInfo.

Un commentaire

  • Sun Location a dit le

    Loool, je viens de tomber sur cette très vielle page... Je ne connaissais pas ce BlocRank :)

Postez un commentaire !

Les champs marqués du signe * sont obligatoires. L'adresse email ne sera pas affichée.

En postant un commentaire, vous acceptez les CGU du site WebRankInfo.

Catégories des dossiers

Consultez les dossiers par thématiques :

Annonces Google

Formation référencement et webmarketing

Venez chez Ranking Metrics vous former au référencement, à Google AdWords et Analytics ainsi qu'aux réseaux sociaux ! Plus de 4000 entreprises sont déjà venues (Dossier possible OPCA...).

Préparés et animés par Olivier Duffez (WebRankInfo) et Fabien Faceries (AgentWebRanking), 2 professionnels reconnus dans le domaine, 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, consultez le site de Ranking Metrics (organisme de formation).

Hébergement web

Hébergement web mutualisé et dédié

Pour un bon référencement, il faut un bon hébergeur. Testez Sivit by Nerim, l'hébergeur choisi par Olivier Duffez pour son site WebRankInfo.

A partir de 3€ HT/mois.

Annonces Google