Algoritmo de golpes

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 páginas web, desarrollado por Jon Kleinberg . La idea detrás de Hubs and Authority 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 centros, servían como grandes directorios que en realidad no tenían autoridad en la información que contenían, sino que se utilizaban 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 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 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 más oscuras que han recibido aproximadamente el mismo número de citas, pero una de estas revistas ha recibido muchas citas de Science y Nature , esta revista necesita 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 se da en Internet . Contar el número de enlaces a una página puede darnos una estimación general de su prominencia 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

Expandir el conjunto raíz a 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. 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 enlazan con él. Las páginas web del conjunto base y todos los hipervínculos entre esas páginas forman un subgrafo enfocado. El cálculo de HITS se realiza únicamente en este subgrafo enfocado . Según Kleinberg, la razón para construir un conjunto base es garantizar que la mayoría (o muchas) de las autoridades más fuertes estén incluidas.

Los valores de autoridad y centro se definen en términos mutuos en una recursión mutua . Un valor de autoridad se calcula como la suma de los valores centrales escalados que apuntan a esa página. Un valor central 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 centro de cada nodo que apunta a él. Es decir, a un nodo se le otorga una puntuación de autoridad alta al estar vinculado desde páginas reconocidas como centros de información.
• Actualización del centro : actualice la puntuación del centro 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 alta al vincularse a nodos que se consideran autoridades en el tema.

La puntuación del centro y la puntuación de la autoridad para un nodo se calcula con el siguiente algoritmo:

• Comience con cada nodo con una puntuación de centro 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 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 el PageRank

HITS, al igual que el 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 "subgrafo 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 centro/autoridad 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 caída asociada en el rendimiento que acompaña al procesamiento en el momento de la consulta.
• Calcula dos puntuaciones por documento (centro y autoridad) en lugar de una puntuación única;
• Los motores de búsqueda no lo utilizan habitualmente (aunque se dice que Teoma , que fue adquirido por Ask Jeeves/Ask.com ), utilizó un algoritmo similar.

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 centro. Para calcular las puntuaciones de centro/autoridad de cada nodo, se aplican iteraciones repetidas de la regla de actualización de autoridad y la regla de actualización de centro. 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 hub. ${\displaystyle \mathrm {auth} (p)=1}$ ${\displaystyle \mathrm {hub} (p)=1}$ ${\displaystyle p}$

Regla de actualización de autoridad

Para cada uno , actualizamos dónde están todas las páginas que enlazan con 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 concentrador

Para cada uno , actualizamos dónde están todas las páginas a las que enlaza. 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 central 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 del centro 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 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 hacer // ejecutar el algoritmo para k pasos norma = 0 para cada página p en G  do // actualiza 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 norma += cuadrado ( p .auth) // calcula la suma de los valores de autenticación al cuadrado para normalizar norma = raíz cuadrada (norma) para cada página p en G  hacer // actualizar las puntuaciones de autenticación p .auth = p .auth / norm // normalizar los valores de autenticación norma = 0 para cada página p en G  do // luego actualice todos los valores del hub p .hub = 0 para cada página r en p.outgoingNeighbors  do // p.outgoingNeighbors es el conjunto de páginas que p vincula a p .hub += r .auth norma += cuadrado ( p .hub) // calcula la suma de los valores del centro al cuadrado para normalizar norma = raíz cuadrada (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 de centro y autoridad convergen en el pseudocódigo anterior.

El siguiente código no converge porque es necesario limitar la cantidad 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 la raíz cuadrada de la suma de los cuadrados de todos los valores del centro. 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 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 a p  p .auth += q .hub para cada página p en G  do // luego actualiza todos los valores del 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 enlaza p .hub += r .auth

Ver también

• Rango de página

Referencias

1. Christopher D. Manning; Prabhakar Raghavan; 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 .
2. Kleinberg, Jon (diciembre de 1999). "Centros, autoridades y comunidades". Universidad de Cornell . Consultado el 9 de noviembre de 2008 .

• Kleinberg, Jon (1999). "Fuentes autorizadas en un entorno de hipervínculos" (PDF) . Revista de la ACM . 46 (5): 604–632. CiteSeerX  10.1.1.54.8485 . doi :10.1145/324133.324140. S2CID  221584113.
• 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) . Honolulú, Hola. ISBN 978-1-880672-20-4. Archivado desde el original el 3 de abril de 2005 . Consultado el 3 de junio de 2005 .{{cite book}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace )

enlaces externos

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