domingo, 22 de novembro de 2009

CALCULANDO A BUSCA NO GOOGLE

JOSÉ LUIZ PASTORE MELLO, graduado e mestre pela USP, professor de matemática do colégio Santa Cruz, escreve na FOLHA interessante artigo sobre como o GOGLE ordena as buscas.

De acordo com levantamentos recentes, em outubro de 2009 a internet registrou um total de 230 milhões de sites. Nesse oceano de informação, endereços de busca como Google, Yahoo e AltaVista necessitam ordenar os sites de acordo com a sua importância.
Por exemplo, se você digitar no Google a palavra "folha", o primeiro site listado será a Folha Online, e isso não se deve a uma predileção do Google pela Folha Online, mas sim ao fato de que o site é classificado com alto PageRank ou PR, um índice que mede o grau de "importância" da página. O PR é uma medida do número de links direcionados para uma determinada página. O cálculo do PR de um site é um problema essencialmente matemático, como veremos a seguir.
Imaginemos uma web com apenas três sites, A, B e C. Chamaremos de PR(A), PR(B) e PR(C) o PageRank dos sites A, B e C, respectivamente. O Google utiliza a seguinte fórmula para o cálculo do PR de um site X dessa nossa microweb de apenas três sites: PR(X)=0,15+0,85.K, onde K é a soma dos quocientes de PR dos sites que compõem a web (exceto o site X) e dispõem de link indicando X, pelo número de links indicados em cada um desses sites (links para quaisquer sites da web). Entenderemos melhor o uso dessa fórmula através de três exemplos.
No exemplo 1, para o cálculo de PR(A) temos K=0, porque nem B nem C indicam links para o site A. Nesse caso, temos PR(A)=0,15.
No mesmo exemplo 1, PR(B)=0,15+0,85.[PR(A)/1]. No cálculo de PR(B), o valor de K leva em conta apenas PR(A), porque A é o único site que indica link para B; e PR(A) está sendo dividido por 1 porque A faz uma única indicação de link na web. Finalmente, PR(C)=0,15+0,85.[PR(B)/1], por razões análogas ao caso anterior. Para determinar PR(B) e PR(C), basta resolver o sistema de equações, o que resultará PR(B)=0,2775 e PR(C)=0,385875.
Nesse caso, obtivemos PR(A)PR(B)PR(C), o que sugere uma ordenação razoável da importância dos três sites se analisarmos com atenção a configuração dessa web.
No exemplo 2 temos uma configuração de web onde A, B e C têm a mesma importância. O sistema de equações a ser resolvido é: PR(A)=0,15+0,85.[PR(C)/1], PR(B)=0,15+0,85.[PR(A)/1] e PR(C)=0,15+0,85.[PR(B)/1], cuja solução será PR(A)=PR(B)=PR(C)=1, tal qual o esperado.
No exemplo 3, as equações são as seguintes: PR(A)=0,15+0,85.[PR(B)/1], PR(B)=0,15+0,85.[PR(A)/2 +PR(C)/1] e PR(C)=0,15+0,85.[PR(A)/2], cuja solução é: PR(A) 1,1634, PR(B)1,1922 e PR(C)0,6444. O site B tem maior PR porque é apontado pelos outros dois sites, e o site A fica em segundo lugar porque é apontado por B, que é o site de maior PR.
Saindo da nossa microweb de três sites para a web real, com mais de 230 milhões de sites, o calculo do PR de um site por sistemas de equações é absolutamente intratável, mesmo se forem usados supercomputadores. Na web real, a determinação do PR de um site é feita por aproximação usando as mesmas ideias aqui apresentadas, mas através de cálculos iterativos.

Nenhum comentário: