PageRank

el algoritmo PageRank muestra una distribución de probabilidad utilizada para representar la probabilidad de que una persona que haga clic aleatoriamente en enlaces llegue a una página en particular. PageRank se puede calcular para colecciones de documentos de cualquier tamaño. Se asume en varios trabajos de investigación que la distribución se divide uniformemente entre todos los documentos de la colección al comienzo del proceso computacional., Los cálculos del PageRank requieren varias pasadas, llamadas «iteraciones», a través de la colección para ajustar los valores aproximados del PageRank para reflejar más de cerca el valor verdadero teórico.

una probabilidad se expresa como un valor numérico entre 0 y 1. Una probabilidad de 0.5 se expresa comúnmente como una «probabilidad del 50%» de que algo suceda. Por lo tanto, un documento con un PageRank de 0.5 significa que hay un 50% de probabilidades de que una persona que haga clic en un enlace Aleatorio sea dirigida a dicho documento.

simplified algorithmEdit

asume un pequeño universo de cuatro páginas web: A, B, C y D., Los enlaces de una página a sí misma se ignoran. Los múltiples enlaces salientes de una página a otra se tratan como un solo enlace. PageRank se inicializa con el mismo valor para todas las páginas. En la forma original de PageRank, la suma de PageRank sobre todas las páginas era el número total de páginas en la web en ese momento, por lo que cada página en este ejemplo tendría un valor inicial de 1. Sin embargo, las versiones posteriores de PageRank, y el resto de esta sección, asumen una distribución de probabilidad entre 0 y 1. Por lo tanto, el valor inicial para cada página en este ejemplo es 0.25.,

el PageRank transferido desde una página dada a los destinos de sus enlaces salientes en la siguiente iteración se divide por igual entre todos los enlaces salientes.

si los únicos enlaces en el sistema fueran de las páginas B, C y D A A, cada enlace transferiría 0.25 PageRank A A en la siguiente iteración, para un 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).\ ,}

supongamos en su lugar que la página B tenía un enlace a las páginas C y A, la página C tenía un enlace a la página a, y la página D tenía enlaces a las tres páginas., Por lo tanto, en la primera iteración, la página B transferiría la mitad de su valor existente, o 0.125, a la página a y la otra mitad, o 0.125, a la página C. La Página C transferiría todo su valor existente, 0.25, a la única página a la que enlaza, A. dado que D tenía tres enlaces salientes, transferiría un tercio de su valor existente, o aproximadamente 0.083, a A. Al completar esta iteración, la página a tendrá un PageRank de 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}}.,\ ,}

En otras palabras, el PageRank conferido por un enlace saliente es igual a la puntuación del PageRank del documento dividido por el número de enlaces salientes L ().

P R ( a ) = P R ( B ) L ( B ) + P ( 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)}}.\,}

En el caso general, el valor de PageRank de cualquier página de u se puede expresar como:

P R ( u ) = ∑ v ∈ B u P R ( v ) L ( v ) {\displaystyle PR(u)=\sum _{v\en B_{u}}{\frac {PR(v)}{L(v)}}} ,

es decir,, el valor del PageRank para una página u depende de los valores del PageRank para cada página V contenida en el conjunto Bu(el conjunto que contiene todas las páginas que enlazan a la página u), dividido por el número L (v) de enlaces de la página v.

Damping factoreditar

La teoría del PageRank sostiene que un surfista imaginario que está haciendo clic aleatoriamente en los enlaces eventualmente dejará de hacer clic. La probabilidad, en cualquier paso, de que la persona continúe es un factor de amortiguación d. varios estudios han probado diferentes factores de amortiguación, pero generalmente se asume que el factor de amortiguación se establecerá alrededor de 0.85.,

el factor de amortiguación se resta de 1 (y en algunas variaciones del algoritmo, el resultado se divide por el número de documentos (N) en la colección) y este término se agrega al producto del factor de amortiguación y la suma de las puntuaciones de Pagerank entrantes. Es decir,

P R ( a ) = 1 − d N + d ( P R ( B ) L ( B ) + P ( C ) L ( C ) + P R ( D ) L ( D ) + ⋯ ) . {\displaystyle PR(A)={1-d \sobre N}+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \derecho).}

así que el PageRank de cualquier página se deriva en gran parte de los PageRanks de otras páginas., El factor de amortiguación ajusta el valor derivado hacia abajo. El documento original, sin embargo, dio la siguiente fórmula, que ha llevado a cierta confusión:

P R ( a ) = 1 − d + d ( P R ( B ) L ( B ) + P ( 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 \derecho).}

la diferencia entre ellos es que los valores de PageRank en la primera fórmula suman a uno, mientras que en la segunda fórmula cada PageRank se multiplica por N y la suma se convierte en N., Una declaración en el documento de Page y Brin de que» la suma de todos los PageRanks es uno » y las afirmaciones de otros empleados de Google apoyan la primera variante de la fórmula anterior.

Page y Brin confundieron las dos fórmulas en su artículo más popular «The Anatomy of a Large-Scale Hypertextual Web Search Engine», donde erróneamente afirmaron que esta última fórmula formaba una distribución de probabilidad sobre las páginas web.

Google recalcula las puntuaciones del PageRank cada vez que rastrea la Web y reconstruye su índice., A medida que Google aumenta el número de documentos en su colección, la aproximación inicial del PageRank disminuye para todos los documentos.

la fórmula utiliza un modelo de un surfista Aleatorio que llega a su sitio Objetivo después de varios clics, luego cambia a una Página aleatoria. El valor del PageRank de una página refleja la posibilidad de que el surfista al azar aterrice en esa página haciendo clic en un enlace. Se puede entender como una cadena de Markov en la que los estados son páginas, y las transiciones son los enlaces entre páginas, todos los cuales son igualmente probables.,

