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 :
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 :
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 :
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 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 :
- découper le web en blocs selon les domaines
- calculer le PageRank local de chaque bloc
- estimer l’importance relative de chaque bloc (notée BlockRank)
- pondérer le PageRank local de chaque bloc par son BlockRank, et les regrouper pour former une estimation du PageRank global.
- utiliser l’algorithme classique du PageRank initialisé par le PageRank estimé à l’étape 4
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 :
- 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.
- 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.
- 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é).
- 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.
) on pourrait penser que son installation (et utilisation) va se multiplier chez les utilisateurs.
