La búsqueda de temas inducida por hipervínculos ( HITS ; también conocida como centros y autoridades ) es un algoritmo de análisis de enlaces que califica las páginas web, desarrollado por Jon Kleinberg . La idea detrás de Hubs and Authorities 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 en realidad no tenían autoridad en la información que tenían, pero se usaban como compilaciones de un amplio catálogo de información que conducía a los usuarios directamente a otras páginas autorizadas. En otras palabras, un buen centro 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 centros diferentes.[1]
Por lo tanto, 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 centro, 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 esos métodos 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 poco conocidas que han recibido aproximadamente el mismo número de citas, pero una de estas revistas ha recibido muchas citas de Science and 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 sin importancia. [2]
En la red
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 puede tener una clasificación mucho más alta que su relevancia real.
Algoritmo
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. Un conjunto base se genera aumentando el conjunto raíz con todas las páginas web que están vinculadas desde él y algunas de las páginas que lo enlazan. Las páginas web en el 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 básico es garantizar que se incluya a la mayoría (o muchas) de las autoridades más fuertes.
Los valores de autoridad y de concentrador se definen en términos uno del otro en una recursividad mutua . Un valor de autoridad se calcula 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 : actualice la puntuación de autoridad de cada nodo para que sea igual a la suma de las puntuaciones del concentrador de cada nodo que apunta a él. Es decir, un nodo recibe una puntuación de autoridad alta al estar vinculado desde páginas que se reconocen como Hubs para obtener información.
- Actualización del concentrador : actualice la puntuación del 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 otorga una puntuación de concentrador alta al vincularse a nodos que se consideran autoridades en el tema.
La puntuación de Hub y la puntuación de Autoridad para un nodo se calcula con el siguiente algoritmo:
- Comience con cada nodo con una puntuación de concentrador y una puntuación de autoridad de 1.
- Ejecute la regla de actualización de autoridad
- Ejecute la regla de actualización del concentrador
- Normalice los valores dividiendo cada puntaje de Hub por la raíz cuadrada de la suma de los cuadrados de todos los puntajes de Hub y dividiendo cada puntaje de Autoridad por la raíz cuadrada de la suma de los cuadrados de todos los puntajes de Autoridad.
- Repita desde el segundo paso según sea necesario.
HITS, como Page y el PageRank de Brin , es un algoritmo iterativo basado en el enlace de los documentos en la web . Sin embargo, tiene algunas diferencias importantes:
- Depende de la consulta, es decir, las puntuaciones (Hubs y Authority) resultantes del análisis de enlaces están influenciadas por los términos de búsqueda;
- Como corolario, se ejecuta en el momento de la consulta, no en el momento de la indexación, con el impacto asociado en el rendimiento que acompaña al procesamiento en el momento de la consulta.
- Los motores de búsqueda no suelen utilizarlo. (Aunque se dijo que Teoma usaba un algoritmo similar , que fue adquirido por Ask Jeeves / Ask.com ).
- Calcula dos puntuaciones por documento, centro y autoridad, en contraposición a una única puntuación;
- Se procesa en un pequeño subconjunto de documentos 'relevantes' (un 'subgrafo enfocado' o conjunto base), no todos los documentos como fue el caso con PageRank.
En detalle
Para comenzar el ranking, dejamos y para cada página . Consideramos dos tipos de actualizaciones: regla de actualización de autoridad y regla de actualización de concentrador. Para calcular los puntajes de centro / autoridad de cada nodo, se aplican iteraciones repetidas de la Regla de actualización de autoridad y la Regla de actualización del concentrador. Una aplicación de k pasos del algoritmo Hub-Authority implica aplicar k veces primero la regla de actualización de la autoridad y luego la regla de actualización del concentrador.
Regla de actualización de autoridad
Para cada , actualizamos a dónde son 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.
Regla de actualización del concentrador
Para cada , actualizamos a dónde son todas las páginas cuya página 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 apunta.
Normalización
Los puntajes finales de autoridad de hub de los nodos se determinan después de infinitas repeticiones del algoritmo. Dado que la aplicación directa e iterativa de la regla de actualización del 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 de este proceso eventualmente convergerán.
Pseudocódigo
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 p para paso de 1 a k do // ejecutar el algoritmo para k pasos norma = 0 para cada página p en G do // actualice 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 enlazan con 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 do // actualiza las puntuaciones de autenticación p .auth = p .auth / norm // normaliza los valores de autenticación norma = 0 para cada página p en G do // luego actualice todos los valores de concentrador p .hub = 0 para cada página r en p.outgoingNeighbors do // p.outgoingNeighbors es el conjunto de páginas que p enlaza con p .hub + = r .auth norm + = square ( p .hub) // calcula la suma de los valores del cubo al cuadrado para normalizar norma = sqrt (norma) para cada página p en G do // luego actualice todos los valores del concentrador p .hub = p .hub / norm // normalice los valores del concentrador
Los valores de centro y autoridad convergen en el pseudocódigo anterior.
El siguiente código no converge, porque es necesario limitar el número de pasos que ejecuta el algoritmo. Sin embargo, una forma de evitar esto sería normalizar los valores de centro 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 centro por el raíz cuadrada de la suma de los cuadrados de todos los valores del eje. 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 pfunction HubsAndAuthorities ( G ) para el paso de 1 a k do // ejecutar el algoritmo para k pasos para cada página p en G do // actualizar todos los valores de autoridad primero p .auth = 0 para cada página q en p.incomingNeighbors do // p.incomingNeighbors es el conjunto de páginas que enlazan con p p .auth + = q .hub para cada página p en G do // entonces actualizar todos los valores de cubo p .hub = 0 para cada página r en p.outgoingNeighbors hacer // p.outgoingNeighbors es el conjunto de páginas que p enlaza con p .hub + = r .auth
Ver también
Referencias
- ^ Christopher D. Manning, Prabhakar Raghavan y Hinrich Schütze (2008). "Introducción a la recuperación de información" . Prensa de la Universidad de Cambridge . Consultado el 9 de noviembre de 2008 .Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ Kleinberg, Jon (diciembre de 1999). "Hubs, autoridades y comunidades" . 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 .
- Pequeño.; Shang, Y .; Zhang, W. (2002). "Mejora de algoritmos basados en HITS en documentos web" . Actas de la 11ª Conferencia Internacional World Wide Web (WWW 2002) . Honolulu, HI. ISBN 978-1-880672-20-4.