si una página no tiene enlaces a otras páginas, se convierte en un sumidero y, por lo tanto, termina el proceso de navegación aleatoria. Si el surfista Aleatorio llega a una página de sumidero, elige otra URL al azar y continúa navegando de nuevo.

al calcular PageRank, se supone que las páginas sin enlaces salientes enlazan con todas las demás páginas de la colección. Por lo tanto, sus puntuaciones de PageRank se dividen equitativamente entre todas las demás páginas. En otras palabras, para ser justos con las páginas que no son sumideros, estas transiciones aleatorias se agregan a todos los nodos en la Web. Esta probabilidad residual, d, generalmente se establece en 0.,85, estimado a partir de la frecuencia con la que un surfista promedio usa la función de marcadores de su navegador. Así, la ecuación es la siguiente:

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}\in M(p_{i})}{\frac {PR(p_{j})}{L(p_{j})}}}

Los valores de PageRank son las entradas de la dominante autovector derecho de la modificación de la matriz de adyacencia de ajustaron de manera que cada columna suma a uno.,_{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. los elementos de cada columna suman 1, por lo que la matriz es una matriz estocástica (para más detalles, consulte la sección de cálculo a continuación). Por lo tanto, esta es una variante de la medida de centralidad del vector propio utilizada comúnmente en el análisis de redes.

debido al gran eigengap de la matriz de adyacencia modificada anterior, los valores del vector propio del PageRank se pueden aproximar dentro de un alto grado de precisión dentro de solo unas pocas iteraciones.,

los fundadores de Google, en su artículo original, informaron que el algoritmo de PageRank para una red que consta de 322 millones de enlaces (in-edges y out-edges) converge dentro de un límite tolerable en 52 iteraciones. La convergencia en una red de la mitad del tamaño anterior tomó aproximadamente 45 iteraciones. A través de estos datos, concluyeron que el algoritmo se puede escalar muy bien y que el factor de escala para redes extremadamente grandes sería aproximadamente lineal en log ⁡ n {\displaystyle \log n} , donde n es el tamaño de la red.,

como resultado de la teoría de Markov, se puede demostrar que el PageRank de una página es la probabilidad de llegar a esa página después de un gran número de clics. Esto sucede a igual t-1 {\displaystyle T^{-1}} donde t {\displaystyle t} es la expectativa del número de clics (o saltos aleatorios) necesarios para volver de la página a sí misma.

Una de las principales desventajas de PageRank es que favorece a las páginas más antiguas. Una página Nueva, incluso una muy buena, no tendrá muchos enlaces a menos que sea parte de un sitio existente (un sitio es un conjunto de páginas densamente conectadas, como Wikipedia).,

Se han propuesto varias estrategias para acelerar el cálculo del PageRank.

Se han empleado varias estrategias para manipular el PageRank en esfuerzos concertados para mejorar las clasificaciones de los resultados de búsqueda y monetizar los enlaces publicitarios. Estas estrategias han impactado severamente la confiabilidad del concepto de PageRank, que pretende determinar qué documentos son realmente muy valorados por la Comunidad Web.,

desde diciembre de 2007, cuando comenzó a penalizar activamente los sitios que venden enlaces de texto de pago, Google ha combatido las granjas de enlaces y otros esquemas diseñados para inflar artificialmente el PageRank. Cómo Google identifica las granjas de enlaces y otras herramientas de manipulación de PageRank es uno de los secretos comerciales de Google.

ComputationEdit

PageRank puede ser calculado iterativamente o algebraicamente. El método iterativo se puede ver como el método de iteración de potencia o el método de potencia. Las operaciones matemáticas básicas realizadas son idénticas.,

Iterativeditar

en t = 0 {\displaystyle t = 0}, se asume una distribución de probabilidad inicial, generalmente

P R ( p i ; 0 ) = 1 N {\displaystyle PR(p_{i};0)={\frac {1}{N}}} .

donde N es el número total de páginas, y p i; 0 {\displaystyle p_ {i};0} es la página i en el tiempo 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 A ) t {\displaystyle {\mathcal {M}}:=(K^{-1}A)^{T}} ,

donde A {\displaystyle A} denota la matriz de adyacencia del gráfico y K {\displaystyle K} es la matriz diagonal con los grados exteriores en la diagonal.

el cálculo de probabilidad se hace para cada página en un punto de tiempo, luego se repite para el siguiente punto de tiempo. El cálculo termina cuando para algunos pequeños ϵ {\displaystyle \epsilon }

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

es decir, cuando la convergencia es de suponer.,

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} } .,

La solución existe y es única para 0 < d < 1 {\displaystyle 0<d<1} . Esto se puede ver observando que M {\displaystyle {\mathcal {M}}} es por Construcción una matriz estocástica y por lo tanto tiene un valor propio igual a uno como consecuencia del 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 } .,

tenga en cuenta que en la ecuación (3) de la matriz en el lado derecho en el paréntesis puede ser interpretado como

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

donde P {\displaystyle \mathbf {P} } es una primera distribución de probabilidad. En el 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

Un ejemplo típico es el uso de la programación funcional de Scala con los RDD de Apache Spark para calcular iterativamente los rangos de Página.

MATLAB/OctaveEdit

Ejemplo de código llamando a la función rank definida anteriormente:

M = ;rank2(M, 0.80, 0.001)

PythonEdit

Este ejemplo toma ≈13 iteraciones para converger.