O Algoritmo de US$ 2 Trilhões É Só Uma Pergunta Recursiva
Existe uma pergunta que parece ingênua, mas esconde toda a matemática por trás do Google: quem são minhas conexões?
Não "quantas conexões eu tenho" — isso é fácil de responder, e é exatamente o que a centralidade de grau mede. A pergunta mais rica, e mais difícil, está escondida numa armadilha lógica: para saber o quão importante você é, preciso saber o quão importantes são suas conexões. Mas para saber o quão importantes são suas conexões, preciso saber o quão importantes são as conexões delas. E assim por diante, infinitamente.
Isso é o que torna a pergunta recursiva: a resposta depende da própria resposta, aplicada a outra parte da rede. Não existe um jeito de calcular "de fora para dentro" — a única saída é definir a importância de todo mundo simultaneamente, como um sistema que se resolve sozinho quando as pontuações param de mudar. É exatamente esse quebra-cabeça circular, formalizado em matemática rigorosa, que fundou uma empresa de trilhões de dólares.
O problema real: medir importância sem intervenção humana
Em 1998, Larry Page e Sergey Brin, então estudantes de doutorado em Stanford, enfrentavam um problema concreto: como ordenar milhões de páginas da web por importância, sem que um humano precisasse avaliar cada uma manualmente? A resposta deles partiu de uma ideia simples — um link de A para B é um voto de confiança de A em B. Mas nem todo voto vale o mesmo: um link do jornal Estado de São Paulo (que raramente linka para qualquer coisa) carrega muito mais peso do que mil links de um diretório automático de spam.
A matemática: da centralidade de grau ao autovetor
Centralidade de Grau
A forma mais simples de medir importância de um nó é contar conexões — a centralidade de grau:
onde:
: centralidade de grau do nó x
: número de links conectadas ao nó x
: número total de nós
A centralidade de grau mede a centralidade de um nó. Ela calcula a importância ou influência de um nó com base no número de links diretos que ele possui com outros nós na rede.
Em redes sociais, ela representa popularidade — o número de seguidores diretos ou contatos.
Uma celebridade pode ter uma centralidade de grau extremamente alta: milhões de conexões diretas que permitem que a informação se espalhe instantaneamente. No entanto, isso não significa que eles são os indivíduos mais estrategicamente posicionados — apenas que são altamente conectados. O posicionamento estratégico em uma rede não diz respeito apenas ao número de conexões. Veremos que outras medidas, como a betweenness centrality capturam quão bem um nó conecta diferentes grupos ou a rapidez com que pode alcançar todos os outros.
Uma pessoa com menos conexões, mas posicionada como uma ponte entre comunidades, pode ser mais influente na formação dos fluxos de informação.
Centralidade de autovetor (eigenvector)
Mas essa métrica trata todos os links igualmente, mesmo que se conectem a nós irrelevantes. A centralidade de autovetor resolve isso ponderando as conexões: um nó conectado a nós influentes ganha pontuação mais alta, recursivamente — sua importância depende da importância de seus vizinhos.
Antes de prosseguir, vale definir a ferramenta que sustenta tudo o que segue. Uma matriz de adjacência é uma forma de representar uma rede inteira como uma tabela de números: se a rede tem nós, a matriz tem tamanho , e cada posição indica se existe uma conexão entre o nó e o nó — tipicamente se existe um link, caso contrário.
Para a rede de três nós do próximo exemplo (nó 1 conectado a 2 e 3; nós 2 e 3 sem conexão entre si), a matriz de adjacência é:
Lendo a primeira linha: o nó 1 (, não conecta consigo mesmo) se conecta ao nó 2 () e ao nó 3 (). A segunda linha mostra que o nó 2 só se conecta ao nó 1 (), e assim por diante.
Repare que essa matriz é simétrica () porque a rede não é direcionada — cada link vale nos dois sentidos. Em redes direcionadas (como veremos no PageRank), essa simetria desaparece: um link de A para B não implica um link de B para A, e a matriz reflete isso diretamente.
Aqui entramos no que é o coração de toda uma área da álgebra linear chamada autovalores e autovetores (eigenvectors e eigenvalues), com aplicações que vão muito além de redes (aparece em física, em sistemas dinâmicos, em reconhecimento de padrões). Desenvolvi a intuição completa por trás disso, com a dedução matemática passo a passo, num artigo à parte: "O Que Significa Multiplicar um Vetor e Ele Não Mudar de Direção?" — vale a leitura complementar se quiser entender o mecanismo por completo.
Para a nossa rede de exemplo — três nós, onde o nó 1 se conecta aos nós 2 e 3, mas 2 e 3 não se conectam entre si — a solução dessa equação dá o autovetor (já normalizado):
O nó 1 emerge com centralidade quase 1,4 vezes maior que os nós 2 e 3 — não porque tenha "mais" conexões em algum sentido absoluto, mas porque é o único ponto de ligação entre os outros dois. A centralidade de autovetor transforma a pergunta "quantas conexões?" em "quem são minhas conexões?".
PageRank: a mesma ideia, adaptada para redes direcionadas
O PageRank é, 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).
O fator de amortecimento 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 pelo grau de saída de é 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.
O processo como uma eleição em cascata
Uma forma útil de visualizar o cálculo: imagine uma rede de 6 nós, onde o nó 6 é um hub dominante (peso inicial 2,5), conectado a quase todos os outros.
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 — soma . O nó 6 recebe pesos de cinco vizinhos diferentes (2,0 + 1,5 + 1,0 + 0,5 + 0,8) — soma .
Estágio 2 → Iterações 2 e 3 (cascata simples): a partir daqui, cada nó soma diretamente as pontuações da rodada anterior dos seus vizinhos — sem reaplicar os pesos originais. Por exemplo, a Iteração 2 do nó 1 é simplesmente — os pesos (1,5 e 2,5) já cumpriram seu papel na primeira rodada, moldando quem começa "na frente"; a partir daí, o que importa é de quantos vizinhos bem pontuados cada nó recebe voto, rodada após rodada.
Nó | Iteração 1 | Iteração 2 | Iteração 3 |
1 | 4,0 | 11,3 | 34,3 |
2 | 5,5 | 13,8 | 43,1 |
6 | 5,8 | 20,5 | 52,0 |
É 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ó —
A rede abaixo mostra 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.
O nó 3, com grau de entrada zero (ninguém aponta para ele), fica com o menor PageRank de todos (0,0375) — exatamente o piso mínimo de teletransporte. O fato de ele emitir um link (grau de saída 1) não altera em nada sua própria pontuação; grau de saída só determina quanto um nó repassa aos outros, nunca quanto recebe.
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.
Onde isso se conecta na coleção
Volume I (Ferramentas Fundamentais): o PageRank é, literalmente, o cálculo do autovalor principal de uma matriz — a mesma álgebra linear de autovalores e autovetores desenvolvida ali.
Volume III (Redes): centralidade — de grau, proximidade, intermediação e autovetor — é o arcabouço central deste volume; o PageRank é o caso mais famoso e mais aplicado dessa família de métricas.
Volume IV (Modelos Baseados em Agentes): o "surfista aleatório" que segue links com probabilidade 0,85 e teletransporta com probabilidade 0,15 é, na prática, um agente individual seguindo uma regra de decisão simples — o comportamento coletivo (o ranking de toda a web) emerge dessa regra repetida bilhões de vezes.
Para fechar
O PageRank não é só o algoritmo que fundou uma empresa de trilhões de dólares — é a prova de que uma pergunta recursiva simples ("quem são minhas conexões, e quem são as conexões delas?") pode ser formalizada em matemática rigorosa e aplicada em escala planetária. A mesma lógica, note bem, funciona igualmente bem para identificar super-disseminadores numa rede de contágio epidemiológico, ou o porto mais crítico numa cadeia de suprimentos global — a estrutura matemática é a mesma; só a interpretação do que é um "link" muda.
Este artigo faz parte da coleção Matemática para o Século XXI — onde conectamos a matemática do século XXI aos desafios reais do mercado, sem fórmulas assustadoras, mas sem simplificações vazias.
Comentários