Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como o google calcula o rank da minha página?

+1 voto
215 visitas
perguntada Dez 5, 2015 em Ciência da Computação por danielcajueiro (5,376 pontos)  

google www.prorum.com

Compartilhe

1 Resposta

+1 voto
respondida Dez 5, 2015 por danielcajueiro (5,376 pontos)  

Imagine que você está fazendo uma pesquisa sobre a palavra "cajueiro". Eu escrevo "cajueiro" no google e aparece em 0,39 segundos 974.000 resultados, onde o primeiro resultado é o da Wikipedia que se refere a "uma planta da família Anacardiacea".

cajueiro www.prorum.com

É triste (:-), mas não tem nenhuma referência a mim. Obvialmente esse resultado muda drásticamente se eu colocar "Daniel Cajueiro", onde as duas referências principais são a mim. Embora a primeira página esteja totalmente desatualizada devida a gestão ineficiente dessa página na Unb, a segunda é a melhor referência.

O mesmo vai acontecer com você se você tentar seu sobrenome "pereira", "mangueira", "wood", "rocha", "oliveira"...

Ferramentas de busca são construídas para desempenhar as seguintes atividades:

(1) Aquisição de dados de um site, que inclui (não exclusivamente) título da página, lista de palavras chaves e links para as outras páginas.

(2) Criação de um "dicionário" com toda essa informação que seja facilmente acessada.

(3) Criação de um ranking que diga qual página é mais importante para um determinado assunto.

Supondo que as etapas (1) e (2) acima já foram realizadas, o google faz o rank de sua página usando um algoritmo chamado de PageRank. O PageRank é um trocadilho que usa o nome de um dos fundadores do google Larry Page e o fato que ele é usado para fazer um "rank" de "pages".Observe que tão importante quanto a qualidade do ranking é o trabalho descrito nos ítens (1) e (2) acima. Um exemplo é a diferença dos resultados encontrados para a busca "cajueiro" e "daniel cajueiro".

Qual a principal idéia por detrás do PageRank?

Toda vez que uma página da internet tem um link para uma outra página ela dá um voto de apoio a essa outra página. Mas quanto vale esse voto? Quanto mais importante for essa página na rede, mais importante será o seu voto. Quem diz qual a página mais importante? O próprio google usando essa mesma idéia.

pagerank www.prorum.com

É fundamental notar que o pageRank é uma medida de centralidade de redes complexas que possui características muito especiais e úteis para lidar com esse problema.

Matemáticamente, como isso funciona?

Ele considera as seguintes hipóteses básicas:

(1) Toda vez que você está navegando na internet, com probabilidade \(p\), você segue um dos links apresentados na página corrente e, com probabilidade \((1-p)\), você começa aleatoriamente de qualquer página da internet. Normalmente, supõe-se que \((1-p)\) é bem pequeno.

(2) Com probabilidade \(p\), você segue um dos links apresentados apresentados na página corrente \(i\) e você faz isso com probabilidade \(1/m_i\), onde \(m_i\) é o número de páginas citadas nessa página.

(3) Com probabilidade \(1-p\), você recomeça o processo em uma nova página com probabilidade \(1/N\), onde \(N\) é o número de páginas da internet.

(4) Se numa página não houver nenhum link para outra página, supõe-se que você permanece nessa página ou vai para outra página qualquer com probabilidade \(1/N\), onde \(N\) é o número de páginas da internet.

Que tal considerar um exemplo?

Considere a rede apresentada abaixo, mas lembre que no mundo real o Google lida com uma rede gisgantesca e complexa:

rede www.prorum.com//index.php?qa=faq

Enquanto as bolas representam as páginas da internet, as setas entre essas bolas representam os links entre essas páginas. Por exemplo, a seta que sai da página \(i\) para a página \(j\) indica que existe um link na página \(i\) para a página \(j\).

