4 - Grafos e Machine Learning: Como funciona o PageRank

O PageRank (PR) é, essencialmente, centralidade de autovetor com um ajuste inteligente para lidar com direção (um link de A para B não é o mesmo que de B para A) e com nós sem saída (páginas sem nenhum link, que "vazariam" toda a pontuação da rede se não fossem tratadas à parte).

A fórmula:

N é o número total de nós da rede.

A fórmula tem duas partes:

representa o "piso" que todo nó recebe automaticamente, não importa quantos links tenha. Representa a chance de o "surfista aleatório" se cansar e teletransportar direto para aquele nó, ignorando a estrutura de links da rede.

a soma dos votos que chegam de outros nós que apontam para i (o j→i significa "para todo j que tem um link indo para i").

O fator de amortecimento α = 0,85 modela um "surfista aleatório": 85% do tempo, ele segue um link da página atual; 15% do tempo, ele se entedia e "teletransporta" para uma página qualquer da web. A divisão de PR(j) pelo grau de saída de j é o que penaliza spam: se uma página tem 1.000 links de saída, cada um recebe só 1/1000 do seu prestígio, generosidade indiscriminada dilui influência. Entretanto, escolher o α é uma decisão de negócio, não só matemática. O Google escolheu 0,85 porque a web tem muitos links, mas em redes pequenas, esse valor pode não ser ideal.

Para exemplificar como a fórmula funciona vamos construir um exemplo bem pequeno, com 3 páginas, para deixar as duas partes da fórmula visíveis lado a lado, com números reais.

A rede: 3 páginas

Links: A → B, A → C, B → C, C → A.

Grau de saída: grau(A)=2, grau(B)=1, grau(C)=1.

Valores reais de PageRank (calculados via networkx): 

PR(A) = 0,3878, PR(B) = 0,2148, PR(C) = 0,3974.

Vamos calcular a mão PR(C), separando as duas partes da fórmula:

Parte 1, o piso de teletransporte (a chance de o surfista se cansar e cair direto em C, ignorando todos os links):

Parte 2, a soma dos votos que chegam a C (de A e de B, cada um diluído pelo próprio grau de saída):

que bate  com o valor real calculado pelo networkx.

O processo como uma eleição em cascata

Uma forma útil de visualizar o cálculo é através de uma rede pequena, de 6 nós, onde o nó 6 é um hub dominante, conectado a quase todos os outros. É importante notar que essa rede é direcionada, cada seta representa uma conexão com sentido único e peso próprio. Isso significa que a conexão de "2 para 1" pode ter um peso diferente da conexão de "1 para 2", e o mesmo vale para qualquer outro par de nós. Não é uma simplificação, é a mesma lógica que o PageRank usa na web real, onde um link de A para B não implica nada sobre um link de B para A.

O cálculo funciona em dois estágios diferentes.

Estágio 1 → Iteração 1 (voto direto ponderado): cada nó soma os pesos das conexões que chegam até ele, exatamente como mostrado na figura acima.

O nó 1 recebe peso 1,5 do nó 2 e peso 2,5 do nó 6:

1,5 + 2,5 = 4,0.

O nó 6 recebe pesos de cinco vizinhos diferentes:

(2,0 + 1,5 + 1,0 + 0,5 + 0,8) = 5,8.

Estágio 2 → Iterações 2 e 3 (cascata simples): a partir daqui, o cálculo muda de natureza. Cada nó não volta a usar os pesos originais das setas, em vez disso, soma diretamente as pontuações que os vizinhos alcançaram na rodada anterior. Os pesos da Iteração 1 já cumpriram seu papel, moldando quem começa "na frente", a partir daqui, o que importa é de quantos vizinhos bem pontuados cada nó recebe voto, rodada após rodada.

Por exemplo, a Iteração 2 do nó 1 não volta a somar 1,5 e 2,5. Em vez disso, soma o que os nós 2 e 6 alcançaram na Iteração 1:

Iteração₂(1) = Iteração₁(2) + Iteração₁(6) = 5,5 + 5,8 = 11,3

E assim sucessivamente, a Iteração 3 soma os resultados da Iteração 2, não os pesos originais de novo.

É por isso que o nó 6 (hub) dispara na frente: ele já começa a Iteração 1 recebendo votos de cinco vizinhos diferentes, enquanto o nó 5 (periférico) só recebe de um. Essa vantagem inicial se amplifica a cada rodada da cascata, o nó 5, mesmo conectado ao hub, termina com pontuação baixa (0,39), porque sua única conexão não é suficiente para compensar isso.

Um detalhe que poucos sabem: em redes não direcionadas, o PageRank não diz nada de novo

Esse é um resultado elegante e pouco intuitivo: se todos os links forem bidirecionais, a distribuição estacionária do passeio aleatório é simplesmente proporcional ao grau do nó:

