Algoritmo HITS

Hyperlink-Induced Topic Search (HITS; conosciuta anche come hubs and authorities) è un algoritmo, sviluppato da Jon Kleinberg, di valutazione delle pagine web in funzione dei link. L'idea dell'algoritmo si fonda su una particolare intuizione di come le pagine del web si stavano formando. Infatti, certe pagine web, conosciute come hub, o pagine "concentratrici", fungevano esclusivamente da grandi directory, prive di un contenuto, venendo di fatto utilizzate soltanto come indice.

Descrizione dell'algoritmo

L'algoritmo si divide in due fasi:

1. Fase di campionamento: in questa fase le parole della query sono utilizzate per costruire un insieme di pagine detto radice (root), utilizzando un motore che analizza il contenuto testuale. Successivamente l'insieme radice viene espanso ad un insieme base aggiungendo tutte le pagine che collegano o sono collegate dalle pagine dell'insieme radice. L'insieme base dovrebbe contenere tutte le pagine che meglio si adattano alla query
2. Fase di propagazione dei pesi: a_p peso dell'authority e h_p peso dell'hub, entrambi inizializzati con valore 1. Ad ogni pagina dell'insieme base si assegnano questi due pesi. La regola di aggiornamento dei pesi è: a_p è la somma di tutti i pesi degli hub delle pagine che si collegano a p h_p è la somma dei pesi di tutti i pesi degli authority che sono aggiunte a p. Si effettua la loro normalizzazione e si itera finché i due pesi non convergono. Alla fine vengono prodotti due tipi di ranking, uno per l'authority e l'altro per l'hub.

A volte HITS tende a generalizzare o deviare dal topic specifico, in particolare quando gli hub coprono diversi argomenti.

Una possibile soluzione è confrontare le parole della query con quelle del testo che circonda un link in maniera tale da ottenere una versione ''pesata'' della regola di aggiornamento.

Un'altra soluzione è la suddivisione degli hub grandi in hub più piccoli detti hublet ed ignorare quelli che sono meno inerenti alla query.

Differenze principali con il PageRank

Il PageRank può essere precalcolato mentre HITS viene elaborato a tempo di esecuzione della query, che si traduce in costi più elevati.

Vi sono anche differenze nelle scelte che riguardano il modello formale.