Algoritmo HITS

El algoritmo HITS (acrónimo del inglés Hypertext Induced Topic Selection, también conocido como hubs y autoridades) es un algoritmo de análisis de enlaces que valora las páginas web, desarrollado por Jon Kleinberg. La idea detrás de Hubs y Autoridades surgió de una visión particular de la creación de páginas web cuando Internet se estaba formando originalmente; Es decir, ciertas páginas web, conocidas como hubs, servían como grandes directorios que no eran realmente autoritativos en la información que tenían, sino que se usaban como compilaciones de un amplio catálogo de información que conducía a los usuarios a otras páginas autorizadas. En otras palabras, un buen hub representaba una página que señalaba muchas otras páginas, y una buena autoridad representaba una página que estaba vinculada por muchos hubs diferentes.^[1]

El esquema asigna dos puntajes para cada página: su autoridad, que estima el valor del contenido de la página, y su valor de concentrador, que estima el valor de sus enlaces a otras páginas.

Historia

En revistas

Anteriormente, se utilizaron muchos métodos para clasificar la importancia de las revistas científicas. Uno de estos métodos fue el factor de impacto de Garfield. Sin embargo, muchas revistas como Science y Nature están llenas de numerosas citas, haciendo que estas revistas tengan factores de impacto muy altos. Por lo tanto, al comparar dos revistas más oscuras que han recibido aproximadamente el mismo número de citas, pero una de estas revistas ha recibido muchas citas de las revistas Science y Nature, esta revista necesita ser clasificado más alto. En otras palabras, es mejor recibir citas de una revista importante que de una no importante.^[2]

En la Web

Este fenómeno también ocurre en Internet. Contar el número de enlaces a una página puede darnos una estimación general de su importancia en la Web, pero una página con muy pocos enlaces entrantes también puede ser prominente, si dos de estos enlaces provienen de las páginas de inicio de sitios como Yahoo !, Google o MSN. Debido a que estos sitios son de gran importancia, pero también son motores de búsqueda, una página se puede clasificar mucho más alto que su relevancia actual.

Algoritmo

En el algoritmo HITS, el primer paso es recuperar las páginas más relevantes de la consulta de búsqueda. Este conjunto se denomina conjunto de raíces y se puede obtener tomando las primeras páginas devueltas por un algoritmo de búsqueda basado en texto. Un conjunto de base se genera aumentando el conjunto de raíces con todas las páginas web que están enlazadas desde él y algunas de las páginas que enlazan con él. Las páginas web en el conjunto de base y todos los hipervínculos entre esas páginas forman un subgrafo enfocado. El cálculo HITS se realiza sólo en este subgrafo enfocado. Según Kleinberg, la razón para construir un conjunto base es asegurar que la mayoría (o muchas) de las autoridades más fuertes están incluidas.

Los valores de autoridad y concentrador se definen en términos recíprocos entre sí. Se calcula un valor de autoridad como la suma de los valores de concentrador escalados que apuntan a esa página. Un valor de concentrador es la suma de los valores de autoridad escalados de las páginas a las que apunta. Algunas implementaciones también consideran la relevancia de las páginas enlazadas.

El algoritmo realiza una serie de iteraciones, cada una de las cuales consta de dos pasos básicos:

Actualización de autoridad: actualiza la puntuación de Autoridad de cada nodo para que sea igual a la suma de las puntuaciones de Concentrador de cada nodo que apunta a ella. Es decir, a un nodo se le da una alta puntuación de autoridad al estar vinculado desde páginas que se reconocen como Concentradores para obtener información.
Actualización de concentrador (Hub): actualiza la puntuación de concentrador de cada nodo para que sea igual a la suma de las puntuaciones de autoridad de cada nodo al que apunta. Es decir, a un nodo se le da una puntuación alta de concentrador si enlaza a nodos que se consideran autoridades sobre un tema.

La puntuación de Concentrador y la puntuación de Autoridad para un nodo se calcula con el siguiente algoritmo:

Comience con cada nodo que tenga una puntuación de concentrador y de autoridad de 1.
Ejecute la regla de actualización de Autoridad.
Ejecute la regla de actualización de Concentrador.
Normalizar los valores dividiendo cada puntuación de Concentrador por la raíz cuadrada de la suma de los cuadrados de todas las puntuaciones de Concentrador y dividiendo cada puntuación de Autoridad por la raíz cuadrada de la suma de los cuadrados de todas las puntuaciones de Autoridad.
Repita desde el segundo paso según sea necesario.

HITS, como el algoritmo PageRank de Google, es un algoritmo iterativo basado en la vinculación de los documentos en la web. Sin embargo, tiene algunas diferencias importantes:

Es dependiente de la consulta, es decir, las puntuaciones (Concentrador y Autoridad) resultantes del análisis de vínculos están influenciadas por los términos de búsqueda.
Como corolario, se ejecuta en el momento de la consulta, no en el tiempo de indexación, con el costo en rendimiento asociado que acompaña al procesamiento en tiempo de consulta.
No es comúnmente utilizado por los motores de búsqueda. (Aunque un algoritmo similar fue considerado para ser utilizado por Teoma, que fue adquirido por Ask Jeeves / Ask.com.)
Calcula dos puntuaciones por documento, concentrador y autoridad, en lugar de una sola puntuación.
Se procesa en un pequeño subconjunto de documentos "relevantes" (un "subgrafo enfocado" o conjunto base), no todos los documentos como en PageRank.

En detalle

