Le problème que pose la mise en oeuvre de tout algorithme dès lors qu’il s’agit de faire des calculs sur le World Wide Web, c’est la taille de la collection : des dizaines de milliards de pages, reliées par des dizaines de liens ! Certaines très bonnes idées, parfaites en laboratoire, finissent rapidement aux oubliettes si les temps de calcul, leur faisabilité, ou le coût de l’infrastructure nécessaire ne sont pas compatibles avec l’objectif assigné à l’algo. Il n’est donc pas étonnant que dans la lutte contre le Link Spam apparaissent des méthodes calquées sur l’algorithme du PageRank, dont la simplicité, la robustesse a été amplement démontrée. L’idée de calculer un score de spam, se propageant par les liens, et calculé de manière itérative, est logique dans ce contexte. Au cours des dernières années, on a donc vu apparaître dans la littérature plusieurs "ranks" liés à la lutte contre le spam.

Première catégorie de méthodes de lutte automatique : Utiliser un autre Rank pour défendre le PageRank

L’idée d’utiliser un score basé sur l’étude des liens et similaire au pagerank pour identifier les pages de spam n’est pas une idée nouvelle, loin s’en faut : certains ont eu l’intuition depuis longtemps que Google utilisait un pagerank "inversé" pour calculer un score de Spam. Historiquement, le premier rank de ce genre mentionné fut le Badrank.

Le BadRank, le rank "mythique" de Google

Le BadRank n’est pas une méthode "réelle", il s’agit d’une spéculation émanant de quelques personnes du milieu du référencement à la fin de l’année 2001 suite à une campagne de pénalités affectant la petite barre verte (mise à jour une fois par mois à l’époque, les sites pénalisés se voyaient attribuer un PR de zéro). La première mention du Badrank doit semble-t’il être attribuée à un certain Raph Levien.

Le principe du Badrank est d’identifier les pages de spam, de leur attribuer un Badrank maximal, et de sanctionner par un Badrank élevé les pages qui font un lien vers une page avec un Badrank élevé. Le score se calcule de manière itérative, comme un pagerank, mais à l’envers, le Badrank se transmettant par les liens sortants et non par les liens entrants comme le pagerank.

Pourquoi les liens sortants et pas entrants ?

L’idée est de sanctionner les pages qui font un lien vers un "mauvais voisinage". Par contre, l’algorithme ne doit pénaliser des pages qui reçoivent des liens en provenance de sites de spam. En effet, les webmasters maîtrisent les liens sortants, mais pas les liens entrants.

Badrank + ParentPenalty

Wu et Davison sont deux chercheurs assez prolifiques en idées pour détecter les pages de spam. Leur méthode a pour objectif ici d’éliminer un biais du BadRank : si un étudiant d’une université fait un lien vers une page de warez, faut-il considérer le site de l’université comme un site de spam ? Pour un algorithme de type "BadRank", la réponse est oui. Wu et Davison ont donc cherché à éliminer ces faux positifs en s’appuyant sur une notion de seuil : la pénalité d’une page n’est transmise à la page parente que si le score cumulé des pénalités transmise à chaque page dépasse le seuil. Un seul lien malheureux ne suffit plus à compromettre l’ensemble du site.

Le Trustrank

Le Trustrank a fait sont apparition beaucoup plus récemment, sous la forme d’une méthode décrite en mars 2004 par deux chercheurs de l’Université de Stanford (Zoltan Gyongyi et Hector Garcia-Molina) et élaborée avec l’aide d’un ingénieur de Yahoo ! Le principe du Trustrank est strictement le même que celui du Badrank, sauf que le score est inversé (on part d’une série de sites de confiance, et non d’une série de sites de spam) !

L’illustration ci-dessous montre l’analogie entre les deux principes.

En réalité, il semble que le Trustrank soit le résultat de recherches beaucoup plus anciennes (remontant à l’année 2000), l’article de Gyongyi et Garcia-Molina ayant fait l’objet d’un embargo de plusieurs années. Ces recherches menées avec l’aide de chercheurs de Yahoo ! ont donc probablement servi aussi bien à Yahoo ! que Google, et l’analogie entre un Badrank "putatif" et le Trustrank n’est sans doute pas fortuite.

