Skip to content
Voltar aos resultados

PageRank Ponderado (Weighted PageRank)

Proposto por
Xing, W. & Ghorbani, A.
Ano
2004
Tipo
Centrality measure / ranking algorithm
Família
Network science

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?

Weighted PageRank estende o algoritmo PageRank clássico para redes onde as arestas (edges) carregam diferentes forças ou frequências, distribuindo a importância proporcionalmente aos pesos das arestas de entrada e saída, em vez de tratar todos os links igualmente.

Isso o torna substancialmente mais informativo do que o PageRank binário em qualquer rede onde a força da conexão importa.

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

O PageRank clássico trata cada hiperlink ou ligação (tie) identicamente: um nó ganha prestígio igual de uma conexão fraca como de uma forte. Weighted PageRank corrige isso escalonando cada voto pelo peso relativo da aresta. Um nó que recebe muitas ligações de entrada de peso elevado de nós já importantes sobe mais alto no ranking, enquanto um nó com conexões numerosas, mas fracas, permanece modesto. Isso espelha como a influência realmente se acumula na maioria das redes do mundo real, onde a frequência de interação ou o volume de transações sinalizam a verdadeira importância.

História

O PageRank foi introduzido por Brin e Page em 1998 como a base do Google Search, tratando todos os hiperlinks como votos iguais. O Weighted PageRank foi formalizado por Xing e Ghorbani em 2004, estendendo o algoritmo para atribuir a distribuição de ranking proporcional aos pesos das arestas, baseando-se em frações de peso de entrada e saída. Desde então, tem sido aplicado em análise de citações, bioinformática, análise de redes sociais e sistemas de recomendação sempre que a força do link é um proxy significativo para influência.

Quando usar

Use Weighted PageRank quando sua rede tiver pesos de arestas significativos e você precisar de um ranking global de importância dos nós, sensível ao fluxo. É ideal para redes de citação com contagens de co-citação, grafos da web com volumes de tráfego, redes de interação biológica com níveis de expressão, redes sociais com frequências de interação e redes de transações financeiras. Prefira Weighted PageRank sobre o PageRank binário sempre que ignorar a força da aresta puder representar mal o fluxo de influência. Evite-o quando os pesos das arestas forem não confiáveis ou atribuídos arbitrariamente, quando a rede for muito esparsa e os pesos forem majoritariamente binários (PageRank simples é suficiente), ou quando você precisar de uma medida de centralidade puramente local, como o grau ponderado (weighted degree). Não é apropriado para redes não direcionadas onde a direção do fluxo é conceitualmente sem sentido.

Limitações e considerações

  • Requer que os pesos das arestas sejam significativos e medidos de forma confiável; pesos ruidosos ou arbitrários degradam a qualidade do ranking.
  • O fator de amortecimento (d) é um parâmetro livre; o valor convencional de 0.85 pode não ser ideal para redes não-web.
  • Sensível ao esquema de normalização de peso escolhido; os resultados podem diferir se os pesos de entrada e saída forem combinados de maneiras diferentes.
  • Não distingue entre diferentes tipos de arestas; um modelo de peso único pode colapsar distinções estruturais importantes.
  • A convergência pode ser lenta em redes muito grandes e densas sem implementações eficientes de matriz esparsa.

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

  • Incorpora a força da aresta diretamente na propagação da importância, fornecendo rankings mais realistas do que o PageRank binário em redes ponderadas.
  • Captura o prestígio global, de toda a rede, em vez de apenas a conectividade local.
  • Preserva o mecanismo de teletransporte do PageRank, tornando-o robusto contra nós pendentes e componentes desconectados quando corrigido.
  • Escala para grandes redes através de computação iterativa eficiente; operações de matriz esparsa mantêm a memória tratável.
  • Facilmente interpretável: uma pontuação alta significa que um nó recebe endosso pesado e ponderado de outros nós de alta pontuação.

Aplicações

  • Identificar artigos ou autores influentes em redes de citação e coautoria ponderadas.
  • Classificar páginas da web ou documentos quando o volume de tráfego de hiperlinks ou as taxas de cliques estão disponíveis.
  • Detectar proteínas ou genes-chave em redes de interação biológica ponderadas.
  • Priorizar nós em redes de transações financeiras pelo fluxo de volume de transações.
  • Classificar usuários ou conteúdo em grafos de interação de redes sociais ponderadas.
  • Construir sistemas de recomendação onde as frequências de co-ocorrência de itens servem como pesos de arestas.

Como funciona

Como funciona

1

