PageRank

Supongamos 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 enlaces salientes múltiples 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 versión original de PageRank, la suma de PageRank de 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 que se transfiere de una página determinada a los destinos de sus enlaces salientes en la siguiente iteración se divide equitativamente entre todos los enlaces salientes.

Si los únicos enlaces del 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.

${\displaystyle PR(A)=PR(B)+PR(C)+PR(D).\,}$

Supongamos que la página B tiene un enlace a las páginas C y A , la página C tiene un enlace a la página A , y la página D tiene 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 (0,125) a la página A y la otra mitad (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 tiene tres enlaces salientes, transferiría un tercio de su valor existente, o aproximadamente 0,083, a A. Al finalizar esta iteración, la página A tendrá un PageRank de aproximadamente 0,458.

${\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 PageRank del propio documento dividida por el número de enlaces salientes L() .

${\displaystyle PR(A)={\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}.\,}$

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

${\displaystyle PR(u)=\sum _{v\in B_{u}}{\frac {PR(v)}{L(v)}}}$,

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

La teoría PageRank sostiene que un usuario hipotético que hace clic aleatoriamente en enlaces eventualmente dejará de hacerlo. La probabilidad, en cualquier paso, de que la persona continúe siguiendo los enlaces es un factor de amortiguación d . La probabilidad de que, en cambio, salte a cualquier página aleatoria es 1 - d . Diversos estudios han probado diferentes factores de amortiguación, pero generalmente se asume que el factor de amortiguación se establecerá alrededor de 0,85. ^{[ 6 ]}

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; en la literatura técnica a esto a veces se le denomina "tamaño de la biblioteca") y este término se suma luego al producto del factor de amortiguación y la suma de las puntuaciones PageRank entrantes. Es decir,

${\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).}$

Así, el PageRank de cualquier página se deriva en gran medida de los PageRanks de otras páginas. El factor de amortiguación ajusta el valor derivado a la baja. Sin embargo, el artículo original proporcionaba la siguiente fórmula, lo que ha generado cierta confusión:

${\displaystyle PR(A)=1-d+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right).}$

La diferencia entre ellas es que los valores de PageRank en la primera fórmula suman uno, mientras que en la segunda fórmula cada PageRank se multiplica por N y la suma se convierte en N. Una afirmación en el artículo de Page y Brin de que "la suma de todos los PageRanks es uno" ^{[ 6 ]} y afirmaciones de otros empleados de Google ^{[ 36 ]} respaldan la primera variante de la fórmula anterior.

Page y Brin confundieron las dos fórmulas en su artículo más popular, "La anatomía de un motor de búsqueda web hipertextual a gran escala", donde afirmaron erróneamente que la segunda fórmula formaba una distribución de probabilidad sobre las páginas web. ^{[ 6 ]}

Google recalcula la puntuación 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 de PageRank disminuye para todos los documentos.

La fórmula utiliza un modelo de un usuario aleatorio que llega a su sitio web objetivo tras varios clics y luego cambia a una página aleatoria. El valor PageRank de una página refleja la probabilidad de que el usuario aleatorio acceda a ella haciendo clic en un enlace. Puede entenderse como una cadena de Markov en la que los estados son las páginas y las transiciones son los enlaces entre ellas, todas con la misma probabilidad.

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

Al calcular PageRank, se asume que las páginas sin enlaces salientes enlazan con todas las demás páginas de la colección. Por lo tanto, sus puntuaciones 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 suman a todos los nodos de la web. Esta probabilidad residual, d , se suele fijar en 0,85, estimada a partir de la frecuencia con la que un usuario promedio utiliza la función de marcadores de su navegador. Así pues, la ecuación es la siguiente:

${\displaystyle PR(p_{i})={\frac {1-d}{N}}+d\sum _{p_{j}\in M(p_{i})}{\frac {PR(p_{j})}{L(p_{j})}}}$

dónde${\displaystyle p_{1},p_{2},...,p_{N}}$son las páginas que se están considerando,${\displaystyle M(p_{i})}$es el conjunto de páginas que enlazan con${\displaystyle p_{i}}$,${\displaystyle L(p_{j})}$es el número de enlaces salientes en la página${\displaystyle p_{j}}$, y${\displaystyle N}$es el número total de páginas.

