BlockRank

Olivier Duffez (admin)
Membre du personnel
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.
 
WRInaute discret
cette etude, c'est basé sur quoi ?
ce sont des suppositions ou vraiment la methode de travail de GG ?
 
WRInaute passionné
Salut,

Si j'ai bien pigé, c'est basé sur le fait que le PR est linéaire?
Et que
PR total=PR (SIGMA tous les sites) = SIGMA PR (Site individuel)

Si c'est mis en place, cela signifie quäon aura moins de changement brusque et plus de petits ajustements progressif permettant donc au webamster de réagir plus rapidement sans avoir à attendre un ou deux mois. Donc c'est intéressant.

Le principal probleme est sans doute de définir les blocs, i.e. d'identifier les blocs ayant le moins de connection entre eux.

François
 
Olivier Duffez (admin)
Membre du personnel
cette étude a été réalisée en dehors de Google. Peut-être que Google utilise déjà des techniques similaires, sinon ils pourraient s'y intéresser.
attention cette méthode n'a pas pour but de calculer un autre PageRank qui serait une estimation du véritable PageRank, mais obtenue plus rapidement. Elle a pour but de fournir une méthode plus rapide pour calculer le véritable PageRank.

en résumé : le PR est un calcul itératif. Selon les conditions initiales, la convergence sera + ou - rapide. Le BlockRank permet de trouver rapidement des conditions initiales qui permettent d'accélérer la convergence.

avec des études comme celle-là, Google arrivera peut-être un jour à calculer le PR plusieurs fois par mois... voire à chaque requête !!!

Un autre intérêt est le calcul de PR personnalisés... j'en parlerai un peu + d'ici peu...
 
WRInaute discret
Très intéressant et comme cela vient de l'université qui a conçu Google, cela a encore plus de poids...

Une remarque : la vraie difficulté est de créer les blocs. Dans ce cas, Google peut calculer le pr en fonction du degré de cohérence des liens inter et intra block.

Par exemple, un site sur l'immobilier (disons dans le bloc immobilier ou commerce) et qui possède des liens qui pointent sur lui du bloc musique, on peut penser que ceux-ci n'auront que peu de poids.

Il faut alors avoir des liens intra bloc qui compteront bien plus...

Un moyen de lutter contre l es Link Farms en fait...
 
Olivier Duffez (admin)
Membre du personnel
pour l'instant ils envisagent 1 bloc = 1 "host" (cad un sous-domaine dans leur dénomination, ou un domaine dans la plupart des cas)
 
WRInaute discret
Merci de la précision, je n'avais pas compris cela... Mon post est à ressortir dans 5 ans alors, c'est de la SF pour le moment... :lol:
 
WRInaute impliqué
WebRankInfo a dit:
pour l'instant ils envisagent 1 bloc = 1 "host" (cad un sous-domaine dans leur dénomination, ou un domaine dans la plupart des cas)

Les bloc dont vous parlez, exprime d'une autre maniere, est-ce que ca voudrait dire que, pour reprendre l'exemple deja choisis que : "ca" va former des clans comme celui des sites immobiliers ? Ce clan ne connaitra rien, ne liera pas, n'aura rien a voir avec le clan des sites des planteurs de choux (pas auvergnats :wink: ) ?

Je veux dire : irait-on vers une separation dans les familles frequentant le web, les uns refusant de cotoyer les autres ? Ce qui, a mon sens, serait contraire a l'esprit des pionniers d'Internet...

Ma question est peut-etre due a une lecture erronnee des posts precedents ? Par exemple, le machin sigma ; ca mange quoi ce truc ? 8O
 
Olivier Duffez (admin)
Membre du personnel
ça n'a aucun impact sur les webmasters ou les internautes, c'est complètement transparent !!! c'est juste une technique de calcul...
 
WRInaute impliqué
WebRankInfo a dit:
ça n'a aucun impact sur les webmasters ou les internautes, c'est complètement transparent !!! c'est juste une technique de calcul...

Certainement, je crois que j'avais compris cela. Et, en meme temps, c'est interessant a connaitre, donc, de chercher a comprendre !
 
WRInaute accro
Benoist a dit:
Une remarque : la vraie difficulté est de créer les blocs. Dans ce cas, Google peut calculer le pr en fonction du degré de cohérence des liens inter et intra block.

une application typique de l'intelligence artificielle.
doit etre "chiadé" l'algo ! :twisted:
 
