Skip to content
Voltar aos resultados

Centralidade PageRank

Proposto por
Page, Brin, Motwani & Winograd
Ano
1999
Tipo
Iterative link-based centrality algorithm
Família
Centrality

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

PageRank é um algoritmo de centralidade baseado em links que atribui uma pontuação de importância a cada nó em um grafo direcionado, medindo quantos nós de alta qualidade apontam para ele.

Introduzido por Larry Page, Sergey Brin, Rajeev Motwani e Terry Winograd na Universidade de Stanford em 1999, tornou-se a base matemática do motor de busca Google e continua sendo um dos algoritmos mais influentes em ciência de redes e recuperação de informação.

A intuição por trás do método

Imagine um surfista aleatório na web que clica em links aleatoriamente, ocasionalmente saltando para uma página completamente aleatória em vez de seguir um link. A fração de tempo que este surfista passa em cada página, após infinitos cliques, é o PageRank dessa página. Uma página visitada com frequência — porque muitas páginas populares linkam para ela — recebe uma pontuação alta. O fator de amortecimento (tipicamente 0.85) modela a probabilidade de continuar clicando em vez de saltar.

História

PageRank foi desenvolvido na Universidade de Stanford por Larry Page e Sergey Brin como o mecanismo de classificação principal de seu projeto de busca BackRub, que se tornou Google em 1998. O relatório técnico fundamental, co-autorado com Rajeev Motwani e Terry Winograd, foi publicado em 1999. O algoritmo popularizou o uso de centralidade baseada em autovetores em redes direcionadas de larga escala e inspirou diretamente algoritmos subsequentes de análise de links, incluindo HITS e TrustRank.

Quando usar

PageRank é apropriado quando você precisa classificar nós em um grafo direcionado por importância estrutural global, especialmente quando a direção da aresta codifica endosso ou influência (hiperlinks, citações, seguidores sociais). Assume que o grafo pode ser modelado como uma cadeia de Markov e requer um componente conectado ou fortemente conectado para convergência limpa. É menos adequado para redes não direcionadas onde HITS ou centralidade de intermediação podem ser preferidos, e pode ser sensível a spam de links ou grau de entrada artificialmente inflado.

Limitações e considerações

  • Requer um grafo direcionado; a aplicação a redes não direcionadas necessita de escolhas de convenção
  • A velocidade de convergência depende do gap espectral da matriz de transição e pode ser lenta para grafos mal conectados
  • Sensível à escolha do fator de amortecimento d; valores diferentes podem alterar substancialmente as classificações
  • Vulnerável à manipulação por 'link farms' e links de entrada artificialmente construídos

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Fundamentação probabilística principiada via o modelo de cadeia de Markov do surfista aleatório
  • Escala para grafos muito grandes através de produtos esparsos matriz-vetor e iteração de potência
  • Captura a topologia global do grafo, recompensando nós endossados por outros nós de alta pontuação
  • Amplamente validado em domínios de redes web, de citação, biológicas e sociais

Aplicações

  • Classificação de motores de busca na web: ordenação de resultados de pesquisa pela autoridade global de páginas da web
  • Análise de citações acadêmicas: identificação de artigos ou periódicos influentes em redes de literatura científica
  • Medição de influência em redes sociais: classificação de usuários pelo prestígio de seus seguidores
  • Análise de redes biológicas: identificação de proteínas ou genes centrais em redes de interação proteica e regulação gênica
  • Sistemas de recomendação: propagação de sinais de preferência através de grafos bipartidos de usuários e itens

Como funciona

Como funciona

1

Todo nó no grafo começa com uma pontuação PageRank igual de 1/N, onde N é o número total de nós. Essa inicialização uniforme garante que nenhum nó tenha uma vantagem artificial e fornece uma distribuição de probabilidade válida em toda a rede antes da primeira iteração.

Fórmula
PR^{(0)}(v_i) = \frac{1}{N}, \quad \forall\, i \in \{1, \ldots, N\}
2

Uma matriz de transição estocástica por colunas M é construída a partir da estrutura de adjacência do grafo. Cada entrada M_ij é igual a 1 dividido pelo grau de saída do nó j se existir uma aresta de j para i, e zero caso contrário. Nós pendentes (sem arestas de saída) são tipicamente tratados redistribuindo sua pontuação uniformemente entre todos os nós.

Fórmula
M_{ij} = \begin{cases} \frac{1}{\text{out}(v_j)} & \text{if } (v_j \to v_i) \in E \\ 0 & \text{otherwise} \end{cases}
3

O vetor PageRank é atualizado iterativamente usando a fórmula do surfista aleatório. Com o fator de amortecimento d (padrão 0.85), cada nó recebe uma probabilidade base de teletransporte (1-d)/N mais d vezes a soma ponderada das pontuações contribuídas por todos os nós que linkam para ele. Esta etapa é repetida até que as pontuações se estabilizem.

Fórmula
PR^{(t+1)}(v_i) = \frac{1-d}{N} + d \sum_{v_j \in \mathcal{B}(v_i)} \frac{PR^{(t)}(v_j)}{\text{out}(v_j)}
4

Após cada iteração, a norma L1 da mudança no vetor de pontuação é comparada com uma pequena tolerância epsilon (por exemplo, 1e-6). Quando a mudança cai abaixo desse limite, o algoritmo convergiu e o vetor de pontuação atual é retornado como a distribuição PageRank final.

Fórmula
\left\| PR^{(t+1)} - PR^{(t)} \right\|_1 < \varepsilon

Erros comuns

  • Ignorar nós pendentes (nós sem arestas de saída) pode quebrar a propriedade estocástica da matriz de transição e causar pontuações incorretas
  • Usar PageRank em grafos não direcionados sem converter para um modelo de transição simétrico pode produzir estimativas de centralidade enganosas
  • Definir a tolerância muito frouxa leva à convergência prematura; muito apertada aumenta o cálculo sem mudanças significativas nas pontuações
  • Interpretar PageRank como uma métrica de importância absoluta em vez de uma classificação relativa dentro de um contexto de grafo específico

Perguntas frequentes

O que o fator de amortecimento d representa e como ele deve ser escolhido?

O fator de amortecimento d (tipicamente 0.85) é a probabilidade de que o surfista aleatório siga um link em vez de teleportar para um nó aleatório. Valores próximos a 1 tornam o algoritmo mais sensível à estrutura do grafo, mas mais lento para convergir e mais propenso a 'rank sinks'; valores próximos a 0 aproximam-se da classificação uniforme. O valor 0.85 foi validado empiricamente por Page e Brin para o grafo da web e é o padrão padrão.

Como o PageRank difere da centralidade de grau?

A centralidade de grau conta apenas o número direto de links de entrada para um nó, tratando todas as fontes igualmente. PageRank pondera cada link de entrada pela pontuação do nó que linka, de modo que um endosso de um nó altamente classificado contribui mais do que um de um nó de baixa classificação. Essa definição recursiva captura a estrutura global do grafo em vez de apenas a conectividade local.

O PageRank pode ser aplicado a grafos não direcionados?

Sim, mas com ressalvas. Um grafo não direcionado deve ser convertido para uma representação direcionada substituindo cada aresta não direcionada por duas arestas direcionadas. As pontuações PageRank resultantes são então iguais a uma função do grau do nó, reduzindo o algoritmo a uma centralidade de grau ponderada. Para redes não direcionadas, medidas de centralidade alternativas, como centralidade de autovetores ou centralidade de intermediação, são frequentemente mais informativas.

Métodos relacionados

Fontes

  1. Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report.

    Abrir referência da publicação
    Copiado.