PageRank (Português)

o algoritmo PageRank produz uma distribuição de probabilidade usada para representar a probabilidade de uma pessoa clicando aleatoriamente em links chegar a qualquer página em particular. PageRank pode ser calculado para coleções de documentos de qualquer tamanho. É assumido em vários trabalhos de pesquisa que a distribuição é dividida uniformemente entre todos os documentos na coleção no início do processo computacional., Os cálculos do PageRank requerem várias passagens, chamadas “iterações”, através da coleção para ajustar valores aproximados do PageRank para refletir mais de perto o valor teórico verdadeiro.

uma probabilidade é expressa como um valor numérico entre 0 e 1. Uma probabilidade de 0,5 é comumente expressa como uma” probabilidade de 50% ” de algo acontecer. Assim, um documento com um PageRank de 0,5 significa que há 50% de chance de que uma pessoa clicando em um link aleatório será direcionado para esse documento.

algoritmo simplificado

Assume um pequeno universo de quatro páginas web: A, B, C E D., Links de uma página para si são ignorados. Vários links de saída de uma página para outra são tratados como um único link. PageRank é inicializado para o mesmo valor para todas as páginas. Na forma original do PageRank, a soma do PageRank sobre todas as páginas era o número total de páginas na web naquela época, de modo que cada página neste exemplo teria um valor inicial de 1. No entanto, versões posteriores do PageRank, e o restante desta seção, assumem uma distribuição de probabilidade entre 0 e 1. Assim, o valor inicial para cada página neste exemplo é 0.25.,

O PageRank transferido de uma dada página para os alvos dos seus links de saída na próxima iteração é dividido igualmente entre todos os links de saída.se as únicas ligações no sistema fossem das páginas B, C E D para A, cada ligação transferiria 0.25 PageRank para A na próxima iteração, para um total de 0.75.

p r ( A) = P R ( B) + P R ( C) + P R ( D). {\displaystyle PR(a)=PR(B)+PR(C)+PR(D).\ ,}

suponha em vez disso que a Página B tinha um link para as páginas C e A, a Página C tinha um link para a página a, e a Página D tinha links para todas as três páginas., Assim, após a primeira iteração, a página B iria transferir metade de seu valor existente, ou 0,125, a página de Um e a outra metade, ou 0,125, a página de C. Página C seria transferir toda a sua valor existente, 0.25, para a única página de links para, A. uma vez que D tinha três links de saída, que seria a transferência de um terço de seu valor existente, ou cerca de 0.083, para A. Na conclusão dessa iteração, Uma página irá ter um PageRank aproximadamente 0.458.

p r ( A) = P R ( B ) 2 + P R ( C ) 1 + P R ( D) 3 . {\displaystyle PR(A)={\frac {PR(B)}{2}}+{\frac {PR(C)}{1}}+{\frac {PR(D)}{3}}.,\ ,}

em outras palavras, o PageRank conferido por um link outbound é igual à pontuação PageRank do próprio documento dividido pelo número de links outbound L( ).

p r ( A) = P R ( B) L ( B) + P R ( C) L ( C) + P R ( D) L ( D). {\displaystyle PR(A)={\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}.\ ,}

no caso geral, o valor do PageRank para qualquer página u pode ser expresso como:

p r ( u ) = ∑ v ∑ b u p r (v ) L (v) {\displaystyle PR (u)=\sum _{v\in b_{u}}{\frac {PR (v)}} {l(v)}}}},

i.e., o valor de PageRank de uma página de u é dependente dos valores de PageRank de cada página v contidos no conjunto Bu (o conjunto que contém todas as páginas vinculadas a página u), dividido pelo número L(v) um dos links a partir da página v.

Amortecimento factorEdit

O PageRank teoria sustenta que um imaginário surfista, que é aleatoriamente clicar em links que, eventualmente, irá parar de clicar. A probabilidade, em qualquer etapa, de que a pessoa continuará é um fator de amortecimento D. vários estudos testaram diferentes fatores de amortecimento, mas é geralmente assumido que o Fator de amortecimento será definido em torno de 0,85. ,

O fator de amortecimento é subtraído 1 (e em algumas variações do algoritmo, o resultado é dividido pelo número de documentos (N) na coleção) e este termo é, então, adicionado ao produto do fator de amortecimento e a soma da entrada PageRank pontuações. Isto é,

p r ( a) = 1 − d N + D [P R ( B) L ( B) + P R ( C) L ( C) + P R ( D) L ( D)+⋯]. {\displaystyle PR(A)={1-d \over N}+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right). então o PageRank de qualquer página é derivado em grande parte dos PageRanks de outras páginas., O Fator de amortecimento ajusta o valor derivado para baixo. O papel original, no entanto, deu a seguinte fórmula, o que levou a alguma confusão: P r ( a ) = 1 − d + D ( P R ( B ) L ( B ) + P R ( C ) L ( C ) + P R ( D ) L ( D ) + ⋯ ) . {\displaystyle PR(A)=1-d+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right).

