Parte II · PageRank — a web como uma cadeia de Markov

draft

A cadeia de Markov mais consequente já construída tem um estado por página web. O algoritmo fundador do Google não inventou um novo tipo de matemática — ele notou que *ranquear a web é o mesmo problema que encontrar a distribuição estacionária de uma caminhada aleatória* (cap. 01, §4). Este capítulo é essa observação, tornada precisa.

1. A ideia: importância é onde um surfista aleatório se demora

Em 1996, os doutorandos de Stanford Larry Page e Sergey Brin iniciaram um projeto apelidado de "BackRub" — um motor que julgava uma página não pelas palavras nela mas pelos back links apontando para ela. Renomeado Google em 1997 (incorporado em setembro de 1998), ele se apoiava em um único modelo:

O surfista aleatório. Imagine alguém navegando para sempre. Em cada página, com probabilidade \(d\) ele clica em um link de saída uniformemente aleatório; com probabilidade \(1-d\) ele fica entediado e se teletransporta para uma página uniformemente aleatória em qualquer lugar da web. O PageRank de uma página é a fração de tempo de longo prazo que esse surfista passa nela. Páginas importantes são simplesmente aquelas às quais uma caminhada aleatória sempre retorna — porque muitas páginas apontam para elas, e porque as páginas que apontam para elas são elas mesmas importantes.

Essa última cláusula torna a definição recursiva (o rank de uma página depende dos ranks de seus linkadores), e essa recursão é exatamente o que uma distribuição estacionária resolve.

2. A matemática: rank = distribuição estacionária

Modele a web como um grafo dirigido: páginas são estados, hiperlinks são arestas. Seja \(L(i)\) o número de links de saída da página \(i\). O movimento do surfista depende apenas da página em que ele está atualmente — a propriedade de Markov. Sua matriz de transição é

\[M = d\,S + (1-d)\,\tfrac{1}{N}\,\mathbf{1},\]

onde \(S\) é a matriz de links (a massa de cada página dividida igualmente entre seus links de saída, com páginas "pendentes" sem saída remendadas para se teletransportar uniformemente) e \(N\) é o número de páginas. PageRank é a distribuição estacionária \(\pi\) de \(M\) — o vetor com \(\pi = M\pi\), equivalentemente o autovetor principal (autovalor 1) de \(M\). Escrito por página:

\[PR(p) = \frac{1-d}{N} + d \sum_{i \in \text{In}(p)} \frac{PR(i)}{L(i)}, \qquad d \approx 0.85.\]

Cada página entrega seu rank aos seus alvos, dividido igualmente; o termo \((1-d)/N\) é o teletransporte. (O artigo original de 1998 escreveu o teletransporte como \((1-d)\); a forma normalizada \((1-d)/N\) acima é a que torna os ranks uma distribuição de probabilidade genuína somando 1.)

Por que o fator de amortecimento não é opcional. O grafo de links bruto é uma cadeia de Markov quebrada: tem ilhas desconectadas, sumidouros de rank e nós pendentes que vazam probabilidade — então pode não ter uma distribuição estacionária única e bem definida. O termo de teletransporte \((1-d)\) torna toda entrada de \(M\) estritamente positiva, o que torna a cadeia irredutível e aperiódica. Pelo teorema de Perron–Frobenius tal cadeia tem uma distribuição estacionária única com entradas estritamente positivas, e a caminhada converge para ela a partir de qualquer início. O amortecimento é o truque que transforma um grafo malformado numa cadeia à qual o teorema fundamental se aplica.

Como é computado — iteração de potência. Comece de um vetor uniforme e aplique \(M\) repetidamente: \(\pi_{k+1} = M\pi_k\). Isso é rodar a caminhada aleatória em agregado; converge geometricamente (a taxa fixada pelo segundo autovalor, limitado por \(d=0.85\)), então algumas dezenas de iterações bastam mesmo na escala da web. O sistema inicial rodava isso sobre cerca de 24 milhões de páginas e centenas de milhões de links.

Brin, S. & Page, L. (1998). *The Anatomy of a Large-Scale Hypertextual Web Search Engine.* WWW7 / Computer Networks 30:107–117. Page, L., Brin, S., Motwani, R. & Winograd, T. (1999). *The PageRank Citation Ranking: Bringing Order to the Web.* Stanford InfoLab TR SIDL-WP-1999-0120.

3. Por que superou a web de 1998

A concorrência ranqueava páginas por palavras-chave na página (AltaVista, Excite, Lycos, Infoseek) ou por diretórios curados por humanos (o Yahoo! Directory). O ranqueamento por palavra-chave tratava toda página como igualmente autoritativa e era trivialmente spammado por enchimento de palavras-chave; diretórios não conseguiam escalar com o crescimento da web. O PageRank contribuiu com um escore de importância independente de consulta derivado do próprio grafo de links — a própria estrutura de hipertexto da web lida como uma gigantesca rede de citações — que é muito mais difícil de falsificar: você não pode se tornar importante meramente alegando ser, apenas conseguindo que páginas importantes apontem para você. Combinado com a indexação de texto-âncora, esse foi o salto.

4. O padrão generaliza

O PageRank é uma instância de um movimento reutilizável: codifique "importância" ou "relevância" como a distribuição estacionária de uma caminhada que você projeta, então leia a resposta no ponto fixo. A mesma construção impulsiona o PageRank personalizado, caminhadas de recomendação sobre grafos usuário–item, ranqueamento de citação e confiança, e recuperação baseada em grafos. Sempre que um sistema ranqueia nós por "quanto uma caminhada aleatória os favorece", ele está computando uma distribuição estacionária — a matemática idêntica que amostra física em Monte Carlo & MCMC e prevê texto no Compêndio de IA.

Por que importa pra Stack

A Stack roda suas próprias superfícies de busca e recuperação — busca de pacotes do Koder Hub, recuperação do kode-rag, ranqueamento cross-repo. Qualquer sinal de linkcitaçãografo que essas incorporem num ranqueamento é, formalmente, uma distribuição estacionária no estilo PageRank sobre uma caminhada nos próprios grafos da Stack. Este capítulo é o solo enciclopédico; a decisão de ranqueamento de um componente (qual grafo, qual amortecimento, quais sinais) é uma escolha de engenharia que o cita, conforme a regra referência-vs-decisão do compêndio.

Fontes

Brin, S. & Page, L. (1998). The Anatomy of a Large-Scale Hypertextual Web Search Engine. WWW7; Computer Networks and ISDN Systems 30:107–117.
Page, L., Brin, S., Motwani, R. & Winograd, T. (1999). The PageRank Citation Ranking: Bringing Order to the Web. Stanford InfoLab Technical Report SIDL-WP-1999-0120.
Perron–Frobenius theorem and the random-surfer/teleportation formulation (standard references; cf. Langville & Meyer, Google's PageRank and Beyond, Princeton, 2006).