Algoritmo HITS

Se han utilizado muchos métodos para clasificar la importancia de las revistas científicas. Uno de ellos es el factor de impacto de Garfield . Revistas como Science y Nature reciben numerosas citas, lo que les confiere factores de impacto muy altos. Por lo tanto, al comparar dos revistas menos conocidas que han recibido aproximadamente el mismo número de citas, pero una de ellas ha recibido muchas citas de Science y Nature , esta última debe tener una clasificación más alta. En otras palabras, es mejor recibir citas de una revista importante que de una poco importante. ^{[ 2 ]}

Este fenómeno también ocurre en Internet . Contar el número de enlaces a una página nos permite estimar su relevancia en la web, pero una página con muy pocos enlaces entrantes también puede ser prominente si dos de ellos provienen de las páginas de inicio de sitios como Yahoo !, Google o MSN . Dado que estos sitios son muy importantes y, además, son motores de búsqueda , una página puede aparecer en una posición mucho más alta de lo que realmente le corresponde.

En el algoritmo HITS, el primer paso consiste en recuperar las páginas más relevantes para la consulta de búsqueda. Este conjunto se denomina conjunto raíz y se obtiene seleccionando las páginas principales devueltas por un algoritmo de búsqueda basado en texto . Se genera un conjunto base ampliando el conjunto raíz con todas las páginas web que enlazan desde él y algunas de las que enlazan con él. Las páginas web del conjunto base y todos los hipervínculos entre ellas forman un subgrafo enfocado. El cálculo HITS se realiza únicamente sobre este subgrafo enfocado . Según Kleinberg, el motivo para construir un conjunto base es asegurar que se incluyan la mayoría (o muchas) de las autoridades más importantes.

Los valores de autoridad y de hub se definen en términos mutuos mediante una recursión recíproca . Un valor de autoridad se calcula como la suma de los valores de hub escalados que apuntan a esa página. Un valor de hub 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 los nodos centrales que lo enlazan. Es decir, un nodo obtiene una puntuación de autoridad alta al ser enlazado desde páginas reconocidas como centros de información.
• Actualización del hub : Actualiza la puntuación de hub de cada nodo para que sea igual a la suma de las puntuaciones de autoridad de cada nodo al que apunta. Es decir, un nodo obtiene una puntuación de hub alta al enlazar con nodos que se consideran autoridades en el tema.

La puntuación del Hub y la puntuación de Autoridad para un nodo se calculan con el siguiente algoritmo:

• Comience con cada nodo teniendo una puntuación de hub y una puntuación de autoridad de 1.
• Ejecutar la regla de actualización de autoridad
• Ejecutar la regla de actualización del hub
• Normalice los valores dividiendo cada puntuación de Hub por la raíz cuadrada de la suma de los cuadrados de todas las puntuaciones de Hub, y dividiendo cada puntuación de Authority por la raíz cuadrada de la suma de los cuadrados de todas las puntuaciones de Authority.
• Repita desde el segundo paso según sea necesario.

HITS, al igual que PageRank de Page y Brin , es un algoritmo iterativo basado en la vinculación de los documentos en la web . Sin embargo, tiene algunas diferencias importantes:

• Se procesa sobre un pequeño subconjunto de documentos "relevantes" (un "subgrafo enfocado" o conjunto base), en lugar del conjunto de todos los documentos, como ocurría con PageRank.
• Depende de la consulta: la misma página puede recibir una puntuación de hub/autoridad diferente según el conjunto base, que aparece para una consulta diferente;
• Como consecuencia, debe ejecutarse en el momento de la consulta, no en el momento de la indexación, con la consiguiente disminución del rendimiento que conlleva el procesamiento en tiempo de consulta.
• Calcula dos puntuaciones por documento (centro y autoridad) en lugar de una sola puntuación;
• No es un algoritmo comúnmente utilizado por los motores de búsqueda (aunque se dice que Teoma , que fue adquirido por Ask Jeeves/Ask.com , utilizaba un algoritmo similar ).

Para cada${\displaystyle p}$actualizamos${\displaystyle \mathrm {autenticación} (p)}$a${\displaystyle \mathrm {auth} (p)=\displaystyle \sum \nolimits _ {q\in P_{\mathrm {to} }}\mathrm {hub} (q)}$dónde${\displaystyle P_{\mathrm {to} }}$son todas las páginas que enlazan a la página${\displaystyle p}$Es decir, la puntuación de autoridad de una página es la suma de todas las puntuaciones de hub de las páginas que enlazan a ella.

Para cada${\displaystyle p}$actualizamos${\displaystyle \mathrm {hub} (p)}$a${\displaystyle \mathrm {hub} (p)=\displaystyle \sum \nolimits _ {q\in P_{\mathrm {de} }}\mathrm {auth} (q)}$dónde${\displaystyle P_{\mathrm {desde} }}$son todas las páginas que página${\displaystyle p}$enlaces a. Es decir, la puntuación central de una página es la suma de todas las puntuaciones de autoridad de las páginas a las que enlaza.

Las puntuaciones finales de autoridad de los nodos se determinan tras un número infinito de repeticiones del algoritmo. Dado que la aplicación directa e iterativa de la Regla de Actualización de Hub y la Regla de Actualización de Autoridad produce valores divergentes, es necesario normalizar la matriz después de cada iteración. De este modo, los valores obtenidos mediante este proceso convergerán finalmente.