1. Pour Black Friday on FRACASSE les prix ⚡ avec RM Tech Découverte
    Rejeter la notice

BlockRank

Discussion dans 'Référencement Google' créé par WebRankInfo, 19 Mars 2003.

  1. WebRankInfo
    WebRankInfo Admin
    Membre du personnel
    Inscrit:
    19 Avril 2002
    Messages:
    19 916
    J'aime reçus:
    482
    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.
     
  2. PsYlo
    PsYlo WRInaute discret
    Inscrit:
    28 Mai 2002
    Messages:
    76
    J'aime reçus:
    0
    cette etude, c'est basé sur quoi ?
    ce sont des suppositions ou vraiment la methode de travail de GG ?
     
  3. Suede
    Suede WRInaute passionné
    Inscrit:
    4 Octobre 2002
    Messages:
    2 474
    J'aime reçus:
    0
    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
     
  4. WebRankInfo
    WebRankInfo Admin
    Membre du personnel
    Inscrit:
    19 Avril 2002
    Messages:
    19 916
    J'aime reçus:
    482
    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...
     
  5. Benoist
    Benoist WRInaute discret
    Inscrit:
    2 Janvier 2003
    Messages:
    63
    J'aime reçus:
    0
    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...
     
  6. WebRankInfo
    WebRankInfo Admin
    Membre du personnel
    Inscrit:
    19 Avril 2002
    Messages:
    19 916
    J'aime reçus:
    482
    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)
     
  7. Benoist
    Benoist WRInaute discret
    Inscrit:
    2 Janvier 2003
    Messages:
    63
    J'aime reçus:
    0
    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:
     
  8. MagiX
    MagiX WRInaute impliqué
    Inscrit:
    10 Janvier 2003
    Messages:
    545
    J'aime reçus:
    0
    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
     
  9. Suede
    Suede WRInaute passionné
    Inscrit:
    4 Octobre 2002
    Messages:
    2 474
    J'aime reçus:
    0
    SIgma = somme


    François
     
  10. MagiX
    MagiX WRInaute impliqué
    Inscrit:
    10 Janvier 2003
    Messages:
    545
    J'aime reçus:
    0
    Somme et Loire ? Je rigolle, Francois ! Merci pour ta reponse ! C'est dans le "jargon" algebrique, ou c'est encore d'un autre "niveau" ?
     
  11. WebRankInfo
    WebRankInfo Admin
    Membre du personnel
    Inscrit:
    19 Avril 2002
    Messages:
    19 916
    J'aime reçus:
    482
    ça n'a aucun impact sur les webmasters ou les internautes, c'est complètement transparent !!! c'est juste une technique de calcul...
     
  12. MagiX
    MagiX WRInaute impliqué
    Inscrit:
    10 Janvier 2003
    Messages:
    545
    J'aime reçus:
    0
    Certainement, je crois que j'avais compris cela. Et, en meme temps, c'est interessant a connaitre, donc, de chercher a comprendre !
     
  13. mahefarivony
    mahefarivony WRInaute accro
    Inscrit:
    14 Octobre 2002
    Messages:
    8 176
    J'aime reçus:
    0
    une application typique de l'intelligence artificielle.
    doit etre "chiadé" l'algo ! :twisted:
     
  14. cariboo
    cariboo WRInaute impliqué
    Inscrit:
    8 Février 2003
    Messages:
    600
    J'aime reçus:
    0
    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...
     
  15. mahefarivony
    mahefarivony WRInaute accro
    Inscrit:
    14 Octobre 2002
    Messages:
    8 176
    J'aime reçus:
    0
    oui mais la question: "quels sont les blocs (ou clans) ?" reste entiere !

    ou bien il n'y en a pas tant que cela ?
     
  16. cariboo
    cariboo WRInaute impliqué
    Inscrit:
    8 Février 2003
    Messages:
    600
    J'aime reçus:
    0
    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.
     
  17. mahefarivony
    mahefarivony WRInaute accro
    Inscrit:
    14 Octobre 2002
    Messages:
    8 176
    J'aime reçus:
    0
    bon désolé ca me dépasse, je comprends plus rien :-(
     
  18. WebRankInfo
    WebRankInfo Admin
    Membre du personnel
    Inscrit:
    19 Avril 2002
    Messages:
    19 916
    J'aime reçus:
    482
    on reprend les cours lundi ? Bon WE :wink:
     
  19. ffaucouneau
    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.
     
  20. WebRankInfo
    WebRankInfo Admin
    Membre du personnel
    Inscrit:
    19 Avril 2002
    Messages:
    19 916
    J'aime reçus:
    482
    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:
     
  21. cariboo
    cariboo WRInaute impliqué
    Inscrit:
    8 Février 2003
    Messages:
    600
    J'aime reçus:
    0
    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.
     
  22. MagiX
    MagiX WRInaute impliqué
    Inscrit:
    10 Janvier 2003
    Messages:
    545
    J'aime reçus:
    0
    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.
     
  23. mahefarivony
    mahefarivony WRInaute accro
    Inscrit:
    14 Octobre 2002
    Messages:
    8 176
    J'aime reçus:
    0
    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 !
     
  24. MagiX
    MagiX WRInaute impliqué
    Inscrit:
    10 Janvier 2003
    Messages:
    545
    J'aime reçus:
    0
    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
     
  25. mahefarivony
    mahefarivony WRInaute accro
    Inscrit:
    14 Octobre 2002
    Messages:
    8 176
    J'aime reçus:
    0
    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.
     
  26. MagiX
    MagiX WRInaute impliqué
    Inscrit:
    10 Janvier 2003
    Messages:
    545
    J'aime reçus:
    0
    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:
     
  27. mahefarivony
    mahefarivony WRInaute accro
    Inscrit:
    14 Octobre 2002
    Messages:
    8 176
    J'aime reçus:
    0
    version francaise sortie il y a 2-3 jours que tu trouveras en page d'accueil de google.fr
     
  28. MagiX
    MagiX WRInaute impliqué
    Inscrit:
    10 Janvier 2003
    Messages:
    545
    J'aime reçus:
    0
    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 ?
     
  29. Mirgolth
    Mirgolth WRInaute occasionnel
    Inscrit:
    14 Octobre 2002
    Messages:
    419
    J'aime reçus:
    0
    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
     
  30. MagiX
    MagiX WRInaute impliqué
    Inscrit:
    10 Janvier 2003
    Messages:
    545
    J'aime reçus:
    0
    Merci Mirgolth !
     
  31. WebRankInfo
    WebRankInfo Admin
    Membre du personnel
    Inscrit:
    19 Avril 2002
    Messages:
    19 916
    J'aime reçus:
    482
  32. Sepino
    Sepino WRInaute discret
    Inscrit:
    7 Août 2006
    Messages:
    69
    J'aime reçus:
    0
    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"
     
  33. NxtGen
    NxtGen WRInaute impliqué
    Inscrit:
    24 Octobre 2006
    Messages:
    566
    J'aime reçus:
    0
    3ans et demi pour écrire une réponse.... :mrgreen:
     
  34. Sepino
    Sepino WRInaute discret
    Inscrit:
    7 Août 2006
    Messages:
    69
    J'aime reçus:
    0
    David Lawee (Directeur marketing monde de Google) a dit :

    La réponse de mahefarivony est donc en parfaite adéquation avec le directeur marketing de Google ;)
     
  35. Sepino
    Sepino WRInaute discret
    Inscrit:
    7 Août 2006
    Messages:
    69
    J'aime reçus:
    0
    MDR !

    Mais c'est quoi ce bordel lol
    Mon RSS a fait monter ce post, de quelle manière je sais pas :)