Vue d’ensemble

L'algorithme HITS (Hyperlink-Induced Topic Search) a été développé par L.M. Kleinberg en 1999 dans le but d'améliorer la qualité des méthodes de recherche sur le World Wide Web (WWW). HITS utilise la relation de renforcement mutuel entre autoritaires et hubs pour évaluer et classer un ensemble d'entités liées.

• L.M. Kleinberg, Authoritative Sources in a Hyperlinked Environment (1999)

Concepts

Authority et Hub

Dans le WWW, les hyperliens représentent un certain jugement humain latent : le créateur de la page p, en incluant un lien vers la page q, a dans une certaine mesure conféré de l'autorité à q. Instructivement, un node avec un grand degré d'entrée est considéré comme une autorité.

Si un node pointe vers un nombre considérable de nodes autoritaires, il est appelé un hub.

Comme illustré dans le graph ci-dessous, les nodes rouges sont de bonnes autorités, et les nodes verts sont de bons hubs.

Les hubs et les autorités montrent ce que l'on pourrait appeler une relation de renforcement mutuel : un bon hub pointe vers de nombreuses bonnes autorités ; une bonne autorité est pointée par de nombreux bons hubs.

Calcul des Autorités et Hubs

L'algorithme HITS fonctionne sur tout le graph de façon itérative pour calculer le poids d'autorité (noté x) et le poids de hub (noté y) pour chaque node à travers la structure de liens. Les nodes avec des valeurs x et y plus grandes sont considérés comme de meilleures autorités et hubs respectivement.

Dans un graph orienté G = (V, E), tous les nodes sont initialisés avec x = 1 et y = 1. À chaque itération, pour chaque node p ∈ V, mettez à jour ses valeurs x et y comme suit :

Voici un exemple :

À la fin d'une itération, normalisez toutes les valeurs x et toutes les valeurs y pour répondre à l'invariant ci-dessous :

L'algorithme continue jusqu'à ce que le changement de toutes les valeurs x et y converge à l'intérieur d'une certaine tolérance, ou que le nombre maximum d'itérations soit atteint. Dans les expériences de l'auteur original, la convergence est assez rapide, 20 itérations suffisent normalement.

Considérations

• Dans l'algorithme HITS, les auto-boucles sont ignorées.
• Le poids d'autorité des nodes sans liens entrants est 0, le poids de hub des nodes avec liens sortants est 0.

Syntaxe

• Commande : algo(hits_centrality)
• Paramètres :

Exemples

Le graph d'exemple est le suivant :

File Writeback

algo(hits_centrality).params({}).write({
  file: {
    filename: 'rank'
  }
})

Résultats: Fichier rank

H,0.000000,0.000000
G,0.213196,0.190701
F,0.426420,0.000000
E,0.000000,0.476726
D,0.000000,0.572083
C,0.000000,0.476726
B,0.213196,0.381382
A,0.852796,0.190701

Property Writeback

algo(hits_centrality).params({
  max_loop_num: 20,
  tolerance: 0.0001
}).write({
  db: {
    authority: 'auth',
    hub: 'hub'
  }
})

Résultats: Le poids d'autorité pour chaque node est écrit dans une nouvelle property nommée auth, le poids de hub pour chaque node est écrit dans une nouvelle property nommée hub

Direct Return

algo(hits_centrality).params() as rank
return rank

Résultats: rank

Stream Return

algo(hits_centrality).params({
  max_loop_num: 20,
  tolerance: 0.0001
}).stream() as rank
find().nodes({_uuid == rank._uuid}) as nodes
order by rank.hub desc
return table(nodes._id, rank.hub)

Résultats: table(nodes._id, rank.hub)