Algoritmos PageRank e HITS

PageRank e HITS são algoritmos de análise de links que estimam a importância ou autoridade de páginas da web a partir da estrutura do grafo de hiperlinks, e não apenas do conteúdo da página.

Definition

PageRank atribui a cada página uma pontuação de importância independente de consulta igual à sua probabilidade estacionária sob um navegador aleatório que segue links de saída com uma probabilidade de amortecimento e se teletransporta de outra forma, enquanto HITS calcula, para um subgrafo dependente de consulta, pontuações de autoridade para páginas com conteúdo valioso e pontuações de hub para páginas que se ligam a boas autoridades, cada uma reforçando a outra.

Scope

Este tópico abrange os dois algoritmos fundamentais de análise de links: PageRank, uma medida de importância de página independente de consulta baseada em um modelo de "navegador aleatório" com teletransporte, e HITS, um esquema dependente de consulta que calcula pontuações de hub e autoridade que se reforçam mutuamente. Ele aborda as formulações subjacentes de caminhada aleatória e autovetor, o papel do amortecimento e teletransporte, convergência e variantes sensíveis ao tópico. Exclui como essas pontuações são combinadas com características de texto em uma classificação final, o que pertence à classificação de busca na web.

Core questions

• Como o modelo de navegador aleatório define o PageRank como uma distribuição estacionária?
• Por que um fator de amortecimento ou teletransporte é necessário para que o PageRank seja bem definido?
• Como as pontuações de hub e autoridade no HITS se reforçam mutuamente?
• Como essas pontuações são calculadas iterativamente e quando convergem?
• Como PageRank e HITS diferem em serem independentes de consulta versus dependentes de consulta?

Key concepts

• PageRank
• modelo de navegador aleatório
• fator de amortecimento e teletransporte
• distribuição estacionária / autovetor principal
• HITS
• hubs e autoridades
• pontuação independente de consulta vs. dependente de consulta
• iteração de potência e convergência

Key theories

Modelo de navegador aleatório PageRank

Modelar um navegador que segue links com probabilidade igual a um fator de amortecimento e, de outra forma, salta para uma página aleatória, produz uma cadeia de Markov cuja distribuição estacionária única pontua as páginas por visitação de longo prazo, fornecendo uma medida de importância estável e independente de consulta.

HITS hubs e autoridades

Dentro de um subgrafo focado em consulta, HITS atribui a cada página uma pontuação de autoridade proporcional às pontuações de hub das páginas que se ligam a ela e uma pontuação de hub proporcional às pontuações de autoridade das páginas às quais ela se liga, calculadas iterando essas relações mutuamente reforçadoras até a convergência.

Clinical relevance

PageRank foi central para o surgimento da busca em larga escala na web e permanece um ponto de referência conceitual para importância e autoridade em grafos. As ideias de análise de links generalizam-se além da web para redes de citação, influência em redes sociais, detecção de fraudes e recomendação, onde quer que links de endosso transmitam informações.

History

Em 1998 e 1999, duas propostas quase simultâneas mostraram que os hiperlinks codificam autoridade: HITS de Kleinberg e PageRank de Page e Brin. As pontuações do PageRank, independentes de consulta e calculadas globalmente, provaram ser adequadas para o serviço em escala da web e sustentaram um motor de busca líder, enquanto HITS influenciou a destilação de tópicos e pesquisas posteriores de classificação de grafos.

Key figures

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

Seminal works

• page1999
• kleinberg1999
• brin1998

Frequently asked questions

Qual é a diferença entre PageRank e HITS?

PageRank calcula uma única pontuação de importância independente de consulta para cada página a partir de todo o grafo da web antecipadamente, enquanto HITS calcula pontuações de hub e autoridade dependentes de consulta em um pequeno subgrafo construído em torno da consulta no momento da recuperação. PageRank se adapta mais facilmente ao serviço da web.

Por que o PageRank precisa de um fator de amortecimento?

Sem ele, o navegador aleatório poderia ficar preso em páginas sem links de saída ou em ciclos, e a distribuição estacionária poderia não ser única ou bem definida. A probabilidade de amortecimento (teletransporte) permite que o navegador salte ocasionalmente para uma página aleatória, garantindo uma pontuação única e bem comportada.