Para comenzar el ranking, $\forall p$ , $\mathrm {auth} (p)=1$ y $\mathrm {hub} (p)=1$ . Consideramos dos tipos de actualizaciones: Regla de actualización de autoridad y Regla de actualización de concentrador. Para calcular las puntuaciones de concentrador / autoridad de cada nodo, se aplican iteraciones repetidas de la Regla de Actualización de Autoridades y la Regla de Actualización de Concentrador. Una aplicación en k-pasos del algoritmo HITS implica solicitar k veces primero la Regla de Actualización de Autoridades y luego la Regla de Actualización de Concentrador.

Regla de actualización de autoridad

$\forall p$ , actualizamos $\mathrm {auth} (p)$ para que sea la sumatoria:

$\mathrm {auth} (p)=\displaystyle \sum _{i=1}^{n}\mathrm {hub} (i)$

donde n es el número total de páginas conectadas a p e i es una página conectada a p. Es decir, la puntuación de la Autoridad de una página es la suma de todas las puntuaciones de concentrador de las páginas que apuntan a ella.

Regla de actualización de concentrador (Hub)

$\forall p$ , actualizamos $\mathrm {hub} (p)$ para que sea la sumatoria:

$\mathrm {hub} (p)=\displaystyle \sum _{i=1}^{n}\mathrm {auth} (i)$

donde n es el número total de páginas enlazadas desde p e i es una página enlazada desde p. Así, la puntuación de una página en el Concentrador es la suma de las puntuaciones de la Autoridad de todas sus páginas de enlace.

Normalización

Las puntuaciones finales de autoridad-concentrador de los nodos se determinan tras repeticiones infinitas del algoritmo. Como aplicación directa e iterativa de la regla de actualización de concentrador y la regla de actualización de la autoridad conduce a valores divergentes, es necesario normalizar la matriz después de cada iteración. Así, los valores obtenidos a partir de este proceso en algún momento convergerán.^[3]

Pseudocódigo

 1 G := set of pages
 2 for each page p in G do
 3   p.auth = 1 // p.auth es la puntuación de autoridad de la página p
 4   p.hub = 1 // p.hub es la putuación de concentrador (Hub) de la página p
 5 function HubsAndAuthorities(G)
 6   for step from 1 to k do // correr k iteraciones
 7     norm = 0
 8     for each page p in G do  // actualizar las puntuaciones de autoridad primero
 9       p.auth = 0
10       for each page q in p.incomingNeighbors do // p.incomingNeighbors es el conjunto de páginas que enlazan con p
11          p.auth += q.hub
12       norm += square(p.auth) // calcular la suma de los cuadrados de las puntuaciones de autoridad para normalizar
13     norm = sqrt(norm)
14     for each page p in G do  // actualizar las puntuaciones de autoridad 
15       p.auth = p.auth / norm  // normalizar las puntuaciones de autoridad
16     norm = 0
17     for each page p in G do  // actualizar las puntuaciones de concentrador (Hub)
18       p.hub = 0
19       for each page r in p.outgoingNeighbors do // p.outgoingNeighbors es el conjunto de páginas enlazadas desde p
20         p.hub += r.auth
21       norm += square(p.hub) // calcular la suma de los cuadrados de las puntuaciones de concentrador (Hub) para normalizar
22     norm = sqrt(norm)
23     for each page p in G do  // actualizar las puntuaciones de concentrador (Hub)
24       p.hub = p.hub / norm   // normalizar las puntuaciones de concentrador (Hub)

Los valores de concentrador y de autoridad convergen en el pseudocódigo anterior.

El código siguiente no converge, porque es necesario limitar el número de pasos que ejecuta el algoritmo. Sin embargo, una manera de evitar esto sería normalizar los valores de los concentradores y de las autoridades después de cada "paso" dividiendo cada valor de autoridad por la raíz cuadrada de la suma de los cuadrados de todos los valores de autoridad y dividiendo cada valor de concentrador por la raíz cuadrada de la suma de los cuadrados de todos los valores de concentrador. Esto es lo que hace el pseudocódigo anterior.

Pseudocódigo no convergente

 1 G := set of pages
 2 for each page p in G do
 3   p.auth = 1 // p.auth es la puntuación de autoridad de la página p
 4   p.hub = 1 // p.hub es la putuación de concentrador (Hub) de la página p
 5 function HubsAndAuthorities(G)
 6   for step from 1 to k do // correr k iteraciones
 7     for each page p in G do  // actualizar las puntuaciones de autoridad primero
 8       p.auth = 0
 9       for each page q in p.incomingNeighbors do // p.incomingNeighbors es el conjunto de páginas que enlazan con p
10         p.auth += q.hub
11     for each page p in G do  // actualizar las puntuaciones de concentrador (Hub)
12       p.hub = 0
13       for each page r in p.outgoingNeighbors do // p.outgoingNeighbors es el conjunto de páginas enlazadas desde p
14         p.hub += r.auth

Véase también

PageRank

Referencias

↑ Christopher D. Manning, Prabhakar Raghavan & Hinrich Schütze (2008). «Introduction to Information Retrieval». Cambridge University Press. Consultado el 9 de noviembre de 2008.
↑ Kleinberg, Jon (December 1999). «Hubs, Authorities, and Communities». Cornell University. Consultado el 9 de noviembre de 2008.
↑ von Ahn, Luis (19 de octubre de 2008). «Hubs and Authorities» (PDF). 15-396: Science of the Web Course Notes. Carnegie Mellon University. Archivado desde el original el 19 de enero de 2015. Consultado el 19 de enero de 2015.