Introdução ao Algoritmo PageRank do Google com o R: uma Aplicação de Autovalores/Autovetores e Cadeias de Markov
Prof. Adriano Azevedo Filho (azevedofilho@usp.br)
Conteúdo
1 - Descrição do problema: ranking de sites na internet
2 - O algoritmo PageRank da Google
3 - Análise teórica da matriz estocástica P
4 - Detalhes da implementação do PageRank
5 - Implementação completa do PageRank no R com exemplo numérico
6 - Conclusão
7 - Referências1 - Descrição do problema - ranking de sites na internet
Achar o site certo, que atenda ao interesse do internauta por algum assunto específico é algo muito valioso na internet. Até 1997/98, a melhor tecnologia para esse fim era fornecida pelo site Altavista. Essa tecnologia se baseava em três pilares que podem ser sintetizados por:
uso de programas (webcrawlers) para percorrer os sites da internet, cadastrando todas as palavras e os links existentes, de forma recursiva;
cadastramento e organização das palavras em índices, ligando essas palavras ao endereço dos sites;
realização de um ranking da importância ou popularidade relativa de cada site que contém as pesquisadas, apresentando ao interessado os sites na ordem do ranking obtido.
O Altavista avançou bastante nos 2 primeiros pilares mas a solução proposta para o terceiro pilar não era a mais adequado. Em pouco tempo, diversos mecanismos foram criados para iludir o processo de elaboração do ranking, diminuido com isso o valor das sugestões de sites oferecidos pelo Altavista.
A solução mais definitiva para o terceiro pilar dos mecanismos de busca veio em 1997/98 com a proposta do algoritmo PageRank desenvolvido por Larry Page e Sergey Brin, fundadores de uma pequena empresa, recém-criada, chamada Google. Em pouco mais de 10 anos, o Google se tornou uma das 10 maiores empresas do mundo, com um valor de mercado próximo de 270 bilhões de dólares em 2013. Grande parte seu sucesso se deveu à qualidade de seu mecanismo para estabelecer o ranking de importância de sites sugeridos para os usuários, fundamentado no algoritmo PageRank, que será descrito nos próximos tópicos.
Esse algoritmo se fundamenta em noções associadas a cadeias de Markov, sendo a solução obtida partir de noções de álgebra linear que envolvem autovalores e autovetores.
Esse material apresenta uma introdução a esse algorítmo, com soluções obtidas pelo R, sintetizando desenvolvimentos mais detalhados sobre o assunto, como os apresentados por Brian et al. (2007) e Lay (2012, cap. 10), assim como suas referências, que devem ser consultados para informações adicionais.
2 - O algoritmo PageRank da Google
A idéia fundamental do algoritmo é estabelecer um índice de popularidade para cada site da internet, fundamentado nos sites com links apontando para esse site, ponderado pelo índice de popularidade desses sites, e assim recursivamente. Para facilitar a exposição, considere que a internet é composta somente de 4 sites, representados pela figura abaixo:
*
Uma análise ingênua da “mini-internet” representada na figura, que reflete exemplo apresentado em Brian et al. (2007), pode sugerir que seria o site 3 o mais popular, pois teria o maior número de sites (1, 2 e 4) apontando para ele. Não será esse o resultado do PageRank.
O problema dessa abordagem – usar o número de links de forma isolada como critério de popularidade – é que não considera a popularidade dos sites que estão apontando para o site de interesse. A simples criação de muitos sites, sem expressão alguma, apontando para o site de interesse, poderia facilmente “inflar” a popularidade desse site, se esse critério fosse utilizado. De fato, os primeiros algoritmos usados por buscadores usavam idéias ingênuas como essas, que foram rapidamente esquecidas.
Solução proposta pelo PageRank
A idéia brilhante de Larry Page e Sergey Brin, fundadores do Google, foi entender cada link dentro de um site A, apontando para outro site B, como sendo um voto proporcional do site A para o site B com respeito à popularidade. Nessa interpretação “democrática” da internet, cada site teria direito a um único voto, de forma que se apontasse para \(s\) sites, os votos computados para cada um desses sites seria de fato somente \(1/s\). Mas isso não levaria em conta a popularidade do site no processo de voto. Então, cada voto (proporcional) seria ponderado pelo índice de popularidade do site, visando estabelecer um processo democrático com um componente meritocrático, fundamentado na popularidade. Esse processo levará a uma interpretação probabilística, tratável por uma cadeia de Markov.
A operacionalização dessa idéia no contexto da “mini-internet” descrita nos parágrafos anteriores será apresentada a seguir para ilustrar o procedimento.
Suponha que \(\boldsymbol{\pi}=[\pi_1, \pi_2, \pi_3, \pi_4]^T\) é um vetor cujos componentes representam os índices de popularidade dos sites 1, 2, 3 e 4. Logo, teríamos:
- \(\left\{\begin{array}{ccl} \pi_1&=&\pi_3+\frac{1}{2} \pi_4\\ \pi_2&=&\frac{1}{3} \pi_1\\ \pi_3&=&\frac{1}{3} \pi_1+\frac{1}{2} \pi_2+\frac{1}{2} \pi_4\\ \pi_4&=&\frac{1}{3} \pi_1+\frac{1}{2} \pi_2\\ \end{array}\right.\)
Esse sistema poderia ser colocado na forma matricial definida por
- \(P\boldsymbol{\pi}=\boldsymbol{\pi}\) em que \(P=\left(\begin{array}{cccc} 0&0&1&\frac{1}{2}\\ \frac{1}{3}&0&0&0\\ \frac{1}{3}&\frac{1}{2}&0&\frac{1}{2}\\ \frac{1}{3}&\frac{1}{2}&0&0\\ \end{array}\right)\) e \(\boldsymbol{\pi}=\left(\begin{array}{c} \pi_1\\ \pi_2\\ \pi_3\\ \pi_4\\ \end{array}\right)\)
A solução \(\boldsymbol{\pi}\), que contém os índices de popularidade dos sites, pode ser reconhecido como um autovetor da matriz \(P\), correspondente ao autovalor 1. Em geral essa matriz \(P\), terá dimensão \(n\times n\), com sendo \(n\) o número de sites na internet.
Podemos facilmente obter os autovalores e autovetores dessa matriz \(P\) com o R através de:
## definição da matriz P
P<-matrix(c(0,1/3,1/3,1/3,0,0,1/2,1/2,1,0,0,0,1/2,0,1/2,0),ncol=4)
P## [,1] [,2] [,3] [,4]
## [1,] 0.0000000 0.0 1 0.5
## [2,] 0.3333333 0.0 0 0.0
## [3,] 0.3333333 0.5 0 0.5
## [4,] 0.3333333 0.5 0 0.0## cálculo dos autovalores e autovetores
resultados<-eigen(P)
resultados## $values
## [1] 1.0000000+0.0000000i -0.3606233+0.4109755i -0.3606233-0.4109755i
## [4] -0.2787533+0.0000000i
##
## $vectors
## [,1] [,2] [,3]
## [1,] 0.7210101+0i -0.7552157+0.0000000i -0.7552157+0.0000000i
## [2,] 0.2403367+0i 0.3036721+0.3460725i 0.3036721-0.3460725i
## [3,] 0.5407576+0i 0.0931532-0.2746779i 0.0931532+0.2746779i
## [4,] 0.3605051+0i 0.3583904-0.0713946i 0.3583904+0.0713946i
## [,4]
## [1,] 0.5064856+0i
## [2,] -0.6056557+0i
## [3,] -0.3815392+0i
## [4,] 0.4807092+0iEssa matriz \(P\) tem 4 autovalores distintos (2 deles reais e 2 complexos), sendo um deles com valor 1. Todos os valores estão expressos em números complexos, ainda que em alguns casos, somente o componente real é não nulo.
O autovetor associado ao autovalor 1, o primeiro, no algorítmo PageRank, é usualmente normalizado (lembrando que se \(\boldsymbol{\pi}\) é um autovetor, \(k \boldsymbol{\pi}\) também será um autovetor para qualquer constante \(k\in \mathbb{R}\)) de forma que a soma de seus componentes seja igual (um vetor estocástico). Isso poderia ser conseguido, já se convertendo o resultado em números complexos para números reais, através de:
Re(resultados$vector[,1]/sum(Re(resultados$vector[,1])))## [1] 0.3870968 0.1290323 0.2903226 0.1935484O resultado mostra que a solução normalizada, com soma 1, seria \(\boldsymbol{\pi}=[0,3871\,\, 0,1290\,\, 0,2903\,\, 0,1935]\), sendo o site 1 o que revelou o maior índice de popularidade (0,3871) e o site 2 o menor (0,1290).
Essa normalização permite interpretar esse resultado como probabilidades (de equilíbrio) de um internauta estar em cada um desses 4 sites, após \(m\) “cliques” depois de iniciar o acesso em qualquer um desses sites, navegando pela seleção aleatória de um dos links existentes no site, e continuando sua navegação seguindo esse mesmo procedimento infinitamente (\(m\rightarrow \infty\)). Isso representaria as probabilidades de equilíbrio de se estar em cada site depois um passeio aleatório infinito pela internet (a tradução de random walk em inglês).
Há várias questões relevantes para uma validação geral do procedimento como: (a) a matriz \(P\) obtida por esse procedimento terá sempre um autovalor 1? (b) a solução do autovetor associado a esse autovalor 1, se existir, é única? (c ) como resolver o problema computacional eficientemente, dado que existem bilhões de sites e a matriz \(P\) será gigantesca?
Todas as questões formuladas podem ser endereçadas através da análise da matriz \(P\) que pode ocorrer dentro do problema formulado e de teoremas que cobrem as situações possíveis. Um pequeno ajuste na forma de ``contabilizar os votos’’, apresentada mais adiante, é utilizada para garantir a unicidade da solução e facilidades computacionais.
3- Análise teórica da matriz estocástica P
Algumas definições
Matriz estocástica coluna: Qualquer matriz \(P_{n\times n}\) com coeficientes \(P_{ij}\ge 0\), cuja soma dos coeficientes nas colunas é igual a 1, ou seja, \(\sum_{i=1}^n P_{ij}=1\), para \(j=1,\ldots, n\), é chamada de matriz estocástica coluna. Matrizes desse tipo aparecem em cadeias de Markov (com tempo discreto e estados finitos) e tem propriedades bem conhecidas.
Vetor estocástico: um vetor qualquer \(\boldsymbol{\pi}_{n\times 1}\) com \(\pi_i\ge 0\) e \(\sum_{i=1}^n \pi_i=1\) é chamado de vetor estocástico.
Matriz estocástica positiva: para uma matriz estocástica coluna \(P\) se temos \(P_{ij}> 0\), coeficientes estritamente positivos, e matriz é chamada de matriz estocástica coluna positiva.
Matriz estocástica regular: Uma matriz estocástica coluna \(P\) é chamada de matriz estocástica coluna regular se \(P^n\) for uma matriz estocástica positiva para um dado \(n\ge 1\).
Teorema 1 - Toda matriz estocástica coluna tem um autovalor 1. Prova: Observe que para qualquer matriz estocástica coluna \(A_{n\times n}\), e um vetor coluna \(\mathbf{1}_{n\times 1}\) com todos os elementos sendo o número 1, temos \(A^T \mathbf{1}=\mathbf{1}\). Isso é claramente verdade pois essa operação corresponde a soma de cada linha da matriz \(A^T\), que corresponde a soma de cada coluna da matriz \(A\), que por definição tem a soma de seus coeficientes igual a 1. Isso significa que \(A^T\) tem um autovalor 1. Mas como os autovalores de \(A\) e \(A^T\) serão os mesmos, para qualquer matriz \(A_{n\times n}\) [use a propriedade \(\det(B)=\det(B^T)\), com \(B=(A-\lambda \mathbf{I})\) para demonstrar isso], podemos concluir que 1 é também um autovalor de \(A\).
Teorema 2 - Toda matriz estocástica coluna regular \(P\) tem um único autovalor 1 associado a um único autovetor caracterizado por um vetor estocástico \(\boldsymbol{\pi}^*\). Para qualquer vetor estocástico \(\boldsymbol{\pi}_t\), se definimos \(\boldsymbol{\pi}_{t+n}=P^n \boldsymbol{\pi}_{t}\), temos \(\lim_{n\rightarrow\infty} \boldsymbol{\pi}_{t+n}= \boldsymbol{\pi}^*\) se \(P\) for uma matriz estocástica coluna regular e \(\boldsymbol{\pi}^*\) é o único autovetor (estocástico) que soluciona \(P\boldsymbol{\pi}^*=\boldsymbol{\pi}^*\) (veja Brian e Laise 2004 e Sargent et al. 2004 para detalhes).
O Teorema 2 indica um caminho seguro para uma solução única e garantida para o problema, com facilidades computacionais, pelo procedimento que será explorado a seguir.
4 - Detalhes da implementação do PageRank
No mundo real da internet há 2 problemas principais que devem ser tratados visando tornar o problema tratável pelos resultados do Teorema 2, que requerem que a matriz \(P\) seja uma matriz estocástica regular.
Motivos que podem levar a matriz \(P\) não ser regular:
Sites sem links: seria como se o site estivesse votando somente nele próprio. Isso corresponderia à situação hipotética em que um internauta realizando um passeio aleatório pela internet ficaria “preso” nessa página, não podendo dela sair por não existir nenhum link nesse site (esse site seria um estado absorvente no contexto de uma cadeia de Markov). Somente por esse motivo, a matriz \(P\) poderia não ser regular.
Outros motivos: no mundo real, assim como no exemplo apresentado, todas as colunas de \(P\) contém coeficientes zero, algo que acontecerá na prática, visto que há um número limitado de links em cada site, não garantindo que \(P\) seja regular.
Para garantir que \(P\) seja uma matriz estocástica regular, é necessário estabelecer um procedimento que garanta que \(P_{ij}>0\) para todos os coeficientes da matriz, para que \(P\) seja regular.
Esse problema pode ser resolvido facilmente através do seguinte procedimento:
Em todos os casos de sites sem links, assuma que o internauta fazendo o passeio aleatório, escolherá aleatóriamente qualquer uma das outras \(n\) páginas existentes, ou seja, seria como se o site estivesse colocando \(1/n\) de seu voto em cada um dos \(n\) sites da internet (inclusive no seu próprio)
Assuma também que há uma probabilidade \(p\) do internauta que está em um dado site escolher aleatóriamente qualquer um dos \(n\) sites da internet (algo que certamente é próximo do que ocorre no mundo real) e probabilidade \(1-p\) dele escolher (aleatoriamente) um dos \(s\) links existente no site em que esta.
Para operacionalizar os 2 passos do procedimento considere a seguinte notação:
\(P_{n\times n}\) indica a representação dos sites e seus “votos” no contexto real da internet (certamente não é uma matriz estocástica regular).
\(P^*_{n\times n}\) é a matriz \(P\) com todas as colunas representando sites sem links trocadas por um vetor cujos elementos são todos \(1/n\).
\(M\) é uma matriz \(n\times n\) com todos seus coeficientes iguais a \(1/n\), ou seja, \(M_{ij}=1/n\).
\(p\) é a probabilidade do internauta saltar para uma página aleatória na internet em lugar de escolher um link (de forma aleatória) dentro do site que está acessando.
Defina agora:
- \(A=(1-p) P^* + p M\)
Essa matriz \(A\) seria claramente uma matriz estocástica dado que \(p\in (0,1)\), algo que o leitor poderá facilmente demonstrar como exercício.
Como \(M\) é uma matriz positiva, claramente \(A\) será também uma matriz estocástica positiva e regular, pois \(A_{ij}=(1-p) P^*_{ij}+p M_{ij}>0\) (todos os coeficientes serão estritamente positivos) dado que \(P^*_{ij}\ge 0\) e \(M^*_{ij}=1/n > 0\).
No algoritmo PageRank original, reporta-se que o Google utilizou \(p=0,15\), obtendo bons resultados com esse valor (Lay 2012).
5 - Implementação completa do PageRank com exemplo numérico
Considere a “mini-internet” com ligações entre sites caracterizadas pela figura abaixo (mesmo exemplo utilizado em Lay 2012, cap. 10)
Essa “mini-internet” poderia ser representada pela matriz
- \(P=\left(\begin{array}{ccccccc} 0&\frac{1}{2}&0&0&0&0&0\\ 0&0&\frac{1}{3}&0&\frac{1}{2}&0&0\\ 1&0&0&0&0&\frac{1}{3}&0\\ 0&0&\frac{1}{3}&1&0&0&0\\ 0&\frac{1}{2}&0&0&0&\frac{1}{3}&0\\ 0&0&\frac{1}{3}&0&\frac{1}{2}&0&0\\ 0&0&0&0&0&\frac{1}{3}&1\\ \end{array}\right)\)
Nessa situação, há 2 sites (4 e 7) sem links, algo que corresponde a estados absorventes no contexto de uma cadeia de Markov. Num teórico passeio aleatório por essa mini-internet, um internauta ficaria retido nesses sites, não conseguindo prosseguir com sua navegação.
Seguindo o procedimento descrito no tópico anterior, vamos criar a matriz \(P^*\), simplesmente substituindo as colunas da matriz \(P\) correspondentes aos sites sem links, por colunas contendo \(1/n\) com \(n=7\) nesse caso (total de sites):
- \(P^*=\left(\begin{array}{ccccccc} 0&\frac{1}{2}&0&\frac{1}{7}&0&0&\frac{1}{7}\\ 0&0&\frac{1}{3}&\frac{1}{7}&\frac{1}{2}&0&\frac{1}{7}\\ 1&0&0&\frac{1}{7}&0&\frac{1}{3}&\frac{1}{7}\\ 0&0&\frac{1}{3}&\frac{1}{7}&0&0&\frac{1}{7}\\ 0&\frac{1}{2}&0&\frac{1}{7}&0&\frac{1}{3}&\frac{1}{7}\\ 0&0&\frac{1}{3}&\frac{1}{7}&\frac{1}{2}&0&\frac{1}{7}\\ 0&0&0&\frac{1}{7}&0&\frac{1}{3}&\frac{1}{7}\\ \end{array}\right)\)
Definiremos agora a matriz \(A=(1-p) P^*+ p M\), com \(p=0,15\), de acordo com a especificação definida no tópico anterior:
- \(A=0,85 \,\left(\begin{array}{ccccccc} 0&\frac{1}{2}&0&\frac{1}{7}&0&0&\frac{1}{7}\\ 0&0&\frac{1}{3}&\frac{1}{7}&\frac{1}{2}&0&\frac{1}{7}\\ 1&0&0&\frac{1}{7}&0&\frac{1}{3}&\frac{1}{7}\\ 0&0&\frac{1}{3}&\frac{1}{7}&0&0&\frac{1}{7}\\ 0&\frac{1}{2}&0&\frac{1}{7}&0&\frac{1}{3}&\frac{1}{7}\\ 0&0&\frac{1}{3}&\frac{1}{7}&\frac{1}{2}&0&\frac{1}{7}\\ 0&0&0&\frac{1}{7}&0&\frac{1}{3}&\frac{1}{7}\\ \end{array}\right)+ 0,15 \,\left(\begin{array}{ccccccc} \frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}\\ \frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}\\ \frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}\\ \frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}\\ \frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}\\ \frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}\\ \frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}\\ \end{array}\right)\)
Podemos implementar esses cálculos no R usando
## Definindo a matriz por coluna:
P<-matrix(c(0,0,1,0,0,0,0,
1/2,0,0,0,1/2,0,0,
0,1/3,0,1/3,0,1/3,0,
0,0,0,1,0,0,0,
0,1/2,0,0,0,1/2,0,
0,0,1/3,0,1/3,0,1/3,
0,0,0,0,0,0,1),ncol=7)
P## [,1] [,2] [,3] [,4] [,5] [,6] [,7]
## [1,] 0 0.5 0.0000000 0 0.0 0.0000000 0
## [2,] 0 0.0 0.3333333 0 0.5 0.0000000 0
## [3,] 1 0.0 0.0000000 0 0.0 0.3333333 0
## [4,] 0 0.0 0.3333333 1 0.0 0.0000000 0
## [5,] 0 0.5 0.0000000 0 0.0 0.3333333 0
## [6,] 0 0.0 0.3333333 0 0.5 0.0000000 0
## [7,] 0 0.0 0.0000000 0 0.0 0.3333333 1## Criando um vetor com 1/7 em cada posição:
v<-1/7*rep(1,7) ## ou 1/7 * c(1,1,1,1,1,1,1)
v## [1] 0.1428571 0.1428571 0.1428571 0.1428571 0.1428571 0.1428571 0.1428571## Trocando as colunas de P dos sites sem links:
P[,4]<-v
P[,7]<-v
## A matriz P corresponde agora à matriz P* na notação do texto:
##
## A matriz M pode ser definida por:
M<-1/7*matrix(rep(1,49),ncol=7)
##
## Finalmente a matriz A será definida por:
A<-0.85*P+0.15*M
A## [,1] [,2] [,3] [,4] [,5] [,6]
## [1,] 0.02142857 0.44642857 0.02142857 0.1428571 0.02142857 0.02142857
## [2,] 0.02142857 0.02142857 0.30476190 0.1428571 0.44642857 0.02142857
## [3,] 0.87142857 0.02142857 0.02142857 0.1428571 0.02142857 0.30476190
## [4,] 0.02142857 0.02142857 0.30476190 0.1428571 0.02142857 0.02142857
## [5,] 0.02142857 0.44642857 0.02142857 0.1428571 0.02142857 0.30476190
## [6,] 0.02142857 0.02142857 0.30476190 0.1428571 0.44642857 0.02142857
## [7,] 0.02142857 0.02142857 0.02142857 0.1428571 0.02142857 0.30476190
## [,7]
## [1,] 0.1428571
## [2,] 0.1428571
## [3,] 0.1428571
## [4,] 0.1428571
## [5,] 0.1428571
## [6,] 0.1428571
## [7,] 0.1428571## Observe que A é estocástica e regular.
## Note que a soma das linhas da transposta
## de A, que corresponde a soma das colunas de A,
## resulta sempre 1:
t(A)%*%rep(1,7)## [,1]
## [1,] 1
## [2,] 1
## [3,] 1
## [4,] 1
## [5,] 1
## [6,] 1
## [7,] 1Para achar os índices de popularidade, precisamos agora encontrar o vetor estocástico \(\boldsymbol{\pi^*}\) que conterá os indices de popularidade dos 7 sites, e que soluciona:
- \(A \boldsymbol{\pi^*}=\boldsymbol{\pi^*}\)
Sabemos pelo resultado dos Teoremas 1 e 2 que essa solução existe e é única, dado que \(A\) é uma matriz estocástica regular. Além disso, pelo Teorema 2 sabemos que se partirmos de um vetor estocástico qualquer \(\boldsymbol{\pi}_t\) de dimensão \(7\times 1\), e definirmos
\(\boldsymbol{\pi}_{t+m}=A^m \boldsymbol{\pi}_t\), é garantido que:
\(\lim_{m\rightarrow \infty} \boldsymbol{\pi}_{t+m}=\boldsymbol{\pi}^*\).
Ainda que o R tenha recursos para diretamente elevar uma matriz a uma dada potência (ex. com o package expm carregado, é possível a operação \(A^{10}\) usando no R:
Podemos iniciar com qualquer vetor estocástico de dimensão \(7\times 1\) e iterar até que se verifique pouca alteração no vetor resultante. A seguir são realizadas 10 iterações, que obtém \(\boldsymbol{\pi}_{t+1}, \boldsymbol{\pi}_{t+2},\ldots, \boldsymbol{\pi}_{t+10}\) a partir de \(\boldsymbol{\pi}_{t}=[1,0,0,0,0,0,0]^T\). Cada iteração é colocada nas colunas de uma matriz para facilitar comparações. Note que há pouca alteração nos valores obtidos a partir da iteração 8, num processo rápido de convergência.
pi<-c(1,0,0,0,0,0,0)
MatRes<-matrix(rep(0,70),ncol=10)
## iteração 1
for (i in 1:10){
pi<-A%*%pi
MatRes[,i]<-pi
}
MatRes## [,1] [,2] [,3] [,4] [,5] [,6]
## [1,] 0.02142857 0.03573980 0.17873898 0.08573477 0.1289619 0.11134850
## [2,] 0.02142857 0.28264456 0.09081168 0.20504399 0.1528835 0.17482930
## [3,] 0.87142857 0.05091837 0.16907649 0.22479791 0.1727886 0.19930762
## [4,] 0.02142857 0.27353741 0.07304191 0.09504481 0.1055109 0.09532978
## [5,] 0.02142857 0.04181122 0.25882160 0.11146475 0.1870577 0.15466548
## [6,] 0.02142857 0.28264456 0.09081168 0.20504399 0.1528835 0.17482930
## [7,] 0.02142857 0.03270408 0.13869766 0.07286978 0.0999140 0.08969001
## [,7] [,8] [,9] [,10]
## [1,] 0.11819772 0.11555284 0.11658562 0.11617685
## [2,] 0.16609858 0.16953566 0.16818287 0.16871954
## [3,] 0.18807645 0.19249026 0.19078798 0.19144873
## [4,] 0.10036575 0.09824927 0.09907187 0.09875573
## [5,] 0.16773268 0.16261410 0.16462072 0.16382867
## [6,] 0.16609858 0.16953566 0.16818287 0.16871954
## [7,] 0.09343023 0.09202221 0.09256807 0.09235095O resultado indica que o site 3 é o mais popular (índice próximo a 0,191) e o site 7 o menos popular.
No caso real do Google, a matriz \(A\) tem mais de 8 bilhões de linhas e colunas e os cálculos demoram dias, sendo utilizadas, segundo Lay (2012) cerca de 50 a 100 iterações (com algumas otimizações para minimização de cálculos desnecessários). Não há motivo para se ter uma precisão absoluta no resultado. O processo iterativo usualmente termina na iteração \(k\) quando, os últimos 2 vetores obtidos estão suficientemente próximos, de acordo com alguma métrica \(d\) usando-se um critério como:
- condição de término: \(d(\boldsymbol{\pi}_{t+k},\boldsymbol{\pi}_{t+k-1})< \epsilon\), onde \(\epsilon>0\) é um valor definido. A métrica \(d\) utllizada pode ser a euclidiana, por exemplo.
Um procedimento com condição de término que atenda um dado \(\epsilon\) ou não exceda um máximo número de iterações (ex. 100) pode ser implementado facilmente nesse caso. Supondo \(\epsilon=0,001\), distância euclidiana e um máximo de 100 iterações, temos:
epsilon<-0.001
nmax<-100 ## número máximo de iterações
pi0<-c(1,0,0,0,0,0,0)
for(i in 1:nmax) {
pi<-A%*%pi0
d<-sqrt(t(pi-pi0)%*%(pi-pi0)) ## distância euclidiana
if (d<=epsilon) break ## saindo se a condição for atendida
pi0<-pi
}
cat("iterações:", i, "distância:",d, "\n")## iterações: 11 distância: 0.0005551374pi## [,1]
## [1,] 0.11634019
## [2,] 0.16850537
## [3,] 0.19118858
## [4,] 0.09887819
## [5,] 0.16414406
## [6,] 0.16850537
## [7,] 0.09243825Em 11 iterações atingimos o objetivo.
6 - Conclusão
Apresentamos aqui uma síntese do algorítmo PageRank desenvolvido pelo Google e da base teórica que suporta as operações realizadas pelo algoritmo, fundamentada em princípios elementares de álgebra linear. Exemplos são utilizados para ilustrar a operacionalização dos procedimentos, com implementação realizada no software R.
São muitas as situações que podem comportar uma abordagem similar para efeito de se produzir rankings das mais diversas naturezas, algo de substancial valor econômico numa sociedade em que a informação é cada vez mais abundante, como mostra o exemplo do Google.
Projeto sugerido
Para melhor familiarização com os procedimentos utilizados, sugiro o desenvolvimento de projeto em que se verifique a possibilidade de aumentar o indice de popularidade do site 7, dessa última “mini-internet” apresentada, simplesmente criando-se 3 sites sem qualquer link apontando para eles que tenham link para o site 7. Essa estratégia funciona?
7 - Referências
Brian, K. e Leise, T. The $25,000,000,000 Eigenvector: The Linear Algebra Behind Google. Dept. Mathematics and Computer Science, Amherst College. 2007.
Lay, D. Linear Algebra and its Applications. Addison-Wesley, 2012.
Meyer, C. Matrix Analysis and Applied Linear Algebra. SIAM, 2004.
Sargent, T. e Ljungqvist, L. Recursive Macroeconomic Theory. MIT Press, 2004.