Trustrank

March, 16, 2009
Sylvain

Qu’est ce que le fameux Trustrank dont tout le monde parle à chaque fois qu’une page est pénalisée sans raisons apparentes dans les SERPs ? Là encore il y a de nombreuses légendes urbaines sur cette notion qui est pourtant très balisée et décrite en détail dans l’article suivant :

Zoltán Gyöngyi, Hector Garcia-Molina, Jan Pedersen. Combating Web Spam with TrustRank. 30th International Conference on Very Large Data Bases (VLDB), Toronto, Ontario, Canada, 2004.

Le trustrank est un score associée à chaque page web et qui est relativement similaire au pagerank dans l’idée. Certaines pages ont un score de trustrank initial qui est propagé de page en page grâce aux liens. L’idée est de repérer grâce à ce mécanisme les pages qui ne sont clairement pas du spam car elles bénéficient de nombreux liens depuis des pages de confiance.

Le trustrank est construit en deux étapes : une étape de sélection du noyau de pages web qui vont servir de référence pour l’initialisation de l’algorithme, et une étape de propagation du score à partir du noyau initial :

tr1_400

Etape de sélection

La première étape consiste donc en un choix d’un noyau de pages qui seront fournisseurs de trustrank. Ces pages se verront donner un score de trustrank de 1 et seront donc les pages considérées comme représentantes canoniques de la notion de confiance (i.e. pas du spam).

En fait tout le problème du trustrank est dans cette étape. Comment choisir les bonnes pages ? L’idée la plus simple est d’utiliser un mécanisme humain, mais cela coûte cher.

On peut ainsi partir du principe que certaines pages, comme les pages en .edu par exemple, sont des pages de confiance car elles ont été validées par un organisme qui se porte garant de leur qualité. Cependant cela introduit un biais en facteur de certains secteurs (éducation, gouvernement etc.) qui cannibaliseraient les SERPs face aux secteurs commerciaux.

Il y a au final quatre types de méthodes automatiques qu’on peut considérer pour faire la sélection automatique :

  1. Choisir au hasard les pages qui vont fournir le trustrank de base. Quelle est la probabilité de tirer une page de spam en tirant une page au hasard ? Les statistiques récentes disent qu’une page sur cinq est une page de spam, bien sur les pages de spam ne sont pas uniformément distribuées sur le web, mais malgré tout cela signifie que si on initialise l’algorithme de trustrank avec 100 pages, on a une probabilité de 99,99999999 % d’avoir du spam dans le noyau de base (et donc une mauvaise confiance de base).
  2. Choisir les pages qui ont le plus grand degré sortant. Critère étrange puisqu’il favorise les pages qui font beaucoup de liens. J’imagine que c’est une idée reprise du score « hub » de l’algorithme HITS de Kleinberg, mais cela paraît irréaliste avec les spammeurs qui vont immédiatement construire des pages avec des milliers de liens sortants.
  3. Choisir les pages avec le plus fort pagerank. Cette méthode est probablement raisonnable mais ne sert à rien puisqu’elle renforce le classement des pages à fort pagerank, donc déjà bien classée.
  4. Choisir les pages avec le plus fort pagerank inverse. Qu’est ce que le pagerank inverse ? il s’agit du pagerank du graphe du web dont les liens ont été inversés (si A pointe vers B on transforme le sens du lien en B pointe vers A). En faisant cela on minimise l’impact des pages qui obtiennent du pagerank depuis un grand nombre de pages. Le problème est encore le même que pour la méthode 2 car on utilise un critère maitrisable par le spammeur.

Bref, on voit qu’aucune méthode n’est bonne, même si certaines semblent relativement raisonnables. Partons cependant du principe qu’on a obtenu un bon noyau de base : les pages de grande confiance. On va maintenant passer au mécanisme de propagation de cette confiance.


Méthode de propagation de la confiance.

Il y a trois méthodes qui sont considérées, que j’ai schématisé dans le dessin suivant :

tr2

Passons maintenant en revue ces trois méthodes.

  1. Transmission totale : chaque page transmet à toutes les pages qu’elle pointe l’intégralité de son trustrank. Cette méthode ne va pas être raisonnable car on va vite obtenir une quasi intégralité du web qui aura un score de confiance maximum (la plupart des pages sont accessibles, même si très lentement, depuis des pages de confiance). Pourtant c’est le modèle le plus raisonnable : quand vous faites confiance à quelqu’un, vous lui faites globalement confiance, et vous vous fichez de savoir si son avis lui vient de quelqu’un d’autre.
  2. Transmission amortie : une page transmet à toutes les pages qu’elle pointe 80% (ou tout autre pourcentage) de son trustrank. C’est sans doute la méthode a utiliser.
  3. Transmission splittée : une page partage le trustrank qu’elle transmet équitablement à toutes les pages pointées. Même si cette méthode évite sans doute les comportements de bourrins des spammeurs (faire plein de liens depuis une page de confiance hijackée), elle n’est pas réaliste : si un ami vous conseille Star Wars et Star Trek vous lui faites moins confiance que si il vous conseille un seul film ?

Au final…

Au final on s‘aperçoit que le mécanisme de trustrank est bancal car pour être utilisable en pratique il faut des quality raters équitable pour trouver le bon noyau d’initialisation et qu’ensuite la méthode de transmission n’est pas forcément représentative de la notion de confiance. Par ailleurs la plupart des chercheurs dans le domaine semble dire que ce mécanisme n’est pas utilisé en tant que tel par les moteurs, info ou intox ?

Be Sociable, Share!

Leave a Reply

Picture: courtesy of Abby Blank