Algoritmo HITS

La búsqueda de temas inducida por hipervínculos ( HITS , por sus siglas en inglés; también conocida como hubs and authors ) es un algoritmo de análisis de enlaces que clasifica las páginas web, desarrollado por Jon Kleinberg . La idea detrás de Hubs and Authorities surgió de una idea particular sobre 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 en realidad no eran autoritativos en la información que contenían, sino que se usaban como compilaciones de un amplio catálogo de información que llevaba a los usuarios directamente a otras páginas autoritativas. En otras palabras, un buen hub representa una página que apunta a muchas otras páginas, mientras que una buena autoridad representa una página que está vinculada por muchos hubs diferentes. ^[1]

Por lo tanto, el esquema asigna dos puntuaciones a cada página: su autoridad, que estima el valor del contenido de la página, y su valor central, que estima el valor de sus enlaces a otras páginas.

Historia

En revistas

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 están repletas de numerosas citas, lo que hace que estas revistas tengan factores de impacto muy altos. Por lo tanto, al comparar dos revistas menos conocidas que han recibido aproximadamente la misma cantidad de citas, pero una de estas revistas ha recibido muchas citas de Science y Nature , esta revista debe tener una clasificación más alta. 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 relevancia en la Web, pero una página con muy pocos enlaces entrantes también puede ser destacada si dos de estos enlaces proceden de las páginas de inicio de sitios como Yahoo !, Google o MSN . Como estos sitios tienen una importancia muy alta pero también son motores de búsqueda , una página puede tener una clasificación mucho más alta que su relevancia real.

Algoritmo

Ampliación del conjunto raíz en un conjunto base

Pasos

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

Los valores de autoridad y de eje se definen en términos mutuos en una recursión mutua . Un valor de autoridad se calcula como la suma de los valores de eje escalados que apuntan a esa página. Un valor de eje 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 vinculadas.

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 de cada nodo que apunta a él. Es decir, se le otorga a un nodo una puntuación de autoridad alta al estar vinculado desde páginas que se reconocen como centros de información.
• Actualización del nodo central : se actualiza la puntuación central de cada nodo para que sea igual a la suma de las puntuaciones de autoridad de cada nodo al que apunta. Es decir, se le otorga una puntuación central alta a un nodo al vincularlo con nodos que se consideran autoridades en el tema.

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

• Comience con cada nodo que tenga una puntuación de centro y una puntuación de autoridad de 1.
• Ejecutar la regla de actualización de autoridad
• Ejecutar la regla de actualización del concentrador
• 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 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.

Comparación con PageRank

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

• Se procesa en un pequeño subconjunto de documentos "relevantes" (un "subgráfico enfocado" o conjunto base), en lugar del conjunto de todos los documentos como era el caso con PageRank.
• Depende de la consulta: la misma página puede recibir una puntuación de autoridad/centro diferente dado un conjunto base diferente, que aparece para una consulta diferente;
• Como corolario, debe ejecutarse en el momento de la consulta, no en el momento de la indexación, con la consiguiente caída de rendimiento que acompaña al procesamiento en tiempo de consulta.
• Calcula dos puntuaciones por documento (centro y autoridad) en lugar de una única puntuación;
• Los motores de búsqueda no lo utilizan habitualmente (aunque se dice que Teoma utiliza un algoritmo similar , que fue adquirido por Ask Jeeves/Ask.com ).

En detalle

Para comenzar la clasificación, dejamos y para cada página . Consideramos dos tipos de actualizaciones: Regla de actualización de autoridad y Regla de actualización de hub. Para calcular las puntuaciones de hub/autoridad de cada nodo, se aplican iteraciones repetidas de la Regla de actualización de autoridad y la Regla de actualización de hub. Una aplicación de k pasos del algoritmo Hub-Authority implica aplicar k veces primero la Regla de actualización de autoridad y luego la Regla de actualización de hub. ${\displaystyle \mathrm {auth} (p)=1}$ ${\displaystyle \mathrm {hub} (p)=1}$ ${\displaystyle p}$

Regla de actualización de autoridad

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

Regla de actualización del centro

Para cada , actualizamos dónde se encuentran todas las páginas a las que se vincula la página. 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 apunta. ${\displaystyle p}$ ${\displaystyle \mathrm {hub} (p)}$ ${\displaystyle \mathrm {hub} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {from} }}\mathrm {auth} (q)}$ ${\displaystyle P_{\mathrm {from} }}$ ${\displaystyle p}$