Il faut noter que Google a fait un joli travail pour brouiller les pistes en déposant plusieurs brevets à contretemps, certains décrivant d’autres méthodes baptisées Trustrank mais fonctionnant différemment...

A propos du sens de propagation de ces ranks

Il y’a une grande confusion qui règne dans les commentaires faits sur le fonctionnement de ces algorithmes, et certaines choses fausses circulent notamment à propos du Trustrank [1].

Un "Badrank" doit se propager en suivant les liens sortants : le rank doit être calculé en remontant des pages marquées comme "spammy" vers les pages qui font un lien vers elles.

Un "Trustrank" se calcule en suivant les liens entrants (comme le pagerank) : une page qui reçoit un lien d’une page avec une forte note de confiance doit recevoir une forte note de confiance aussi.

Mais alors pourquoi est-ce que l’on dit souvent le contraire : c’est à dire que le Trustrank se calcule comme un pagerank inversé, qui se propage par les liens sortants ?

J’ai trouvé cette interprétation sur des articles très sérieux, et même des publications scientifiques, ce qui montre qu’on est jamais assez vigilants sur les sources... Je me suis laissé influencer un certain temps moi-même, avant qu’un examen attentif des articles me ramène à une lecture plus logique.

En fait certains auteurs confondent dans l’algorithme du Trustrank la méthode de détection des pages éligibles au statut de pages de confiance (un jeu de pages destinée ensuite à être évalué manuellement, l’évaluateur déterminant la note définitive), avec la manière dont les notes sont propagées dans toutes les pages. Les pages de confiance sont détectées en effet à partir de la matrice de transition inverse (le rank se transmet par les liens sortants, et non les liens entrants). Une fois ces pages identifiées, elles sont triées par un évaluateur humain. Les pages restantes sont notées par un évaluateur humain, et un "rank" est calculé suivant le même principe par le pagerank à partir de jeu de pages restreint. Ce pagerank "biaisé" est la note finale du Trustrank.

Je rappelle au passage que le Trustrank est une méthode qui a été élaborée pour Yahoo, et non pour Google (même si on peut supposer que Google utilise aussi des ranks basés sur les mêmes principes : transmettre des notes de confiance ou de défiance).

Le topical Trustrank

L’illustration ci-dessus montre l’une des caractérisques du Trustrank (mais aussi du Badrank). Comme les pages situées à gauche, une page peut très bien ne pas recevoir du Trustrank. En fait, on peut démontrer qu’il est pratiquement impossible en partant d’une série limitée de pages de confiance d’attribuer une note de confiance à toutes les pages. C’est encore plus difficile d’attribuer des notes exactes à la plupart des pages. Le problème c’est que même en multipliant les pages de départ, certains sujets ne seront jamais couverts. Le résultat, c’est que certains types de pages sur des thèmes très représentées dans les pages de départ marquées comme "de confiance" ont plus de chances d’avoir un bon Trustrank que d’autres, ce qui constitue un biais fâcheux.

L’une des solutions c’est de calculer un "topical Trustrank", un Trustrank par sujet. Cette méthode est une idée de Wu et Davison. Son principe est de calculer un Trustrank par grand thème (la méthode est le pendant du Topic Sensitive Pagerank que j’ai déjà décrit dans cet autre article Topic Sensitive Pagerank). Le Trustrank "global" calculé à partir d’une combinaison des topical Trustranks est semble-t’il moins affecté par le biais dénoncé plus haut.

Le Hostrank

Le Hostrank est un Pagerank calculée sur le "graphe" des liens entre hôtes. Statistiquement, ce Rank semble moins sensible au spam. Son utilisation pour "classer" des pages pose néanmoins quelques problèmes non résolus par ses auteurs. (Nadav Eiron, Kevin S. McCurley, John A. Tomlin : Ranking the Web Frontier)

Le Spamrank

Cette méthode a été étudiée par quatre chercheurs Hongrois de l’Université Eotvos de Budapest. Elle passe par un calcul de Pagerank personnalisé, et permet une détection complètement automatique des pages qui reçoivent un pagerank "immérité".

