Algoritmos PageRank y HITS

PageRank y HITS son algoritmos de análisis de enlaces que estiman la importancia o autoridad de las páginas web a partir de la estructura del grafo de hipervínculos, en lugar de basarse únicamente en el contenido de la página.

Definition

PageRank asigna a cada página una puntuación de importancia independiente de la consulta igual a su probabilidad estacionaria bajo un navegante aleatorio que sigue los enlaces salientes con una probabilidad de amortiguación y, de lo contrario, se teletransporta, mientras que HITS calcula, para un subgrafo dependiente de la consulta, puntuaciones de autoridad para páginas con contenido valioso y puntuaciones de 'hub' para páginas que enlazan a buenas autoridades, reforzándose mutuamente.

Scope

Este tema abarca los dos algoritmos fundamentales de análisis de enlaces: PageRank, una medida de importancia de página independiente de la consulta basada en un modelo de navegante aleatorio con teletransportación, y HITS, un esquema dependiente de la consulta que calcula puntuaciones de 'hub' y autoridad que se refuerzan mutuamente. Trata las formulaciones subyacentes de paseo aleatorio y vector propio, el papel del factor de amortiguación y la teletransportación, la convergencia y las variantes sensibles al tema. Excluye cómo estas puntuaciones se combinan con características de texto en una clasificación final, lo que pertenece a la clasificación de búsqueda web.

Core questions

• ¿Cómo define el modelo de navegante aleatorio a PageRank como una distribución estacionaria?
• ¿Por qué se necesita un factor de amortiguación o teletransportación para que PageRank esté bien definido?
• ¿Cómo se refuerzan mutuamente las puntuaciones de 'hub' y autoridad en HITS?
• ¿Cómo se calculan estas puntuaciones de forma iterativa y cuándo convergen?
• ¿En qué se diferencian PageRank y HITS en cuanto a ser independientes de la consulta o dependientes de la consulta?

Key concepts

• PageRank
• modelo de navegante aleatorio
• factor de amortiguación y teletransportación
• distribución estacionaria / vector propio principal
• HITS
• hubs y autoridades
• puntuación independiente de la consulta vs. dependiente de la consulta
• iteración de potencia y convergencia

Key theories

Modelo de navegante aleatorio de PageRank

Modelar a un navegante que sigue enlaces con una probabilidad igual a un factor de amortiguación y, de lo contrario, salta a una página aleatoria, produce una cadena de Markov cuya distribución estacionaria única puntúa las páginas por visitas a largo plazo, proporcionando una medida de importancia estable e independiente de la consulta.

HITS hubs y autoridades

Dentro de un subgrafo enfocado en la consulta, HITS asigna a cada página una puntuación de autoridad proporcional a las puntuaciones de 'hub' de las páginas que la enlazan y una puntuación de 'hub' proporcional a las puntuaciones de autoridad de las páginas a las que enlaza, calculadas iterando estas relaciones que se refuerzan mutuamente hasta la convergencia.

Clinical relevance

PageRank fue fundamental para el surgimiento de la búsqueda web a gran escala y sigue siendo un punto de referencia conceptual para la importancia y la autoridad en grafos. Las ideas de análisis de enlaces se generalizan más allá de la web a redes de citas, influencia en redes sociales, detección de fraude y recomendación, dondequiera que los enlaces tipo 'respaldo' transmitan información.

History

En 1998 y 1999, dos propuestas casi simultáneas mostraron que los hipervínculos codifican autoridad: HITS de Kleinberg y PageRank de Page y Brin. Las puntuaciones de PageRank, independientes de la consulta y calculadas globalmente, resultaron adecuadas para el servicio a escala web y sustentaron un motor de búsqueda líder, mientras que HITS influyó en la destilación de temas y en investigaciones posteriores sobre clasificación de grafos.

Key figures

• Larry Page
• Sergey Brin
• Jon Kleinberg
• Rajeev Motwani

Seminal works

• page1999
• kleinberg1999
• brin1998

Frequently asked questions

¿Cuál es la diferencia entre PageRank y HITS?

PageRank calcula una única puntuación de importancia independiente de la consulta para cada página a partir de todo el grafo web de antemano, mientras que HITS calcula puntuaciones de 'hub' y autoridad dependientes de la consulta en un subgrafo pequeño construido alrededor de la consulta en el momento de la recuperación. PageRank se escala más fácilmente para el servicio web.

¿Por qué PageRank necesita un factor de amortiguación?

Sin él, el navegante aleatorio podría quedar atrapado en páginas sin enlaces salientes o en ciclos, y la distribución estacionaria podría no ser única o estar bien definida. La probabilidad de amortiguación (teletransportación) permite al navegante saltar ocasionalmente a una página aleatoria, garantizando una puntuación única y bien comportada.