WRInaute impliqué
Non, détrompe toi. C'est juste du calcul matriciel, appliqué à des matrices de tailles respectables...

Derrière il y'a juste des maths très simples...
 
WRInaute impliqué
WebRankInfo a dit:
pour l'instant ils envisagent 1 bloc = 1 "host" (cad un sous-domaine dans leur dénomination, ou un domaine dans la plupart des cas)

WRI l'avait expliqué un peu plus haut. Un bloc = mondomaine.com ou sousdomaine.mondomaine.com

On peut aussi définir des blocs plus vastes si on identifie plusieurs domaines très liés entre eux... Mais c'est moins facile à généraliser.
 
F
ffaucouneau
Guest
Etrange comme théorie...

J'avais pensé que GG était plus axé sur des techniques de sémantique pure : 'LSA' ou 'Scatter/Gather'.... techniques qui s'appliquent plus facilement à Gg que ce systeme de blockrank...

Enfin,

Je dois me tromper.
 
Olivier Duffez (admin)
Membre du personnel
Petit résumé pour ceux qui prennent le train en marche :
1) l'algorithme de calcul du PageRank est très complexe. Il consiste théoriquement à faire des calculs matriciels sur des matrices contenant des milliards d'éléments... Autant dire que ça ne se calcule pas comme les matrices 3x3 !

2) ce calcul doit etre fait le plus souvent par Google afin de garantir des résultats toujours pertinents (en + bien sûr d'indexer régulièrement tout le web). a priori son résultat est publié à chaque Google Dance

3) une nouvelle méthode de calcul d'un PageRank approché (mais très proche...) a été mise au point : le BlockRank. il permet de calculer bcp + vite le PR de chaque page indexée dans Google

4) la base du BlockRank est que le PR d'une page A dépend surtout d'un grand nb de pages, et très peu d'un petit nombre. Ce grand nombre, ce sont les pages proches de la page A : les pages appartenant au meme bloc. L'idée est donc de calculer d'abord un BlockRank, c'est à dire un PageRank attribué à un bloc de pages.
Ensuite pour calculer le PR, on se basera seulement sur :
- le BlockRank des blocs des pages liantes situées "loin" de A (bloc différent)
- le PageRank des pages liantes situées proches de A (dans le meme bloc)
Cela réduit considérablement le nb de calculs.

J'espère que mes explications auront éclairé ceux qui ne comprenaient pas grand chose :roll:
 
WRInaute impliqué
J'avais pensé que GG était plus axé sur des techniques de sémantique pure : 'LSA' ou 'Scatter/Gather'.... techniques qui s'appliquent plus facilement à Gg que ce systeme de blockrank...

Non, le blockrank ne sert qu'au calcul du Pagerank, qui n'est que l'un des critères utilisés pour calculer l'ordre des résultats dans les pages de résultats.

Donc, cela n'empêche pas que Google s'intéresse à d'autres techniques...

Chaque nouvelle technique a pour objet, soit d'améliorer la pertinence des résultats, soit d'accélérer les mises à jour. Le Block Rank, c'est pour accélérer la mise à jour des PR.

Les objectifs sont différents.
 
WRInaute impliqué
mahefarivony a dit:
oui mais la question: "quels sont les blocs (ou clans) ?" reste entiere !

ou bien il n'y en a pas tant que cela ?

D'une part. D'autre part, avec tous ces changements, ne sommes-nous pas en droit de nous demander si le nouveau traitement des backlinks et celui du pr par Google ne deviendrait pas de moins en moins credible ? Si, a plus ou moins long terme, donc, consequence, le moteur ne va pas y perdre ?

Ou nous contenterons-nous de devenir aussi cynique que Google : tu nous apportes des visiteurs ; le reste, tes statistiques tronques, on s'en fout.
 
WRInaute accro
non non, je suis pas d'accord ! tout ce dont on parle ce sont des "préoccupations" de webmasters ! Les 100 millions d'utilisateurs mensuels eux s'en fichent completement de tout ces "PR" et autres "blockranks".. ce qui les interesse c'est d'avoir des resultats pertinents et ils les ont !
 
WRInaute impliqué
mahefarivony a dit:
non non, je suis pas d'accord ! tout ce dont on parle ce sont des "préoccupations" de webmasters ! Les 100 millions d'utilisateurs mensuels eux s'en fichent completement de tout ces "PR" et autres "blockranks".. ce qui les interesse c'est d'avoir des resultats pertinents et ils les ont !

