PageRank™ é um algoritmo utilizado pela ferramenta de busca Google para posicionar websites entre os resultados de suas buscas. O PageRank mede a importância de uma página contabilizando a quantidade e qualidade de links apontando para ela. Não é o único algoritmo utilizado pelo Google para classificar páginas da internet, mas é o primeiro utilizado pela companhia e o mais conhecido. Suas propriedades são muito discutidas por especialistas em optimização dos motores de busca ([[SEO]], sigla em [[língua inglesa|inglês]] para ”search engine optimization”). O processo do PageRank foi [[patente]]ado pela [[Universidade de Stanford]] nos [[Estados Unidos]] sob o número 6.285.999. Somente o nome PageRank é uma [[marca registrada]] do [[Google]]. O Google tem os direitos de licença exclusivos sobre a patente de PageRank. A universidade de Stanford recebeu 1,8 milhão de ações do Google em troca do uso da patente. As ações foram vendidas em 2005 por 336 milhões de dólares . ==Descrição == Na construção da métrica de PageRank, a web é vista como uma rede de citações, cada nó corresponde a uma página e cada ligação corresponde a uma referência de uma página para outra (hiperligação). A métrica atribuí um valor a cada nó (página) da rede, um valor maior corresponde a um nó mais importante na rede. Do ponto de vista da teoria das redes, PageRank é uma métrica de centralidade. Esta métrica tira partido da estrutura de hiperligações na web para produzir o valor para cada página da rede. Uma hiperligação a uma página conta como um “voto” de suporte. O valor de PageRank de uma página depende do número de páginas e da métrica PageRank dessas páginas que aponta para si. Uma página tem um valor mais alto de PageRank se: * existem muitas página a apontar para si * existem algumas páginas a apontar para si com uma métrica de PageRank alta (uma página é importante se páginas importantes apontarem para si) [[Image:PageRanks-Example.svg|right|thumb|400px|Métrica PageRank para os nós de uma rede simples, expressos em percentagens. (O Google usa uma escala logarítmica). O nó C tem um valor de PageRank mais elevado do que o nó E, apesar de existirem poucas ligações para C, a ligação para C vem de um nó importante e, portanto, tem um valor elevado. Se um utilizador começar num nó aleatório com uma probabilidade de 85% de escolher uma ligação aleatória a partir do nó que está a visitar no momento, e uma probabilidade de 15% de saltar para um nó escolhido aleatoriamente de toda a rede, esse utilizador vai chegar ao nó E 8,1% das vezes. (A probabilidade de 15% de saltar para um nó arbitrário corresponde a um fator de amortecimento de 85%). Sem amortecimento, qualquer utilizador acabariam nos nós A, B, ou C, e todos os outros teriam o valor zero para PageRank. Através da utilização do fator de amortecimento, o nó A está ligado a todos os nós da rede, mesmo que não tenha ligações para outros nós.]] == Google e o PageRank == O sistema PageRank é usado pelo motor de busca [[Google]] para ajudar a determinar a relevância ou importância de uma página. Foi desenvolvida pelos fundadores do Google, [[Larry Page]] e [[Sergey Brin]] enquanto cursavam a [[Universidade de Stanford]] em [[1998]]. O [[Google]] mantém uma lista de bilhões de páginas em ordem de importância, isto é, cada página tem sua importância na Web como um todo; esse Banco de Páginas mantém desde a página mais importante do mundo até a menos importante. Essa importância se dá pelo número de votos que uma página recebe. Um voto é um ”[[link]]” em qualquer lugar da Web para aquela página. Votos de páginas mais importantes valem mais do que votos de páginas menos importantes. Esse critério de ordenação das páginas, de acordo com várias pessoas, é bastante democrático, reflectindo o que a “Web pensa” sobre determinado termo. Lembre-se que cerca de dez bilhões de páginas são levadas em conta. A [[qualidade]] das páginas mais importantes são naturalmente garantidas, classificadas e eleitas pela própria Web. Além de todas as páginas terem a mesma condição de subir nessa lista, conquistando votos pela Web afora. Uma boa unidade de medida para definir o PageRank de uma página pode ser a percentagem (%) de páginas que ela é mais importante. Por exemplo, se uma página tem PageRank de 33% significa que ela é mais importante que um terço de toda a Web. Se o seu PageRank é 99% significa que ela é superior a quase todas as páginas da Web. No entanto, é possível manipular o PageRank atribuindo ”links” descontextualizados com o objectivo da página, modificando a ordenação de resultados na pesquisa pelo Google e induzindo a resultados pouco relevantes ou tendenciosos. Um exemplo recente disso é a pesquisa por [[Google:failure|failure]] ou [[Google:miserable+failure|miserable failure]] que retornava como primeiro site a biografia oficial da [[Casa Branca]] para o presidente dos [[Estados Unidos]], [[George W. Bush]] e em sequência a página de [[Michael Moore]], inimigo declarado do presidente dos EUA. Este processo ficou conhecido por ”[[Google bomb|Googlebombing]]”. Apesar disso, o Google tem removido alguns resultados decorrentes de “Googlebombing”. == História == PageRank foi desenvolvido na [[Stanford University|Universidade de Stanford]] por [[Larry Page]] (daí o nome Page Rank ) e [[Sergey Brin]] em 1996 , no contexto de um projeto de investigação sobre um novo tipo de motor de busca . Sergey Brin teve a ideia de que a informação na web poderiam ser ordenada numa hierarquia de “popularidade de ligações”: Uma página é mais importante se tiver mais hiperligações a apontar para si. Foi co-autoria de Rajeev Motwani e Winograd Terry. O primeiro artigo sobre o projeto, descrevendo a métrica PageRank e o protótipo inicial do motor de busca Google, foi publicado em 1998. Logo depois, Page e Brin fundaram a Google Inc., a empresa por trás do motor de busca Google. A métrica PageRank foi inspirada na análise de citações, desenvolvida por Eugene Garfield em 1950 na Universidade da Pensilvânia, e pelo método “Hyper Search”, desenvolvido por Massimo Marchiori, da Universidade de Pádua. No mesmo ano, foi introduzido o PageRank (1998), Jon Kleinberg publicou seu trabalho sobre HITS . Os fundadores do Google citaram Marchiori, e Kleinberg no seu artigo original . Um motor de busca chamado “RankDex” da IDD Information Services, desenhado por Robin Li, desde 1996, já explorava uma estratégia semelhante para pontuação e ranking de páginas . A tecnologia utilizada em RankDex foi patenteada em 1999 e usada mais tarde quando Li fundou a Baidu na China. O trabalho de Li está referenciado em algumas patentes, de métodos de pesquisa do Google, de Larry Page. == O algoritmo == A métrica PageRank de uma página representa a probabilidade de uma pessoa chegar a essa página, clicando aleatoriamente em hiperligações. O cálculo de PageRank é escalável, ou seja, é executável em tempo útil se aumentarmos consideravelmente o número de páginas da rede. O cálculo de PageRank é iterativo, ou seja, exige várias passagens, chamadas de “iterações”, os valores obtidos em cada iteração convergem para os valores desejados de PageRank. Na primeira iteração é atribuído um valor de PageRank inicial igual para todas as páginas (N é o número total de páginas). === O algoritmo simplificado === Imagine uma rede de apenas 4 páginas ”’A”’, ”’B”’, ”’C”’ e ”’D”’. As ligações de uma página a si própria e as ligações múltiplas entre duas páginas são ignoradas. Inicialmente, a soma dos valores de PageRank de todas as páginas da web correspondia ao número de páginas na web. Em versões posteriores, o PageRank, passou a assumir valores entre 0 e 1, representando uma distribuição probabilística, ou seja, a probabilidade de um utilizador, percorrendo ligações aleatoriamente, chegue a uma determinada página. No primeiro passo do processo de cálculo iterativo do PageRank, todas as páginas têm o mesmo valor de PageRank. No nosso exemplo de 4 páginas, o primeiro passo consiste em atribuir o valor 0,25 de PageRank a cada uma das quatro páginas. Note-se que a soma dos valores de PageRank de todas as páginas é 1. [[File:Simple 4 nodes graph 3 nodes link to one.jpg|thumb|center|alt=Fig. 1- Todas as páginas têm apenas uma referência para a página A.|Fig. 1- Todas as páginas têm apenas uma referência para a página A.]] Numa rede com a configuração da figura em cima, na segunda iteração, cada ligação transfere o valor 0,25 para o PageRank de A, ou seja: : [[File:Pagerank.pt.fig2.jpg|thumb|center|alt=Fig. 2- Páginas que referenciam mais de uma página|Fig. 2- Páginas que referenciam mais de uma página.]] No caso da rede em cima, na segunda iteração, o valor de ”’B”’ é transferido metade para ”’A”’ (0,125) e outra metade para ”’C”’ (0,125). Como ”’D”’ referencia 3 páginas, o seu valor a transferir é dividido por três, neste caso o PageRank de ”’A”’ recebe os seguintes valores. : Portanto, a contribuição de uma ligação para o PageRank da página referenciada, é igual ao valor de PageRank da página com a ligação, dividido pelo número de ligações que a página contém. Se representarmos por L() o número de ligações de uma página, podemos reescrever a expressão em cima, para a nossa rede de 4 páginas: : Generalizando, o valor de PageRank para uma página u pode ser expresso da seguinte forma: : O valor de PageRank de uma página ”’u”’, depende dos valores de PageRank de cada página ”’v”’ contida no conjunto ”’Bu”’ (conjunto de todas as páginas que referenciam ”’u”’), dividido pelo número de referências ”L”(”v”) existentes em ”’v”’. === Páginas sem ligações === O processo iterativo de cálculo de PageRank encontra problemas quando uma página não tem ligação a outras páginas. [[File:Pagerank.pt.fig3.jpg|thumb|center|alt=Fig. 3- Página sem ligação|Fig. 3- Página sem ligação.]] Se for aplicado o cálculo à rede da figura anterior, acabamos por obter o valor zero para ambas as páginas ”’A”’ e ”’B”’ . Em cada iteração, ”’B”’ recebe algum do PageRank de ”’A”’ (neste caso particular ”’B”’ recebe todo o PageRank de ”’A”’, mas numa rede mais complexa onde ”’A”’ tivesse ligações a outras páginas, ”’B”’ receberia apenas uma parte do PageRank), mas como ”’B”’ não tem ligações, não passa o seu valor a outras páginas, neste caso ”’A”’. Isto produz um efeito de drenagem do PageRank para fora da rede. === Ciclo (rank sink) === Outro problema encontrado no cálculo do PageRank acontece quando uma rede contém um ciclo (rank sink). [[File:Pagerank.pt.fig4.jpg|thumb|center|alt=Fig. 4- Exemplo de um ciclo (rank sink)|Fig. 4- Exemplo de um ciclo (rank sink).]] Considere-se um ciclo fechado de páginas ligadas entre si, mas que nenhuma das páginas ligue a uma página fora do ciclo. Num cenário destes, o cálculo do PageRank fica “preso” no ciclo infinito, em cada iteração o valor de PageRank é transmitido de uma página para outra do ciclo, sem nunca distribuir o valor para páginas fora do ciclo e sem que os valores convirjam para valores estacionários de PageRank. === Fator de amortecimento === Os problemas acima descritos são resolvidos por um conceito introduzido pelo PageRank e designado por fator de amortecimento. A teoria de PageRank considera que um utilizador (ou surfista) imaginário que siga as ligações entre as páginas, aleatoriamente, acabará por se aborrecer e parar de seguir as ligações. A probabilidade, em cada passo, de o utilizador continuar a seguir as ligações é o fator de amortecimento ”’d”’. O fator de amortecimento, sendo uma probabilidade, pode variar entre 0 e 1. Desta forma o valor de ”’PR(A)”’ passa a ter uma componente correspondente à contribuição das páginas que apontam para ”’A”’, ponderado pela probabilidade ”’d”’ do utilizador seguir as ligações das páginas: : e uma componente correspondente ao utilizador ter selecionada a página aleatoriamente ponderado pela probabilidade de o utilizador não seguir as ligações das páginas (1-d) : Com a introdução do fator de amortecimento ”’d”’, o cálculo do valor de PageRank, passa a ter a seguinte expressão, representa o número total de páginas: : Existem outras variantes para o cálculo de PageRank, mas a expressão em cima tem a particularidade de a soma dos valores de PageRank de todas as páginas ser 1. Obtém-se desta forma uma distribuição probabilística, ou seja, a probabilidade de um utilizador chegar à página A. O fator de amortecimento introduz as seguintes características no cálculo de PageRank: * Uma página, pelo simples facto de existir, tem uma probabilidade igual a todas as outras de ser selecionada pela escolha aleatória de um utilizador * Uma página que não tenha ligações está ligada a todas as páginas da rede * Resolução dos problemas de páginas sem ligações e ciclos (rank sink). O fator de amortecimento ”’d”’ pode assumir valores entre zero e 1, como já foi indicado. Com ”’d”’ = 1, passamos à forma simplificada do algoritmo, com ”’d”’ = 0, não é atribuído nenhum peso à estrutura de hiperligações entre páginas da rede, todas as páginas ficam com o valor de PageRank igual a , onde é o número de páginas da rede. Portanto, quanto mais próximo estiver ”’d”’ de 1, maior é o peso dado á estrutura da rede. É normalmente atribuído o valor 0,85 para o fator de amortecimento . === Representação matricial === Assumindo que a rede é constituída pelas páginas ”’P1”’, ”’P2”’, …, ”’Pn”’, ”’M(Pi)”’ representa o conjunto de páginas que referenciam ”’Pi”’, ”’L(Pj)”’ representa o número de referências na página ”’Pj”’. A expressão para o cálculo do valor de PageRank, pode ser reescrito da seguinte forma: : (*) O vetor ”’R”’ que contém o valor de PageRank para todas das páginas pode ser representado da seguinte forma : Construindo uma matriz de transição ”’M”’ de nxn, onde n é o número total de páginas, um elemento ”’Mij”’ (linha ”’i”’ e coluna ”’j”’) é dado pela função : :, se não existe referência da página ”’pj”’ para a página ”’pi”’ :, se existe referência da página ”’pj”’ para a página ”’pi”’, : é o número de referências existentes em ”’pj”’ (grau de saída ou número de ligações que saem de ”’pj”’) :Note-se que a função está normalizada, ou seja : A expressão para o cálculo de PageRank para todas as páginas, pode ser escrita da seguinte forma matricial: : Se representarmos por 1 o vector de uns, com o valor 1 em todos os elementos, com n linhas e uma coluna, temos: :. Um vez que a soma de todos os elementos do vetor ”’R”’ é 1 (ou seja ”’PR(P1)+PR(P2)+…PR(Pn)”’ = 1 ), então o produto de ”’R”’ pela matriz ”’E”’ nxn, com o valor 1 em todos os seus elementos, é igual ao vetor ”’1”’, Portanto, podemos reescrever a expressão para o cálculo de R, da seguinte forma: : Colocando ”’R”’ em evidência, obtemos: : Ou seja, ”’R”’ é o vetor próprio da matriz de adjacências modificada , para o valor próprio 1, onde: : Portanto, a métrica PageRank pode ser vista como uma variante da métrica de centralidade de vetor próprio. === Cálculo iterativo da métrica PageRank === Vamos designar por ”’x(0)”’ os valores iniciais de PageRank e por ”’x(t)”’ os valores calculados de PageRank na iteração ”’t”’. Na primeira iteração ”’t=0”’, é atribuído o valor a todas as páginas, ou seja, cada elemento do vetor ”’x(0)”’ tem o valor: : Em cada iteração ”’t+1”’, calculamos o valor de ”’x(t+1)”’ multiplicando a matriz pelo vetor ”’x(t)”’ ( valores de PageRank calculados na iteração anterior): : A matriz tem as seguintes propriedades: * irredutível * primitiva * estocástica Com base nestas propriedades de , prova-se que ”’x(t)”’ converge para o vetor próprio ”’R”’ . O cálculo iterativo termina quando a variação de x(t) para x(t+1), é menor que um determinado valor pré-definido: : Esta forma de cálculo é escalável, numa rede com 322 milhões de ligações, verifica-se uma convergência, com uma tolerância razoável, em aproximadamente 52 iterações . A velocidade de convergência, neste método de cálculo depende do valor de amortecimento ”’d”’ . == Determinar o PageRank == Para verificar o PageRank de uma determinada página existem duas opções: * Instalar a [[Google Toolbar]]