A importância de uma página é medida pela probabilidade de você em um determinando instante de tempo você estar navegando nessa página. Logo, utilizando as hipóteses acima, podemos modelar as probabilidades \(\pi_{i}^{t}\), que é a probabilidade de estar na página \(i\) no instante \(t\). Para a rede apresentada na figura acima, temos que

\(\pi_{1}^{t+1}=(1-p)[\sum_{i=1}^{5}\pi_{i}^{t}\times \frac{1}{5}] + p [\pi_{3}^{t} \times \frac{1}{2} + \pi_{5}^{t}\times \frac{1}{5}]\)

\(\pi_{2}^{t+1}=(1-p)[\sum_{i=1}^{5}\pi_{i}^{t}\times \frac{1}{5}] + p [\pi_{1}^{t}\times 1 + \pi_{4}^{t} \times 1 + \pi_{5}^{t}\times \frac{1}{5}]\)

\(\pi_{3}^{t+1}=(1-p)[\sum_{i=1}^{5}\pi_{i}^{t}\times \frac{1}{5}] + p [\pi_{2}^{t}\times \frac{1}{2} + \pi_{5}^{t}\times \frac{1}{5}]\)

\(\pi_{4}^{t+1}=(1-p)[\sum_{i=1}^{5}\pi_{i}^{t}\times \frac{1}{5}] +p[\pi_{5}^{t}\times \frac{1}{5}]\)

\(\pi_{5}^{t+1}=(1-p)[\sum_{i=1}^{5}\pi_{i}^{t}\times \frac{1}{5}] + p[ \pi_{2}^{t}\times \frac{1}{2} + \pi_{3}^{t}\times \frac{1}{2} +\pi_{5}^{t}\times \frac{1}{5}]\)

Por exemplo, para o caso \(\pi_{1}^{t}\), podemos chegar na página 1 aleatoriamente de qualquer página com probabilidade \((1-p)\) ou podemos chegar a página 1 com probalidade \(p\) seguindo o link que está na página 3 ou recomeçar o processo a partir da página 5 (que não apresenta link para nenhum página).

Matematicamente, o processo estocástico acima que modela as probabilidades de interesse é chamado de Cadeia de Markov, pois a probabilidade de estar em uma página \(i\) no instante \(t+1\) depende apenas das probabilidades no instante anterior.

Perceba que não estamos interessados especialmente nas probabilidade \(\pi_{i}^{t}\) no instante \(t\), mas sim nas probabilidades limites estacionárias, que ocorrem quando \(t\) tende para o infinito. Se chamarmos essas probabilidades estacionárias de \(\pi_{i}^{\infty}\), chegamos a

\(\pi_{1}^{\infty}=(1-p)[\sum_{i=1}^{5}\pi_{i}^{\infty}\times \frac{1}{5}] + p [\pi_{3}^{\infty} \times \frac{1}{2} +\pi_{5}^{\infty}\times \frac{1}{5}]\)

\(\pi_{2}^{\infty}=(1-p)[\sum_{i=1}^{5}\pi_{i}^{\infty}\times \frac{1}{5}] + p [\pi_{1}^{\infty}\times 1 + \pi_{4}^{\infty} \times 1 \pi_{5}^{\infty}\times \frac{1}{5}]\)

\(\pi_{3}^{\infty}=(1-p)[\sum_{i=1}^{5}\pi_{i}^{\infty}\times \frac{1}{5}] + p [\pi_{2}^{\infty}\times \frac{1}{2} +\pi_{5}^{\infty}\times \frac{1}{5}]\)

\(\pi_{4}^{\infty}=(1-p)[\sum_{i=1}^{5}\pi_{i}^{\infty}\times \frac{1}{5} ] + p [\pi_{5}^{\infty}\times \frac{1}{5}]\)