Normalización

Las puntuaciones finales de autoridad de los nodos se determinan después de infinitas repeticiones del algoritmo. Como la aplicación directa e iterativa de la regla de actualización de los nodos y la regla de actualización de la autoridad conduce a valores divergentes, es necesario normalizar la matriz después de cada iteración. Por lo tanto, los valores obtenidos a partir de este proceso eventualmente convergerán.

Pseudocódigo

G  := conjunto de páginas para cada página p en G  hacer  p .auth = 1 // p .auth es la puntuación de autoridad de la página p  p .hub = 1 // p .hub es la puntuación central de la página p para el paso de 1 a k hacer // ejecutar el algoritmo para k pasos norma = 0 para cada página p en G  hacer // actualizar primero todos los valores de autoridad p .auth = 0 para cada página q en p.incomingNeighbors  hacer // p.incomingNeighbors es el conjunto de páginas que se vinculan a p  p .auth += q .hub norm += square( p .auth) // Calcula la suma de los valores de autenticación al cuadrado para normalizar norma = sqrt(norma) para cada página p en G  hacer // actualizar los puntajes de autenticación p .auth = p .auth / norm // normalizar los valores de autenticación norma = 0 para cada página p en G  haga // luego actualice todos los valores del concentrador p .hub = 0 para cada página r en p.outgoingNeighbors  haga // p.outgoingNeighbors es el conjunto de páginas a las que p se vincula p .hub += r .auth norm += square( p .hub) // calcula la suma de los valores del eje al cuadrado para normalizar norma = sqrt(norma) para cada página p en G  hacer // luego actualizar todos los valores del hub p .hub = p .hub / norm // normalizar los valores del hub

Los valores del centro y de la autoridad convergen en el pseudocódigo anterior.

El código que se muestra a continuación no converge, ya que es necesario limitar la cantidad de pasos que se ejecutan en el algoritmo. Sin embargo, una forma de evitarlo sería normalizar los valores de hub y autoridad 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 hub por la raíz cuadrada de la suma de los cuadrados de todos los valores de hub. Esto es lo que hace el pseudocódigo anterior.

Pseudocódigo no convergente

G  := conjunto de páginas para cada página p en G  do  p .auth = 1 // p .auth es la puntuación de autoridad de la página p  p .hub = 1 // p .hub es la puntuación central de la página pfunción HubsAndAuthorities( G ) para el paso de 1 a k do // ejecuta el algoritmo para k pasos para cada página p en G  do // actualiza primero todos los valores de autoridad p .auth = 0 para cada página q en p.incomingNeighbors  do // p.incomingNeighbors es el conjunto de páginas que se vinculan a p  p .auth += q .hub para cada página p en G  do // luego actualiza todos los valores de hub p .hub = 0 para cada página r en p.outgoingNeighbors  do // p.outgoingNeighbors es el conjunto de páginas a las que p se vincula p .hub += r .auth

Véase también

• PageRank

Referencias

1. Christopher D. Manning; Prabhakar Raghavan; Hinrich Schütze (2008). "Introducción a la recuperación de información". Cambridge University Press . Consultado el 9 de noviembre de 2008 .
2. Kleinberg, Jon (diciembre de 1999). "Hubs, Authorities, and Communities". Universidad de Cornell . Consultado el 9 de noviembre de 2008 .

• Kleinberg, Jon (1999). "Fuentes autorizadas en un entorno hipervinculado" (PDF) . Revista de la ACM . 46 (5): 604–632. CiteSeerX  10.1.1.54.8485 . doi :10.1145/324133.324140. S2CID  221584113.
• Li, L.; Shang, Y.; Zhang, W. (2002). "Mejora de algoritmos basados ​​en HITS en documentos web". Actas de la 11.ª Conferencia Internacional sobre la World Wide Web (WWW 2002) . Honolulu, HI. ISBN 978-1-880672-20-4Archivado desde el original el 3 de abril de 2005. Consultado el 3 de junio de 2005 .{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )

Enlaces externos

• Patente estadounidense 6.112.202
• Crear un buscador de datos a partir de una base de datos relacional Motor de búsqueda en C# basado en HITS