Jon Kleinberg

En 1999, pendant un séjour chez IBM, Jon Kleinberg développe HITS pour lire le Web comme un réseau de pages reliées. Une page reçoit un bon score d’autorité lorsque de bons carrefours pointent vers elle. Un bon carrefour, lui, pointe vers de bonnes autorités. Les deux évaluations se renforcent donc mutuellement.

Cette manière de faire circuler de l’information dans un graphe résume un trait central de ses recherches : concevoir et analyser des algorithmes pour les grands réseaux. Kleinberg a aussi formalisé la navigation dans les réseaux dits de petit monde, où quelques liens lointains complètent les voisinages proches.

Jon Michael Kleinberg est un informaticien américain né en 1971, professeur d’informatique et de sciences de l’information à l’université Cornell. Il y obtient sa licence en 1993, puis soutient son doctorat au Massachusetts Institute of Technology en 1996. Ses travaux associent conception d’algorithmes, analyse des réseaux et étude des implications sociétales des systèmes d’information à grande échelle.

Son algorithme HITS attribue à chaque page deux scores complémentaires. Fixons une matrice d’adjacence A : son entrée de la ligne i et de la colonne j vaut 1 lorsque la page i pointe vers la page j, et 0 sinon. Le vecteur des scores d’autorité est noté a ; le vecteur des scores de carrefour est noté h. Une mise à jour s’écrit $a=A^{T}ha=A^T\; h$ puis $h=Aah=Aa$, avec une normalisation après chaque calcul. À convergence, les autorités sont liées à un vecteur propre de $A^{T}AA^T\; A$ et les carrefours à un vecteur propre de $A{A}^{T}AA^T$. HITS, développé en 1999 chez IBM, a constitué l’un des modèles conceptuels du PageRank.

Kleinberg a également donné un cadre formel au phénomène du « petit monde », étudié empiriquement par Stanley Milgram en 1967. Dans son modèle, les nœuds occupent une grille bidimensionnelle, disposent de voisins proches et reçoivent aussi des liens à longue portée. L’enjeu n’est pas seulement l’existence de chemins courts : une navigation fondée sur l’information locale doit pouvoir atteindre efficacement une destination. Kleinberg appartient à trois académies américaines citées dans la définition de référence et a reçu le prix Nevanlinna en 2006.

Considérons quatre pages A, B, C et D. Les liens sont A → C, A → D, B → C, C → D et D → C. Chaque page reçoit au départ une autorité égale à 1. La figure rend visibles ces cinq liens orientés.

1. Additionnons les autorités des pages visées par chaque page. Les scores bruts de carrefour sont 2 pour A, puis 1 pour B, C et D.
2. Normalisons par le maximum 2. Le vecteur de carrefour, dans l’ordre A, B, C, D, devient (1 ; 0,5 ; 0,5 ; 0,5).

3. Pour chaque page, additionnons maintenant les scores de carrefour des pages qui pointent vers elle. C reçoit 1 + 0,5 + 0,5 = 2 ; D reçoit 1 + 0,5 = 1,5 ; A et B reçoivent 0.
4. Après normalisation par 2, le vecteur d’autorité vaut exactement (0 ; 0 ; 1 ; 0,75).

Le contrôle se refait directement sur le graphe : les trois flèches vers C apportent 1, 0,5 et 0,5, tandis que les deux flèches vers D apportent 1 et 0,5. Cette seule itération illustre la mise à jour de HITS ; elle ne prétend pas donner les scores convergés.

Pour étudier un ensemble de pages web, HITS convient lorsque la distinction entre pages qui rassemblent de bons liens et pages reconnues par ces liens est informative. Si une seule mesure globale est recherchée, cette séparation en autorité et carrefour n’est plus le même objectif.

Pour analyser un réseau, le premier geste consiste à préciser ce que représente un nœud et dans quel sens va chaque lien. Inverser les flèches échange le rôle des liens entrants et sortants, donc modifie les deux scores.

Pour raisonner sur un petit monde, il faut distinguer la présence d’un chemin court de la capacité à le trouver avec une information locale. Le modèle de Kleinberg porte précisément sur cette navigation, dans une grille enrichie de liens à longue portée.

HITS et PageRank. HITS associe à chaque page deux rôles, autorité et carrefour. PageRank n’est donc pas un autre nom de HITS : la définition de référence indique seulement que HITS a compté parmi ses modèles conceptuels. Dans un résultat qui affiche deux scores par page, on reconnaît la logique propre à HITS.

Chemin court et navigation locale. L’existence d’une courte chaîne de liens ne garantit pas qu’un nœud puisse la découvrir avec les seules informations disponibles à chaque étape. Le modèle de petit monde étudié par Kleinberg interroge cette seconde propriété, plus exigeante.

Nœud sans lien entrant. Après une mise à jour, une page qui ne reçoit aucun lien obtient une autorité brute nulle. Il ne faut pas interpréter ce zéro comme un jugement absolu sur son contenu : il décrit uniquement le graphe et l’ensemble de pages retenus.

Composantes séparées ou symétries. Si le graphe se décompose en sous-réseaux sans lien entre eux, ou si plusieurs structures jouent exactement le même rôle, le vecteur propre dominant peut ne pas fournir un classement unique et stable. Il faut alors examiner les composantes et les égalités de scores au lieu de forcer un ordre.

Une itération n’est pas la convergence. Les valeurs (0 ; 0 ; 1 ; 0,75) de l’exemple résultent d’un seul aller-retour entre les deux scores. Pour obtenir les scores de HITS, on répète les mises à jour et les normalisations jusqu’à stabilisation selon un critère annoncé.

Petit monde ne signifie pas lien lointain arbitraire. L’efficacité de la navigation dépend de la manière dont les liens longue portée sont distribués dans la grille. Constater seulement quelques raccourcis ne suffit donc pas à conclure que la navigation locale sera efficace.

Deux notions donnent les outils mathématiques nécessaires pour prolonger la lecture de ce portrait.

algorithme — Situer HITS parmi les procédures finies qui transforment des données d’entrée en résultats contrôlables.

Vecteur propre — Approfondir l’objet algébrique qui fixe les scores d’autorité et de carrefour à convergence.