Zut, encore une fois le vocabulaire n'est pas le meme alors que je voulais signifier la meme chose que toi !...

Je ne voulais pas le dire, ici, aussi durement que toi ; mais l'idee etait bien la : on se fout du pr, seuls les visiteurs comptent.

Ceci etant dit et pour rester honnete, je dois avouer que c'est dur de se desintoxiquer de la toolbar :wink: :D
 
WRInaute accro
moi dur ? mais non, un peu direct sans plus ;-)

ceci étant, vu que la pub pour la toolbar est en premiere page de google (avec blocage de popup GRATUIT s'il vous plait :) ) on pourrait penser que son installation (et utilisation) va se multiplier chez les utilisateurs.
 
WRInaute impliqué
mahefarivony a dit:
moi dur ? mais non, un peu direct sans plus ;-)

ceci étant, vu que la pub pour la toolbar est en premiere page de google (avec blocage de popup GRATUIT s'il vous plait :) ) on pourrait penser que son installation (et utilisation) va se multiplier chez les utilisateurs.

Allez, j'assume et n'envoie pas la question par MP...

Euh : tu parles d'une nouvelle version de la toolbar ? Meme en faisant "options de la barre d'outils (deja : que toolbar reprenne le nom de barre d'outils, c'est tendancieux...), je n'ai pas trouver le reglage contre les popup... :oops:
 
WRInaute impliqué
mahefarivony a dit:
version francaise sortie il y a 2-3 jours que tu trouveras en page d'accueil de google.fr

Merci pour l'adresse ! Google en fait la pub en ce moment, mais je n' avais pas prete attention vu que j'ai deja une toolbar...

Ne l'ayant pas installee (la nouvelle), je n'ai pas vu les options offertes ; mais, en effet, il y a ce "truc" anti popup... Je ne vois plus la categorie DMOZ (peut-etre dans les options ?)

mahefarivony : tu as un avis sur cette nouvelle version ; ca vaut la peine de changer de toolbar ?
 
WRInaute occasionnel
MagiX a dit:
mahefarivony : tu as un avis sur cette nouvelle version ; ca vaut la peine de changer de toolbar ?
Je propose que l'on reste sur le BlockRank ici et que vous continuiez votre discussion sur Barre d'outils Google v2.0.102 en francais

Personne ne c'est exprimé sur le "Personnalised PageRank", c'est à mon sens un des points les plus important du document, le reste n'étant qu'une accélération de l'algorithme du PR.

Mirgolth
 
WRInaute discret
WebRankInfo a dit:
ça n'a aucun impact sur les webmasters ou les internautes, c'est complètement transparent !!! c'est juste une technique de calcul...

Une technique de calcul du plus grand moteur de recherche (même si l'on est pas sûr qu'ils l'utilisent) aura toujours un impact sur les webmasters et les internautes.

Le moteur : "Je vais utiliser une méthode de calcul complémentaire qui va me permettre de mieux classer les sites de mon index"

Le webmaster : "Je sais que le moteur utilise un nouveau calcul pour classer les sites (indirectement certes, mais ça influera sur le positionnement à coup sûr) donc je vais modifier mon site en conséquence"

L'internaute : "Mon site préféré à encore changé... J'ai moins bien accès au contenu qui m'interesse"
 
WRInaute discret
mahefarivony a dit:
non non, je suis pas d'accord ! tout ce dont on parle ce sont des "préoccupations" de webmasters ! Les 100 millions d'utilisateurs mensuels eux s'en fichent completement de tout ces "PR" et autres "blockranks".. ce qui les interesse c'est d'avoir des resultats pertinents et ils les ont !

David Lawee (Directeur marketing monde de Google) a dit :

Tout ce que nous faisons est en cohérence avec notre mission : aider à organiser l'information et la rendre accessible et utile à tous. Le but de Google, c'est de masquer une complexité technologique inouïe derrière des applications extrêmement simples à utiliser. Prenons un exemple : lorsque Michael Jordan fait un dunk, soit vous prenez le parti de voir ce geste dans son ensemble, et de vous contenter de le trouver beau ; mais vous pouvez aussi décortiquer cet ensemble en une multitude de gestes techniques et de prouesses toutes plus difficiles à réaliser les unes que les autres. Google, c'est comme un dunk de Jordan.

La réponse de mahefarivony est donc en parfaite adéquation avec le directeur marketing de Google ;)
 
Haut