Represente a rede como um grafo onde cada aresta carrega um peso numérico refletindo a força da ligação — como frequência de interação, volume de transações, contagem de coautoria ou pontuação de similaridade. O algoritmo exige que esses pesos sejam não negativos; pesos negativos devem ser transformados antes da análise.

2

Para cada aresta direcionada de v para u, calcule dois fatores de peso: um fator de peso de entrada (in-weight) normalizando o peso da aresta pelo peso total de entrada de u, e um fator de peso de saída (out-weight) normalizando-o pelo peso total de saída de v. Essas frações determinam quanta parte do ranking de v é distribuída para u através dessa aresta específica.

Fórmula
W_{in}(v,u) = \frac{w(v,u)}{\sum_{k \in In(u)} w(k,u)}, \quad W_{out}(v,u) = \frac{w(v,u)}{\sum_{k \in Out(v)} w(v,k)}
3

Aplique a fórmula do Weighted PageRank iterativamente: o ranking de cada nó é igual a um termo base de teletransporte (1 menos o fator de amortecimento d, tipicamente 0.85) mais d vezes a soma sobre todos os vizinhos de entrada de seus rankings escalonados pelos dois fatores de peso. Isso distribui o ranking proporcionalmente à força da aresta, em vez de uniformemente.

Fórmula
WPR(u) = (1-d) + d \sum_{v \in In(u)} WPR(v) \cdot W_{in}(v,u) \cdot W_{out}(v,u)
4

Repita a atualização do ranking até que a mudança na pontuação de cada nó caia abaixo de uma pequena tolerância (comumente 1e-6). A convergência é garantida para grafos fortemente conectados; para grafos com nós pendentes (dangling nodes) ou componentes isolados, aplique a correção padrão para nós pendentes antes de iterar.

5

Uma vez que as pontuações tenham convergido, ordene todos os nós por sua pontuação Weighted PageRank em ordem decrescente. Esses rankings refletem a importância estrutural global de cada nó, considerando tanto a topologia da rede quanto a força das arestas.

Erros comuns

  • Usar pesos de arestas brutos e não normalizados sem verificar sua escala — misturar contagens na casa das dezenas com valores em milhões distorce a propagação do ranking.
  • Esquecer de tratar nós pendentes (nós sem arestas de saída), que podem drenar o ranking de toda a rede se não corrigidos.
  • Assumir que o fator de amortecimento padrão de 0.85 é universalmente apropriado; em redes de citação ou biológicas, um valor diferente pode refletir melhor o domínio.
  • Interpretar pontuações de Weighted PageRank como probabilidades absolutas em vez de rankings relativos — apenas sua ordem é estável entre diferentes execuções.
  • Comparar pontuações de Weighted PageRank entre redes de tamanhos diferentes sem normalização.

Perguntas frequentes

Como o Weighted PageRank difere do PageRank padrão?

O PageRank padrão distribui o ranking de um nó igualmente para todos os seus vizinhos de saída, independentemente da força da aresta. O Weighted PageRank escala essa distribuição pelos pesos de entrada e saída relativos de cada aresta, de modo que conexões mais fortes carregam proporcionalmente mais ranking.

Qual fator de amortecimento devo usar?

O valor convencional é 0.85, derivado de suposições sobre o grafo da web sobre navegação aleatória. Para redes sociais, biológicas ou de citação, valores entre 0.5 e 0.9 são explorados na literatura. Recomenda-se análise de sensibilidade em uma faixa de valores de amortecimento.

O Weighted PageRank pode ser aplicado a redes não direcionadas?

Sim, representando cada aresta não direcionada como um par de arestas direcionadas com o mesmo peso. O algoritmo então produz fatores de peso de entrada e saída simétricos, o que se simplifica para uma fórmula que ainda respeita a força da aresta.

Como lidar com arestas de peso zero?

Arestas com peso zero não contribuem para a propagação do ranking, portanto, podem ser removidas antes da análise. Se pesos zero forem estruturalmente significativos (ausência versus dados ausentes), documente claramente a distinção antes de removê-los.

O Weighted PageRank é melhor do que a centralidade de grau ponderado (weighted degree centrality)?

Depende da questão de pesquisa. A centralidade de grau ponderado captura apenas conexões diretas, enquanto o Weighted PageRank captura o prestígio global propagado por toda a rede. Use o grau ponderado para influência local e o Weighted PageRank para importância em toda a rede.

Métodos relacionados

Fontes

  1. Xing, W., & Ghorbani, A. (2004). Weighted PageRank algorithm. Proceedings of the Second Annual Conference on Communication Networks and Services Research (CNSR '04), pp. 305–314. IEEE.

    Abrir referência DOI
    Copiado.
  2. PageRank. Wikipedia.

    Abrir referência da publicação
    Copiado.