Los valores de PageRank son las entradas del vector propio derecho dominante de la matriz de adyacencia modificada reescalada de modo que cada columna sume uno. Esto hace de PageRank una métrica particularmente elegante: el vector propio es

${\displaystyle \mathbf {R} ={\begin{bmatrix}PR(p_{1})\\PR(p_{2})\\\vdots \\PR(p_{N})\end{bmatrix}}}$

donde R es la solución de la ecuación

${\displaystyle \mathbf {R} ={\begin{bmatrix}{(1-d)/N}\\{(1-d)/N}\\\vdots \\{(1-d)/N}\end{bmatrix}}+d{\begin{bmatrix}\ell (p_{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} }$

donde la función de adyacencia${\displaystyle \ell (p_{i},p_{j})}$es la relación entre el número de enlaces salientes de la página j a la página i y el número total de enlaces salientes de la página j. La función de adyacencia es 0 si la página${\displaystyle p_{j}}$no enlaza con${\displaystyle p_{i}}$y normalizado de tal manera que, para cada j

${\displaystyle \sum _{i=1}^{N}\ell (p_{i},p_{j})=1}$,

Es decir, la suma de los elementos de cada columna es igual a 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, se trata de una variante de la medida de centralidad de vector propio que se utiliza habitualmente en el análisis de redes .

Debido a la gran brecha propia de la matriz de adyacencia modificada anterior, ^{[ 37 ]} los valores del vector propio de PageRank se pueden aproximar con un alto grado de precisión en tan solo unas pocas iteraciones.

Los fundadores de Google, en su artículo original, ^{[ 35 ]} informaron que el algoritmo PageRank para una red que consta de 322 millones de enlaces (aristas de entrada y de salida) 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${\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 resulta ser igual a${\displaystyle t^{-1}}$dónde${\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 forme 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 de PageRank. ^{[ 38 ]}

Se han empleado diversas estrategias para manipular PageRank en un esfuerzo conjunto por mejorar el posicionamiento en los resultados de búsqueda y monetizar los enlaces publicitarios. Estas estrategias han afectado gravemente la fiabilidad del concepto PageRank, que pretende determinar qué documentos son realmente valorados por la comunidad web.

Desde diciembre de 2007, cuando comenzó a penalizar activamente los sitios que vendían enlaces de texto pagados, Google ha combatido las granjas de enlaces y otros esquemas diseñados para inflar artificialmente el PageRank. La forma en que Google identifica las granjas de enlaces y otras herramientas de manipulación del PageRank es uno de sus secretos comerciales .

PageRank se puede calcular de forma iterativa o algebraica. El método iterativo se puede considerar como el método de iteración de potencia ^{[ 39 ] [ 40 ]} o el método de potencia. Las operaciones matemáticas básicas que se realizan son idénticas.

El PageRank de un grafo no dirigido${\displaystyle G}$es estadísticamente cercano a la distribución de grados del gráfico.${\displaystyle G}$, ^{[ 41 ]} pero generalmente no son idénticos: Si${\displaystyle R}$es el vector PageRank definido anteriormente, y${\displaystyle D}$es el vector de distribución de grados

${\displaystyle D={1 \over 2|E|}{\begin{bmatrix}\deg(p_{1})\\\deg(p_{2})\\\vdots \\\deg(p_{N})\end{bmatrix}}}$

dónde${\displaystyle \deg(p_{i})}$denota el grado del vértice${\displaystyle p_{i}}$, y${\displaystyle E}$es el conjunto de aristas del grafo, entonces, con${\displaystyle Y={1 \over N}\mathbf {1} }$, ^{[ 42 ]} muestra que:

${\displaystyle {1-d \over 1+d}\|Y-D\|_{1}\leq \|R-D\|_{1}\leq \|Y-D\|_{1},}$

Es decir, el PageRank de un grafo no dirigido es igual al vector de distribución de grados si y solo si el grafo es regular, es decir, cada vértice tiene el mismo grado.

Daugulis describió una generalización de PageRank para el caso de clasificar dos grupos de objetos interactuantes. ^{[ 43 ]} En las aplicaciones puede ser necesario modelar sistemas que tengan objetos de dos tipos donde se define una relación ponderada en pares de objetos. Esto lleva a considerar grafos bipartitos . Para tales grafos se pueden definir dos matrices irreducibles relacionadas, positivas o no negativas, correspondientes a conjuntos de partición de vértices. Se pueden calcular clasificaciones de objetos en ambos grupos como vectores propios correspondientes a los valores propios positivos máximos de estas matrices. Los vectores propios normalizados existen y son únicos por el teorema de Perron o Perron-Frobenius . Ejemplo: consumidores y productos. El peso de la relación es la tasa de consumo del producto.

Sarma et al. describen dos algoritmos distribuidos basados ​​en paseos aleatorios para calcular el PageRank de los nodos en una red. ^{[ 44 ]} Un algoritmo toma${\displaystyle O(\log n/\epsilon )}$rondas con alta probabilidad en cualquier grafo (dirigido o no dirigido), donde n es el tamaño de la red y${\displaystyle \epsilon }$es la probabilidad de reinicio (${\displaystyle 1-\epsilon }$(que se denomina factor de amortiguación) utilizado en el cálculo de PageRank. También presentan un algoritmo más rápido que toma${\displaystyle O({\sqrt {\log n}}/\epsilon )}$rondas en grafos no dirigidos. En ambos algoritmos, cada nodo procesa y envía una cantidad de bits por ronda que es polilogarítmica en n, el tamaño de la red.

La barra de herramientas de Google incluía desde hace tiempo una función de PageRank que mostraba el PageRank de una página visitada como un número entero entre 0 (menos popular) y 10 (más popular). Google no había revelado el método específico para determinar el valor de PageRank de la barra de herramientas, que debía considerarse solo una indicación aproximada del valor de un sitio web. El "PageRank de la barra de herramientas" estaba disponible para los administradores de sitios verificados a través de la interfaz de Google Webmaster Tools. Sin embargo, el 15 de octubre de 2009, un empleado de Google confirmó que la empresa había eliminado PageRank de su sección de Webmaster Tools , afirmando: "Llevamos mucho tiempo diciéndole a la gente que no deberían centrarse tanto en PageRank. Muchos propietarios de sitios parecen pensar que es la métrica más importante que deben monitorizar, lo cual simplemente no es cierto". ^{[ 45 ]}

El PageRank de la barra de herramientas se actualizaba con muy poca frecuencia. La última actualización fue en noviembre de 2013. En octubre de 2014, Matt Cutts anunció que no habría otra actualización visible del PageRank. ^{[ 46 ]} En marzo de 2016, Google anunció que dejaría de dar soporte a esta función y que la API subyacente pronto dejaría de funcionar. ^{[ 47 ]} El 15 de abril de 2016, Google desactivó la visualización de los datos de PageRank en la barra de herramientas de Google, ^{[ 48 ]} aunque el PageRank siguió utilizándose internamente para clasificar el contenido en los resultados de búsqueda. ^{[ 49 ]}

La página de resultados del motor de búsqueda (SERP) es el resultado real que devuelve un motor de búsqueda en respuesta a una consulta de palabras clave. La SERP consta de una lista de enlaces a páginas web con fragmentos de texto asociados, anuncios pagados, fragmentos destacados y preguntas y respuestas. El posicionamiento SERP de una página web se refiere a la posición del enlace correspondiente en la SERP, donde una mejor posición significa un mejor posicionamiento SERP. El posicionamiento SERP de una página web es una función no solo de su PageRank, sino también de un conjunto relativamente grande y continuamente ajustado de factores (más de 200). ^{[ 50 ]} La optimización para motores de búsqueda (SEO) tiene como objetivo influir en el posicionamiento SERP de un sitio web o un conjunto de páginas web.

El posicionamiento de una página web en los resultados de búsqueda de Google (SERP) para una palabra clave depende de la relevancia y la reputación, también conocidas como autoridad y popularidad. El PageRank es el indicador que utiliza Google para evaluar la reputación de una página web: no depende de una palabra clave específica. Google utiliza una combinación de la autoridad de la página web y del sitio web para determinar la autoridad general de una página web que compite por una palabra clave. ^{[ 51 ]} El PageRank de la página de inicio de un sitio web es el mejor indicador que ofrece Google para la autoridad del sitio web. ^{[ 52 ]}

Tras la introducción de Google Places en los resultados de búsqueda orgánicos (SERP) principales, numerosos factores además de PageRank influyen en la clasificación de un negocio en los resultados de búsqueda locales. ^{[ 53 ]} Cuando Google explicó los motivos de la descontinuación de PageRank en la sesión de preguntas y respuestas de marzo de 2016, anunció que los enlaces y el contenido eran los principales factores de clasificación. RankBrain ya había sido anunciado en octubre de 2015 como el tercer factor de clasificación, por lo que Google confirmó oficialmente los tres factores principales. ^{[ 54 ]}

El PageRank del Directorio de Google era una medida de 8 unidades. A diferencia de la barra de herramientas de Google, que mostraba un valor numérico de PageRank al pasar el ratón por encima de la barra verde, el Directorio de Google solo mostraba la barra, nunca los valores numéricos. El Directorio de Google se cerró el 20 de julio de 2011. ^{[ 55 ]}

Se sabía que el PageRank que se mostraba en la barra de herramientas podía falsificarse fácilmente . La redirección de una página a otra, ya sea mediante una respuesta HTTP 302 o una etiqueta meta "Refresh" , provocaba que la página de origen adquiriera el PageRank de la página de destino. Por lo tanto, una página nueva con PR 0 y sin enlaces entrantes podía adquirir PR 10 al redirigir a la página de inicio de Google. La falsificación suele detectarse realizando una búsqueda en Google de la URL de origen; si en los resultados aparece la URL de un sitio completamente diferente, esta última podría representar el destino de una redirección.

Para fines de optimización de motores de búsqueda , algunas empresas ofrecen vender enlaces con alto PageRank a los webmasters. ^{[ 56 ]} Dado que se cree que los enlaces de páginas con mayor PR son más valiosos, tienden a ser más caros. Puede ser una estrategia de marketing efectiva y viable comprar anuncios de enlaces en páginas de contenido de sitios relevantes y de calidad para generar tráfico y aumentar la popularidad de los enlaces de un webmaster. Sin embargo, Google ha advertido públicamente a los webmasters que si se descubre que venden enlaces con el propósito de conferir PageRank y reputación, sus enlaces serán devaluados (ignorados en el cálculo del PageRank de otras páginas). La práctica de comprar y vender ^{[ 57 ]} es objeto de un intenso debate en la comunidad de webmasters. Google aconsejó a los webmasters que utilicen el atributo HTML nofollow en los enlaces pagados. Según Matt Cutts , a Google le preocupa que los webmasters intenten manipular el sistema y, por lo tanto, reduzcan la calidad y la relevancia de los resultados de búsqueda de Google. ^{[ 56 ]}

En 2019, Google anunció dos atributos de enlace adicionales que proporcionan pistas sobre qué enlaces considerar o excluir en la Búsqueda: rel="ugc" como etiqueta para contenido generado por el usuario , como comentarios; y rel="sponsored"como etiqueta para anuncios u otros tipos de contenido patrocinado. relTambién se permiten varios valores; por ejemplo, rel="ugc sponsored"se puede usar para indicar que el enlace proviene de contenido generado por el usuario y es patrocinado. ^{[ 58 ]}

Aunque PageRank se ha vuelto menos importante para fines de SEO, la existencia de enlaces entrantes de sitios web más populares sigue impulsando una página web a posiciones más altas en los rankings de búsqueda. ^{[ 59 ]}

Un surfista más inteligente que salta probabilísticamente de página en página dependiendo del contenido de las páginas y los términos de consulta que el surfista está buscando. Este modelo se basa en una puntuación PageRank de una página que depende de la consulta, que como su nombre indica también es una función de la consulta. Cuando se le da una consulta de múltiples términos,${\displaystyle Q=\{q1,q2,\cdots \}}$, el surfista selecciona un${\displaystyle q}$según alguna distribución de probabilidad,${\displaystyle P(q)}$y utiliza ese término para guiar su comportamiento durante un gran número de pasos. Luego selecciona otro término según la distribución para determinar su comportamiento, y así sucesivamente. La distribución resultante sobre las páginas web visitadas es QD-PageRank. ^{[ 60 ]}

PageRank se ha utilizado para cuantificar el impacto científico de los investigadores. Las redes subyacentes de citas y colaboración se utilizan junto con el algoritmo PageRank para generar un sistema de clasificación para publicaciones individuales que se propaga a autores individuales. Se ha demostrado que el nuevo índice conocido como índice PageRank (Pi) es más justo en comparación con el índice h, dados los numerosos inconvenientes que presenta este último. ^{[ 62 ]}

Para el análisis de redes de proteínas en biología, PageRank también es una herramienta útil. ^{[ 63 ] [ 64 ]}

En cualquier ecosistema, se puede utilizar una versión modificada de PageRank para determinar las especies que son esenciales para la salud continua del medio ambiente. ^{[ 65 ]}

Un uso similar y más reciente de PageRank consiste en clasificar los programas de doctorado académicos según su historial de colocación de sus egresados ​​en puestos docentes. En términos de PageRank, los departamentos académicos se vinculan entre sí mediante la contratación de sus profesores entre sí (y entre ellos mismos). ^{[ 66 ]}

Recientemente se ha propuesto una versión de PageRank como sustituto del factor de impacto tradicional del Institute for Scientific Information (ISI) ^{[ 67 ]} , y se ha implementado tanto en Eigenfactor como en SCImago . En lugar de simplemente contar el total de citas a una revista, la "importancia" de cada cita se determina mediante PageRank.

En neurociencia , se ha descubierto que el PageRank de una neurona en una red neuronal se correlaciona con su tasa de disparo relativa. ^{[ 68 ]}

Twitter utiliza el PageRank personalizado para mostrar a los usuarios otras cuentas que podrían interesarles. ^{[ 69 ]}

El producto de búsqueda de sitios de Swiftype crea un "PageRank específico para cada sitio web" al analizar las señales de importancia de cada sitio web y priorizar el contenido en función de factores como el número de enlaces desde la página de inicio. ^{[ 70 ]}

Un rastreador web puede usar PageRank como una de las métricas de importancia que utiliza para determinar qué URL visitar durante un rastreo de la web. Uno de los primeros documentos de trabajo ^{[ 71 ]} que se utilizaron en la creación de Google es Efficient crawling through URL ordering [ ^{72 ] ,} que analiza el uso de varias métricas de importancia diferentes para determinar con qué profundidad y qué cantidad de un sitio rastreará Google. PageRank se presenta como una de estas métricas de importancia, aunque se enumeran otras como el número de enlaces entrantes y salientes de una URL y la distancia desde el directorio raíz de un sitio hasta la URL.

El PageRank también puede utilizarse como metodología para medir el impacto aparente de una comunidad como la Blogosfera en la Web en general. Este enfoque emplea, por lo tanto, el PageRank para medir la distribución de la atención, reflejando el paradigma de redes libres de escala .

En 2005, en un estudio piloto en Pakistán, se utilizó la Democracia Profunda Estructural (SD2) ^{[ 73 ] [ 74 ]} para la selección de líderes en un grupo de agricultura sostenible llamado Contact Youth. La SD2 utiliza PageRank para el procesamiento de los votos por poder transitivos, con la restricción adicional de exigir al menos dos votos por poder iniciales por votante, y todos los votantes son candidatos por poder. Se pueden crear variantes más complejas sobre la base de la SD2, como agregar votos por poder especializados y votos directos para temas específicos, pero la SD2, como sistema paraguas subyacente, exige que siempre se utilicen votos por poder generalistas.

En el deporte, el algoritmo PageRank se ha utilizado para clasificar el rendimiento de: equipos en la Liga Nacional de Fútbol Americano (NFL) en los EE. UU.; ^{[ 75 ]} jugadores de fútbol individuales; ^{[ 76 ]} y atletas en la Liga Diamante. ^{[ 77 ]}

PageRank se ha utilizado para clasificar espacios o calles y predecir cuántas personas (peatones o vehículos) llegan a cada espacio o calle. ^{[ 78 ] [ 79 ]} En semántica léxica se ha utilizado para realizar desambiguación del sentido de las palabras , ^{[ 80 ]} similitud semántica , ^{[ 81 ]} y también para clasificar automáticamente los conjuntos de sinónimos de WordNet según la intensidad con la que poseen una propiedad semántica determinada, como la positividad o la negatividad. ^{[ 82 ]}

La forma en que un sistema de tráfico cambia su modo operativo puede describirse mediante transiciones entre estados cuasiestacionarios en estructuras de correlación del flujo de tráfico. PageRank se ha utilizado para identificar y explorar los estados dominantes entre estos estados cuasiestacionarios en los sistemas de tráfico. ^{[ 83 ]}