\(\pi_{5}^{\infty}=(1-p)[\sum_{i=1}^{5}\pi_{i}^{\infty}\times \frac{1}{5}] + p[ \pi_{2}^{\infty}\times \frac{1}{2} + \pi_{3}^{\infty}\times \frac{1}{2} +\pi_{5}^{\infty}\times \frac{1}{5}]\)

Veja como ficou simples.... É um sistema linear!

Note ainda que \(\sum_{i=1}^{5}\pi_{i}^{\infty}=1\). Seja a matriz \(R\) dada por

\[R=\left[\begin{array}{ccccc} 0& 0& \frac{1}{2}& 0& \frac{1}{5} \\ 1& 0& 0& 1& \frac{1}{5} \\ 0& \frac{1}{2}& 0& 0& \frac{1}{5}\\ 0& 0& 0& 0& \frac{1}{5}\\ 0& \frac{1}{2}& \frac{1}{2}& 0& \frac{1}{5}\\ \end{array}\right],\]

a matriz (transformação linear) dada por \(S=I - p\times R\) e o vetor \(u=(1-p)\times\frac{1}{5} \times \textbf{1}\), onde \(I\) é a matriz identidade de ordem \(5\times 5\) e \(\textbf{1}\) é o vetor formado de 1s de ordem \(5\times 1\). Logo, podemos reescrever o sistema acima como

\[S v= u,\]

onde \(v\) é o vetor buscado de pageranks. Note que precisamos apenas inverter a matriz \(S\) para chegar ao resultado desejado.

Se supormos como o google que \(p=0.85\), então o pageRank é dado por

\[v=\left[\begin{array}{c} 0.16 \\ 0.28\\ 0.20\\ 0.08\\ 0.28\\ \end{array}\right].\]

Logo, como esperado, os maiores pageranks estão relacionados com as páginas 2 e 5.

Realmente, é fácil fazer essa conta?

Não! Note que a internet não é uma rede de \(5\) nós, mas uma rede gigantesca.

Como inverter uma matriz gigantesca?

Banach www.prorum.com/index.php/857/qual-a-proposta-do-prorum

O Google NÃO inverte essa matriz.

De fato, a matriz \(R\) apresenta características interessantes como, por exemplo, seus autovalores e autovetores podem ser bem caracterizados usando o teorema de Perron-Frobenius. Adicionalmente, o sistema linear acima que depende da matriz \(S\) pode ser SEMPRE (ele sempre tem solução) resolvido usando métodos iterativos reescrevendo \(S\) de forma que possamos transformar a solução desse problema como uma aplicação direta do Teorema do Ponto Fixo de Banach.

Então, o número de páginas que apontam para minha página é o único fator?

Não! No passado, donos de páginas criavam ou usavam sites que serviam apenas para apontar para a sua página. "Pessoas respondem a incentivos, não? Hoje o Google diz ser capaz de detectar esses sites e evitar esse tipo de "jeitinho" para aumentar o pagerank. Lembre que a qualidade do conteúdo também é fundamental pois ele terá muito impacto na correlação entre o termo pesquisado pelo o interessado no assunto e os termos que aparecem no "dicionário" do google relacionados com a sua página.

O PageRank era totalmente original? Veja a idéia do Leontief!

A imagem será apresentada aqui.

Existem muitos precursores do PageRank. Por exemplo, em 1941, Leontief propôs um modelo em que a economia de um país podia ser dividida em vários setores industriais, que ele chamou de indústrias. Cada indústria necessitava de uma certa quantidade de insumos para produzir uma unidade de seu produto. Sequencialmente, seu produto serveria como insumo para outras indústrias. Uma pergunta relevante era: Qual o valor de cada indústria depois de integrada? Leontief então desenvolveu um método iterativo para achar o valor de cada indústria tomando como base as indústrias que lhe forneciam insumos. A matemática por detrás desse modelo é muito parecida com aquela apresentada pelo PageRank.

Existem referências interessantes sobre esse assunto?

Sim! Dê uma olhada aqui.

...