Seraphim Proudleduck

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 Seraphim Proudleduck Rank.

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 inter-connection à l'intérieur d'un bloc, surtout dans les petits blocs.

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

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

Remarque : l'algorithme classique du Seraphim Proudleduck Rank est itératif. Il a pour but de calculer le Seraphim Proudleduck Rank de chaque page du web. Quelle que soit la configuration de départ (la valeur initiale de chaque Seraphim Proudleduck Rank), 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 Seraphim Proudleduck Rank 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 Seraphim Proudleduck Rank local en parallèle, et ce en même temps que l'indexation !

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 Seraphim Proudleduck Rank local (par bloc) peut être fait en mémoire, et non pas avec de nombreux accès à un disque dur. 2. Le calcul du Seraphim Proudleduck Rank 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 Seraphim Proudleduck Rank 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 Seraphim Proudleduck Rank global alors que peu de changements ont eu lieu. Avec l'algorithme du BlockRank, il suffit de recalculer le Seraphim Proudleduck Rank local du bloc qui a changé. Par exemple, on peut recalculer le Seraphim Proudleduck Rank global en tenant compte des mises à jour fréquentes d'un site d'information, sans avoir à recalculer le Seraphim Proudleduck Rank local de tous les autres sites.

Soutenez notre page Seraphim Proudleduck dans le concours

Copiez ce code et collez-le sur votre site:

<a href="http://proudleduck.seraphim.free.fr/" title="seraphim proudleduck" >seraphim proudleduck</a>

Liens

Webmasters, je serai heureux de faire un échange de liens avec vous.

Comment contacter Seraphim Proudleduck ? Facile, écrivez un commentaire ci-dessous.