PageRank(i) ∝ grau(i)

Ou seja, numa rede não direcionada, o PageRank não adiciona informação alguma além do que a centralidade de grau já mostrava. Todo o poder do algoritmo vem justamente da assimetria: capturar quem cita quem, quem segue quem, quem linka para quem, relações que só existem numa direção.

A função pagerank()

A função pagerank() da biblioteca networkx, em Python, calcula automaticamente o vetor de PageRank de todos os nós de um grafo, resolvendo internamente a equação de autovalor que vimos acima, sem que você precise programar as iterações manualmente.

O que ela faz, por baixo do pano

Dado um grafo (direcionado ou não), a função:

• Constrói a matriz de transição da rede, baseada em quem aponta para quem, e no grau de saída de cada nó.

• Aplica a fórmula

• repetidamente, começando com uma distribuição inicial (geralmente uniforme, PR(i) = 1/N para todo mundo), até os valores pararem de mudar significativamente entre uma iteração e a próxima (esse processo de repetir até estabilizar chama-se "iteração de potência", power iteration, o mesmo método numérico usado para encontrar autovetores dominantes em geral).

• Devolve um dicionário (ou estrutura equivalente), com o PageRank final de cada nó, valores que somam 1 no total.

Isso reproduz exatamente o exemplo do artigo, sem você precisar resolver o sistema de equações lineares na mão.

Os parâmetros principais que ela aceita

• alpha: o fator de amortecimento α, com 0,85 como padrão, o mesmo valor usado pelo Google originalmente.

• personalization: permite substituir a teletransportação uniforme ((1 − α)/N igual para todo mundo) por uma distribuição customizada, essa é a base do "PageRank personalizado" mencionado no artigo, usado em sistemas de recomendação, onde a teletransportação favorece páginas relacionadas ao interesse específico de um usuário, não qualquer página aleatória.

• max_iter e tol: controlam quantas iterações rodar, e qual a tolerância de convergência antes de parar, já que, na prática, o algoritmo não roda infinitamente, ele para quando a mudança entre iterações fica menor que um limiar.

• weight: se as links do grafo tiverem pesos (não só existência de link, mas uma intensidade), esse parâmetro permite que o PageRank leve esse peso em conta na divisão de importância, não só o grau de saída bruto.

Por que vale entender a matemática, mesmo usando a função pronta

Como você já viu no gancho do post, se você só chama nx.pagerank(G) sem entender a lógica por trás, é fácil interpretar mal o resultado, por exemplo, rodar a função numa rede não direcionada esperando um resultado sofisticado, sem perceber que o resultado vai ser essencialmente proporcional ao grau de cada nó, porque é exatamente isso que a matemática garante nesse caso específico.

Código: PageRank do zero, numa rede pequena

A rede com as 5 conexões rotuladas, e o PageRank real de cada nó.

Repare que esta rede não é puramente direcionada: existe uma conexão de mão dupla entre os nós 0 e 2 (0→2 e 2→0), misturada com três conexões de mão única (0→1, 1→2, 3→0). Isso é comum em redes reais, poucas redes são inteiramente simétricas ou inteiramente assimétricas, e é justamente essa mistura que o PageRank sabe processar sem dificuldade, ao contrário da centralidade de grau simples.

O nó 0 vence porque recebe votos por dois caminhos diferentes: diretamente do nó 2 (2→0) e do nó 3 (3→0). O nó 2 fica logo atrás, recebendo do nó 0 e do nó 1. Mas o resultado mais revelador está no fundo da tabela: o nó 3, apesar de ter grau 1 (só emite um link, para o nó 0), termina com o menor PageRank de todos, 0,0375. Esse número não é coincidência: é exatamente o piso de teletransporte da fórmula.

Para o nó 3, a fórmula geral se reduz a:

Substituindo α = 0,85 e N = 4 (o número de nós na rede):

Ou seja, o nó 3 não recebe nenhum voto de verdade de ninguém na rede, sua pontuação inteira vem só da fração de probabilidade que todo nó recebe automaticamente, pelo simples fato de existir (a chance de o "surfista aleatório" teletransportar direto para ele, ignorando todos os links). Um nó pode emitir quantos links quiser; se não recebe nenhum de volta, ele fica preso nesse piso mínimo, a estrutura da rede, não a contagem de links de saída, decide quem ganha importância.

Rode o código, mude o alpha para 1,0 e veja o que acontece com o nó 3 (dica: ele zera, porque o teletransporte some). Depois, mude o grafo para não direcionado e veja o ranking virar uma simples contagem de graus.

Continue essa jornada matemática

Na Parte 5 desta série, vamos ver o conceito do PageRank aplicado aum Sistema de Recomendação.

No Volume III, Redes, da coleção Matemática para o Século XXI, desenvolvo os conceitos em detalhes.