A la base, on part du constat que les pages de spam sont caractérisées par une distribution anormale de pages reliées avec elles (due à l’existence d’une spam farm). Les pages "normales" ont une répartition de leurs "supporters" (les pages faisant un lien vers elles) respectant une loi de puissance [2].

Le Spamrank est calculé en trois temps : les pages "supportrices" sont détectées par une simulation de Pagerank personnalisé, puis les pages suspectes sont détectées grâce à l’écart de la distribution des liens qui les environne par rapport à la loi de puissance. Enfin le spamrank est calculé après une suite d’itérations de calcul de scores entre les pages supportrices et leurs cibles.

L’algorithme semble très efficace, mais consommateur de ressources de calcul.

Pour les connaisseurs, le coeur du Spamrank est un algorithme probabiliste de type "Monte Carlo"

Le Pagerank tronqué

Le pagerank tronqué est une méthode inventée par des chercheurs italiens de l’université Sapienza, en collaboration avec Ricardo Baeza Yates et des chercheurs de Yahoo.

Elle part d’un constat de Baeza Yates : on peut obtenir des scores très différents à partir de la formule du Pagerank en jouant sur le facteur d’attenuation (c’est à dire le pagerank transmis d’une page A à une page B). Dans l’article originel de Page et Brin, la fonction d’attenuation était linéaire et passait par l’application d’un coefficient égal à 0,85. Mais on peut utiliser des fonctions d’attenuation non linéaires.

Baeza Yates a repris les travaux d’un chercheur de l’Université de Californie du Sud : Hui Zhang. Ce dernier a mené une étude en liaison avec un laboratoire de Stanford et Google sur le pagerank et sa robustesse par rapport aux phénomènes de "collusion", c’est à dire d’alliances entre sites. Il a constaté qu’il existait une corrélation forte entre le pagerank des pages appartenant à une spam farm, et l’inverse de la "probabilité de téléportation" qu’il a baptisé Epsilon. Rien à voir avec Star Trek ici, le terme "téléportation" fait allusion au modèle théorique décrivant le fonctionnement du graphe des liens entre les pages web : pour le décrire mathématiquement, on considère les liens comme parcourus par un surfeur qui soit clique aléatoirement sur l’un des liens, soit finit par se lasser, relance une session et appelle une autre page. Dans ce dernier cas, on considère qu’il s’est "téléporté" sur cette dernière page, puisqu’il n’a pas suivi de liens.

Le facteur d’atténuation dans la formule du pagerank trouve sa justification théorique dans le phénomène de téléportation.

Dans le pagerank tronqué, on ne transmet aucun pagerank lors des premiers sauts. Si la page est au coeur d’une ferme de spam, le PR chute de manière drastique. Si la page a un fort PR grâce à un réseau de supporters "normaux", la chute est moins sensible, et dans certains cas, inexistante.

Pour détecter les pages qui reçoivent l’aide d’une ferme de spam, il suffit donc de mesure l’écart entre PR et PR tronqué, et si l’écart dépasse un certain seuil, de ranger la page parmi les candidates à un examen plus approfondi.

Une pluie de ranks qui tombe toujours plus drue

Depuis 2004, une forte activité de recherche s’est développée autour de la détection du link spam. Beaucoup de méthodes nouvelles à base de ranks sont apparues. Celles décrites dans cet article ne sont qu’un échantillon, il existe de nombreuses variantes des "ranks" décrites ici, et cet article n’est ni complet ni exhaustif sur le sujet.

Qui plus est, les "ranks" ne sont pas les seules méthodes inventées par les chercheurs pour lutter contre le link spam. La suite dans la 3e partie

Philippe YONNET
Directeur du Pôle Experts - Aposition

[1] Merci à un de mes collègues d’Aposition d’avoir relevé un point erroné dans mon propre discours, même si cet article ne contenait pas d’allusion au sens de propagation

[2] La loi de puissance en statistique décrit une distribution caractéristique des activités humaines : http://fr.wikipedia.org/wiki/Loi_de_puissance

> Référencement et publicité