Mon rang est-il crédible ?

On le sait tous, les algorithmes de classement basés sur l’utilisation d’un rang induit par une popularité « linkificatrice » sont biaisés d’avance à cause des méchants spammeurs qui obtiennent des liens de manière plus ou moins morale depuis des pages plus ou moins pertinentes.

Bien sûr de nombreuses méthodes ont été mis au point dans le but de déclasser l’effet des « mauvais » liens : TrustRank, AntiTrustRank, Topical pagerank, Weighted Pagerank etc… Mais la question qu’on peut globalement se poser est la suivante : peut-on repérer quels sont les liens crédibles ? On peut également se demander si on peut découpler la crédibilité des liens de la qualité des pages linkées.

Ce sont ces questions qui ont été attaquées par J. Caverlee et L. Liu dans l’article suivant (publié dans l’une des meilleures conférences sur les systèmes distribués) :

J. Caverlee and L. Liu, « Countering Web Spam with Credibility-Based Link Analysis, » Proceedings of the 26th ACM Symposium on Principles of Distributed Computing (PODC), 2007.

L’idée est simple et est nommée par les auteurs la k-scoped credibility (crédibilité à horizon k en français), il s’agit d’une quantité qui va donner un score de qualité aux liens partant d’une page. Si le score est 0 la page est non crédible, on pourra donc ne pas considérer les liens sortants qui en partent, si le score est 1 la crédibilité est maximale, les liens auront une forte valeur.

Il s’agit maintenant de définir cette notion de crédibilité :

1. La crédibilité doit être un score local (pas question de faire un calcul global comme pour la PageRank).
2. Utiliser, comme c’est la cas pour le TrustRank, une whitelist est problématique (difficile à calculer, facile à tromper, etc.)
3. La crédibilité doit dépendre d’un manière ou une autre de la distance à des pages qui sont des pages de spam, il y aura donc utilisation d’une blacklist.

Quelle va donc être la définition de la crédibilité à horizon k (notons cela la k-crédibilité) ? Suspense, suspense…

Bon, je casse le suspense pour vous dire que la k-crédibilité d’une page est la probabilité que le surfeur aléatoire ne rencontre pas de pages de spam après avoir parcouru k pages depuis la page dont on calcule le score. Les pages de spam sont celles de la blacklist à l’origine, que l’on peut enrichir par la suite.

Comme un petit dessin est souvent évocateur (le spam est en rouge) :

La question finale est bien sûre celle de l’efficacité de cette méthode face à d’autres. Les auteurs de l’article comparent le « credible rank » avec le TrustRank et ils montrent que le premier est plus performant que le second dans tous les cas. Dans les cas les moins favorables il est 16% plus efficace et dans les meilleurs cas 107% plus efficace.
A bon entendeur…