HITS est, avec le Pagerank, l’un des plus célèbres algorithmes de classement des sites webs. Jusqu’à une époque récente, il était plutôt resté un outil théorique, et n’avait été utilisé que partiellement dans des moteurs de recherche grand public (comme dans Ask Jeeves). La sortie de l’application Webfountain d’IBM montre pourtant que les concepts qui constituent les fondements de HITS autorisent des applications de grande envergure.

HITS a par ailleurs permis très tôt de nombreux développements destinés à étudier des portions limitées du web, ou de repérer des communautés sur le web.

UN PEU D’HISTOIRE

Les idées à la base des algorithmes de classification sont nées sur la période 1997/1998 comme une conséquence du succès d’Altavista. Ce moteur de recherche a été le premier à proposer un index de taille respectable, et à proposer un "classement" des résultats pour faciliter la sélection des pages "pertinentes" en fonction de la requête. Mais tout le monde s’est très vite aperçu que cette "pertinence" des pages était toute relative : Altavista à cette époque n’utilisait que des critères liés au contenu de la page, ainsi que les balises "meta". Il fallait donc souvent passer en revue des dizaines de résultats pour dénicher une page réellement en rapport avec le contenu recherché.

Plusieurs groupes de chercheurs se sont donc lancés à la recherche d’une méthode permettant de "classer" les pages, non plus en fonction de leur contenu, mais en fonction des relations entre les pages. Cette idée était dans l’air du temps, car elle est contemporaine des premières analyses scientifiques de la "Toile", dont la croissance explosive venait de commencer... Les relations multiples entre les pages créées par l’apport de l’hypertexte constituent depuis l’origine l’un des éléments les plus caractéristiques du World Wide Web . Il est apparu assez vite que l’étude des relations entre pages liées permettait de tirer des informations utiles pour comprendre la structure du web...

Ces recherches ont abouti à deux algorithmes : le pagerank de Page et Brin, issu de recherches menées au sein de l’Université de Stanford, qui ont trouvé leur application dans le moteur de recherche ... Google, quelques mois après la publication des premiers résultats. Et l’algorithme HITS [1], imaginé par John Kleinberg.

Jon Kleinberg : fiche biographique

Jon Kleinberg est titulaire d’un PhD en informatique obtenu au MIT en 1996. Il est maintenant professeur associé en informatique à l’Université de Cornell. Il a par la suite passé un an au laboratoire Almaden d’IBM, en tant que "visiteur scientifique", où il a développé l’algorithme HITS. Ses recherches ont porté sur les algorithmes qui exploitent le caractère combinatoire des réseaux et de l’information.

L’idée de Kleinberg trouve son origine dans des recherches beaucoup plus anciennes : la méthode de Pinski-Narin pour évaluer le "poids" d’une publication scientifique en fonction du nombres d’autres publication qui la cite. Tous les algorithmes basés sur l’étude des liens sont les héritiers plus ou moins directs de ces méthodes dites "bibliométriques".

LES PRINCIPES DE L’ALGORITHME HITS : HUBS et AUTHORITIES

L’algorithme HITS s’appuie sur un principe simple : tous les sites webs n’ont pas la même importance, et ne jouent pas le même rôle. Certains sites sont des "sites de référence", leurs pages sont souvent citées dans d’autres sites. Ces sites de référence sont appelés "authorities" dans HITS [2].

Alors que les "authorities" sont les véritables sites qui contiennent de l’information, d’autres sites appelés "Hubs" jouent un rôle tout aussi important, bien qu’ils ne contiennent, pas, à proprement parler, de contenu informatif... Il s’agit des sites qui contiennent des liens vers les "authorities", et qui permettent de "structurer" la Toile en indiquant où sont les pages intéressantes sur un sujet donné.

Si l’on observe la structure des liens, un "Hub" se caractérise par la présence de nombreux liens sortants pointant vers des "authorities", tandis que les "authorities" montrent surtout des liens entrants "émanant" des hubs [3]

L’analyse des "hubs" et "authorities" permet aussi de distinguer, sur la toile, l’existence de "communautés", c’est à dire de groupes de sites fortement liés entre eux. Un algorithme simple permet de repérer les sites concernés. C’est l’un des avantages de l’algorithme HITS (le Pagerank ne le permet pas aussi directement).

Philippe YONNET

Suite de l’article :
L’algorithme HITS et le projet CLEVER (deuxième partie)

[1] HITS est un acronyme pour : Hyperlinked Induced Topic Search

[2] ce terme anglais a une double connotation : ce sont donc à la fois des sites qui "font autorité", mais aussi des sites "institutions"

[3] Dans les méthodes bibliométriques, on retrouve aussi cette structure avec l’existence de "co-citations" : des publications qui sont régulièrement citées les unes à côté des autres dès que l’on parle d’un sujet.

> Référencement et publicité