A matemática por trás do sucesso do Google

Introdução

Se pensarmos no que fez o Google se tornar uma ferramenta tão poderosa, desde que despontou, poderíamos pesquisar sobre o que estaria por trás do seu sucesso e ver que, talvez sejam os seus mais de um milhão de servidores em data-centers executando o software ao redor do mundo ou o seu corpo técnico tão qualificado composto por cientistas da computação e programadores.

Sim, certamente que toda esta estrutura o mantém como a ferramenta que é, sendo o website mais visitado do mundo [1], com o seu sistema de buscas processando cerca de 5 bilhões de solicitações de pesquisa por usuários todos os dias, e, sem mencionar todos os outros produtos e parcerias da marca.

Mas o diferencial do aplicativo, a ideia do núcleo inicial, que o tornou mais utilizado que todos os outros mecanismos de busca ainda nos anos 90 foi o seu algoritmo, denominado PageRank, desenvolvido pelos fundadores, Lawrence Page e Sergey Brin, quando ambos eram estudantes de doutorado na Universidade Stanford, e publicado no artigo "The Anatomy of a Large-Scale Hypertextual Web Search Engine".

O PageRank, de forma distinta dos demais mecanismos de busca da época, organiza os resultados de busca pela sua ordem de relevância. Ou seja, um resultado de pesquisa realizado no Google, que retorna uma quantidade incrível de páginas, centenas de milhares, apresenta geralmente os resultados mais relevantes ainda nas primeiras páginas.

Como este mecanismo sabe quais as páginas mais importantes? Atribuindo um número a cada página de forma a refletir esta importância. Esse número é o PageRank.

Vamos entender como calcular um dos algoritmos do Google, o PageRank, de forma simplificada, e mostrar como podemos utilizar um dos muitos métodos numéricos que vemos em Cálculo, o método iterativo de Gauss-Seidel para obtermos a solução.

Cálculo do PageRank

O PageRank original pode ser descrito pela seguinte equação [2]:                  

sendo:

• : PageRank da página
• : PageRank da página que aponta para a página , (isto é, citações)
• : número de links de saída (páginas que aponta)
• : fator de amortecimento (). Para o google, é utilizado o valor .

Note que o PageRank forma uma distribuição de probabilidade sobre as páginas web, logo a soma dos PageRank de todas as páginas é igual a 1.

Na Internet, como temos uma rede de conexões entre páginas, lidamos com um sistema de equações para calcularmos a ordem de relevância das páginas. Sim, caro leitor, calcular o PagRank de uma página equivale a resolver um sistema linear!

Método Iterativo de Gauss-Seidel

 O objetivo dos métodos iterativos [3] é encontrar a solução via processo iterativo para um sistema linear do tipo , sendo  a matriz dos coeficientes ; é o vetor de variáveis  e é o vetor dos termos constantes . Esse processo iterativo é interrompido até que uma condição de parada seja satisfeita – que a solução  atenda a uma precisão previamente estipulada (por exemplo, usando o teste do erro relativo). Computacionalmente, usamos também como condição de parada o número máximo de iterações.

O método de Gauss-Seidel trata-se de um processo iterativo que consiste em, sendo uma aproximação inicial, calcular a solução , ,..., por

Este processo iterativo é repetido até que o vetor  esteja suficientemente próximo do vetor . Medimos a distância entre  e  por .

Assim, para uma precisão , o vetor  será , chamado de solução aproximada, se .

Devo ressaltar aqui, como em todo processo iterativo, é necessário um critério que garanta a convergência do método. Cito o Critério de Sassenfeld ou o Critério das Linhas como os critérios utilizados.

Exemplo

Suponhamos que exista uma ‘’pequena Internet’’ e que uma expressão qualquer digitada no Google retorne 4 páginas: www.pagina1.com, www.pagina2.com, www.pagina3.com, www.pagina4.com, que referenciam umas às outras como ilustrado na figura abaixo:

Vamos traduzir a figura acima em um grafo, composto de 4 vértices. Quando a página relacionada ao vértice citar a página relacionada ao vértice , um arco direcionado irá representar esta conexão. Por exemplo, podemos ver que a página 4 cita a página 1, então esta conexão será representada por um arco com ponta inicial em 4 e ponta final em 1, e assim por diante.  Procedendo desta forma, construímos o grafo completo mostrado abaixo:

De acordo com o que fizemos no grafo, podemos substituir os dados na equação 2.  Analisando o grafo, para a página 1, temos:

• : PageRank da página ( é uma das variáveis a serem determinadas)
• é apontada por , e
• ; ;
• 

A primeira equação é então obtida:

As demais equações podem ser obtidas de maneira análoga, e deixo a cargo do leitor determina-las, como exercício.

Para resolver este sistema linear, vamos utilizar o método iterativo de Gauss-Seidel. Organizando o sistema, obtemos o processo iterativo que iremos simular, dado pela Equação (4):

Vamos adotar a aproximação inicial  e erro , para o qual a solução convergirá, após 31 iterações, para

A simulação foi realizada no Matlab – uma importante ferramenta computacional usada para implementação de algoritmos matemáticos, entre outras funcionalidades.

A partir do resultado, vemos que a soma de todos os PageRank é igual a 4. O maior PageRank é o da página 1, pois é apontada por 3 páginas. Apesar de  e serem referenciadas por 3 páginas cada, o que as diferencia é que  é apontada por páginas com maior PageRank ( pela própria página ).

O uso de métodos iterativos é mais indicado para este problema, ainda mais quando pensamos nas dimensões reais – a matriz G representa uma estrutura de ligações da web com cerca de  páginas, o que exige máquinas de grande armazenamento e processamento. O uso de métodos diretos é inviável para estas dimensões.

Apresentei a vocês um, dentre muitos, algoritmos do Google. Com o tempo, houveram aprimoramentos, para ser o que é hoje - são mais de 2 bilhões de linhas de código para que o Google funcione. Matematicamente, ressalto que há diversos outros aspectos que podem ser explorados.

Quer entender mais sobre programação matemática e métodos numéricos? Deseja saber como e onde são aplicados os diversos conceitos matemáticos? Me procure aqui no Profes! Será um prazer ajuda-los.

Abraço!

REFERÊNCIAS BIBLIOGRÁFICAS:

[1] Alexa Traffic Rank for Google (three month average). Alexa Internet. Consultado em 23 de julho de 2021.

[2] The Anatomy of a Large-Scale Hypertextual Web Search Engine, Computer Networks and ISDN Systems, Volume 30, Issues 1–7, Brin, S.; Page, L., April 1998, Pages 107–117, Proceedings of the Seventh International World Wide Web Conference.

[3] RUGGIERO, M,A,G, & LOPES, V,L,R. Cálculo Numérico: aspectos teóricos e computacionais, São Paulo, Pearson Makron Books, 1996, 406p.