a diferença entre eles é que os valores do PageRank na primeira fórmula somam-se a um, enquanto na segunda fórmula cada PageRank é multiplicado por N e a soma torna-se N., Uma declaração na página e no artigo de Brin que “a soma de todos os PageRanks é um” e reivindicações de outros funcionários do Google suportam a primeira variante da fórmula acima.

Page and Brin confused the two formulas in their most popular paper “The Anatomy of a Large-Scale Hypertextual Web Search Engine”, where they mistakenly claimed that the latter formula formed a probability distribution over web pages.

O Google recalcula as pontuações do PageRank cada vez que rasteja a Web e reconstrói o seu índice., Como o Google aumenta o número de documentos em sua coleção, a aproximação inicial do PageRank diminui para todos os documentos.

a fórmula usa um modelo de um surfista aleatório que atinge o seu local alvo após vários cliques, em seguida, muda para uma página aleatória. O valor PageRank de uma página reflete a chance de que o surfista aleatório vai pousar nessa página clicando em um link. Pode ser entendida como uma cadeia de Markov na qual os estados são páginas, e as transições são os elos entre páginas – todos os quais são igualmente prováveis.,

Se uma página não tem links para outras páginas, ela se torna uma pia e, portanto, termina o processo de navegação aleatória. Se o surfista Aleatório chega a uma página de pia, ele pega outra URL ao acaso e continua surfando novamente.

ao calcular o PageRank, assume-se que as páginas sem ligações externas estão ligadas a todas as outras páginas da colecção. As suas pontuações de PageRank estão, portanto, divididas uniformemente entre todas as outras páginas. Em outras palavras, para ser justo com páginas que não são sumidouros, estas transições aleatórias são adicionadas a todos os nós na Web. Esta probabilidade residual, d, é normalmente definida como 0.,85, estimado a partir da frequência que um surfista médio usa seu recurso de favoritos do navegador. Assim, a equação é a seguinte:

P R ( p i ) = 1 − d N + d ∑ p j ∈ M ( p i ) P R ( p j), L ( p j ) {\displaystyle PR(p_{i})={\frac {1-d}{N}}+d\sum _{p_{j}\no M(p_{i})}{\frac {PR(p_{j})}{L(p_{j})}}}

O PageRank valores são as entradas do dominante direito eigenvector alterada da matriz de adjacências redimensionado de forma a que cada coluna adiciona a um.,_{1},p_{1})&\ell (p_{1},p_{2})&\cdots &\ell (p_{1},p_{N})\\\ell (p_{2},p_{1})&\ddots &&\vdots \\\vdots &&\ell (p_{i},p_{j})&\\\ell (p_{N},p_{1})&\cdots &&\ell (p_{N},p_{N})\end{bmatrix}}\mathbf {R} } ∑ i = 1 N ℓ ( p i , p j ) = 1 {\displaystyle \sum _{i=1}^{N}\ell (p_{i},p_{j})=1} ,

i.,e. Os elementos de cada coluna somam até 1, então a matriz é uma matriz estocástica (para mais detalhes veja a seção de computação abaixo). Assim, esta é uma variante da medida de centralidade de autovetor usada comumente na análise de rede.

devido ao grande eigengap da matriz de adjacência modificada acima, os valores do PageRank eigenvector podem ser aproximados dentro de um alto grau de precisão dentro de apenas algumas iterações.,

os fundadores do Google, em seu artigo original, relataram que o algoritmo PageRank para uma rede consistindo de 322 milhões de links (arestas e arestas) converge para dentro de um limite tolerável em 52 iterações. A convergência em uma rede de metade do tamanho acima levou aproximadamente 45 iterações. Através destes dados, eles concluíram que o algoritmo pode ser dimensionado muito bem e que o Fator de escala para redes extremamente grandes seria aproximadamente linear em log ⁡ n {\displaystyle \log n} , onde n é o tamanho da rede.,como resultado da teoria de Markov, pode ser mostrado que o PageRank de uma página é a probabilidade de chegar a essa página após um grande número de cliques. Isto acontece com igual T-1 {\displaystyle T^{-1} onde t {\displaystyle t} é a expectativa do número de ‘clicks’ (ou saltos aleatórios) necessários para voltar da página para si.uma das principais desvantagens do PageRank é que ele favorece páginas mais antigas. Uma nova página, mesmo muito boa, não terá muitos links a menos que faça parte de um site existente (um site sendo um conjunto de páginas densamente conectadas, como a Wikipédia).,várias estratégias foram propostas para acelerar o cálculo do PageRank.várias estratégias para manipular o PageRank foram empregadas em esforços concertados para melhorar os rankings dos resultados da pesquisa e monetizar os links publicitários. Estas estratégias têm afetado severamente a confiabilidade do conceito de PageRank, que pretende determinar quais documentos são realmente altamente valorizados pela comunidade Web.,

desde dezembro de 2007, quando começou a penalizar ativamente sites que vendem links de texto pagos, o Google tem combatido fazendas de links e outros esquemas destinados a inflacionar artificialmente o PageRank. Como o Google identifica fazendas de links e outras ferramentas de manipulação de PageRank está entre os segredos comerciais do Google.

ComputationEdit

PageRank pode ser calculado iterativamente ou algebricamente. O método iterativo pode ser visto como o método de iteração de potência ou o método de potência. As operações matemáticas básicas realizadas são idênticas.,

IterativeEdit

At T = 0 {\displaystyle t=0}, assume-se uma distribuição inicial de probabilidade, normalmente

p r ( p i ; 0 ) = 1 n {\displaystyle PR(p_{i};0)={\frac {1}{n}}} .

Onde n é o número total de páginas, e p i ; 0 {\displaystyle p_{i};0} é a Página I no momento 0.,

(1)

The matrix M {\displaystyle {\mathcal {M}}} is defined as

M i j = { 1 / L ( p j ) , if j links to i 0 , otherwise {\displaystyle {\mathcal {M}}_{ij}={\begin{cases}1/L(p_{j}),&{\mbox{if }}j{\mbox{ links to }}i\ \\0,&{\mbox{otherwise}}\end{cases}}}

i.,e.

M := ( K − 1 ) T {\displaystyle {\mathcal {M}}:=(K^{-1}A)^{T}} ,

, onde Uma {\displaystyle A} denota a matriz de adjacências do grafo e K {\displaystyle K} é a matriz diagonal com os outdegrees na diagonal.

o cálculo de probabilidade é feito para cada página em um ponto de tempo, então repetido para o próximo ponto de tempo. O cálculo termina quando, por algum pequeno ϵ {\displaystyle \epsilon }

| R ( t + 1 ) − R ( t ) | < ϵ {\displaystyle |\mathbf {R} (t+1)-\mathbf {R} (t)|<\epsilon } ,

por exemplo, quando a convergência é assumido.,

AlgebraicEdit

—For t → ∞ {\displaystyle t\to \infty } (i.e., in the steady state), the equation (1) reads

(2)

The solution is given by

R = ( I − d M ) − 1 1 − d N 1 {\displaystyle \mathbf {R} =(\mathbf {I} -d{\mathcal {M}})^{-1}{\frac {1-d}{N}}\mathbf {1} } ,

with the identity matrix I {\displaystyle \mathbf {I} } .,

A solução existe e é única para 0 < d < 1 {\displaystyle 0<d<1} . Isto pode ser visto observando que m {\displaystyle {\mathcal {M}}} é por construção uma matriz estocástica e, portanto, tem um valor eigen igual a um como consequência do teorema de Perron–Frobenius.,

Power methodEdit

(3)

x ( t + 1 ) = M ^ x ( t ) {\displaystyle x(t+1)={\widehat {\mathcal {M}}}x(t)} ,

until

| x ( t + 1 ) − x ( t ) | < ϵ {\displaystyle |x(t+1)-x(t)|<\epsilon } .,

Note que na equação (3) a matriz do lado direito parênteses pode ser interpretado como

1 − d N E = ( 1 − d ) P 1 t {\displaystyle {\frac {1-d}{N}}\mathbf {E} =(1-d)\mathbf {M} \mathbf {1} ^{t}} ,

, onde P {\displaystyle \mathbf {P} } é uma primeira distribuição de probabilidade. No caso actual

P: = 1 n 1 {\displaystyle \mathbf {P}: = {\frac {1}{n}}\mathbf {1} }.,therwise {\displaystyle \mathbf {D} _{i}={\begin{cases}1,&{\mbox{if }}L(p_{i})=0\ \\0,&{\mbox{otherwise}}\end{cases}}}

In this case, the above two computations using M {\displaystyle {\mathcal {M}}} only give the same PageRank if their results are normalized:

R power = R iterative | R iterative | = R algebraic | R algebraic | {\displaystyle \mathbf {R} _{\textrm {power}}={\frac {\mathbf {R} _{\textrm {iterative}}}{|\mathbf {R} _{\textrm {iterative}}|}}={\frac {\mathbf {R} _{\textrm {algebraic}}}{|\mathbf {R} _{\textrm {algebraic}}|}}} .,

ImplementationEdit

Scala/Apache SparkEdit

um exemplo típico é usar a programação funcional do Scala com o Apache Spark RDDs para calcular iterativamente as fileiras de páginas.

o MATLAB/OctaveEdit

Exemplo de código de chamar a função de classificação acima definida:

M = ;rank2(M, 0.80, 0.001)

PythonEdit

Este exemplo leva ≈13 iterações para convergir.