PageRank ( PR ) es un algoritmo utilizado por la búsqueda de Google para clasificar las páginas web en los resultados de sus motores de búsqueda . PageRank lleva el nombre de Larry Page , [1] uno de los fundadores de Google. PageRank es una forma de medir la importancia de las páginas web. Según Google:
Actualmente, PageRank no es el único algoritmo usado por Google para ordenar los resultados de búsqueda, pero es el primer algoritmo que fue usado por la compañía, y es el más conocido.
Descripción [ editar ]
PageRank es un algoritmo de análisis de enlaces y asigna una ponderación numérica a cada elemento de un conjunto de documentos con hipervínculos , como la World Wide Web , con el propósito de "medir" su importancia relativa dentro del conjunto. El algoritmo puede aplicarse a cualquier colección de entidades con citas y referencias recíprocas . El peso numérico que asigna a cualquier elemento E dado se conoce como el PageRank de E y se denota por
Un PageRank es el resultado de un algoritmo matemático basado en el gráfico web , creado por todas las páginas de la World Wide Web como nodos e hipervínculos como bordes, teniendo en cuenta los centros de autoridad como cnn.com o usa.gov . El valor de rango indica la importancia de una página en particular. Un hipervínculo a una página cuenta como un voto de apoyo. El PageRank de una página se define recursivamente y depende del número y la métrica de PageRank de todas las páginas que lo vinculan (" enlaces entrantes "). Una página que está vinculada a muchas páginas con alto PageRank recibe un alto rango.
Se han publicado numerosos trabajos académicos relacionados con PageRank desde el artículo original de Page y Brin. [5] En la práctica, el concepto de PageRank puede ser vulnerable a la manipulación. La investigación se ha llevado a cabo para identificar los rankings de PageRank con influencia falsa. El objetivo es encontrar un medio eficaz para ignorar los enlaces de documentos con PageRank falsamente influenciado. [6]
Otros algoritmos de clasificación basados en enlaces para páginas web incluyen el algoritmo HITS inventado por Jon Kleinberg (utilizado por Teoma y ahora Ask.com ), el proyecto IBM CLEVER , el algoritmo TrustRank y el algoritmo Hummingbird . [7]
Historia [ editar ]
El valor propio problema fue sugerida en 1976 por Gabriel Pinsky y Francis Narin, que trabajó en cientometríaranking de revistas científicas, [8] en 1977 por Thomas Saaty en su concepto de Proceso Analítico Jerárquico qué opciones alternativas ponderadas, [9] y en 1995 por Bradley Love y Steven Sloman como modelo cognitivo para los conceptos, el algoritmo de centralidad. [10] [11]
Un motor de búsqueda llamado " RankDex " de IDD Information Services, diseñado por Robin Li en 1996, desarrolló una estrategia para la clasificación de sitios y la clasificación de páginas. [12] Li se refirió a su mecanismo de búsqueda como "análisis de enlaces", que implicaba clasificar la popularidad de un sitio web en función de la cantidad de otros sitios que se habían vinculado a él. [13] RankDex, el primer motor de búsqueda con algoritmos de clasificación de sitios y puntuación de sitios, se lanzó en 1996. [14] Li patentó la tecnología en RankDex, con su patente registrada en 1997 y otorgada en 1999. [15] Más tarde lo usó cuando fundó Baidu en China en 2000. [16] [17] El fundador de Google, Larry Pagehizo referencia al trabajo de Li como una cita en algunas de sus patentes de Estados Unidos para PageRank. [18] [14] [19]
Larry Page y Sergey Brin desarrollaron PageRank en la Universidad de Stanford en 1996 como parte de un proyecto de investigación sobre un nuevo tipo de motor de búsqueda. [20] Sergey Brin tuvo la idea de que la información en la web podría ordenarse en una jerarquía por "popularidad de enlaces": una página ocupa un lugar más alto a medida que hay más enlaces a ella. [21] Rajeev Motwani y Terry Winograd en coautoría con Page y Brin el primer documento sobre el proyecto, PageRank describir y el prototipo inicial de la búsqueda de Google motor, publicado en 1998: [5] poco después, Page y Brin fundaron Google Inc. ., la empresa detrás del motor de búsqueda de Google. Si bien es solo uno de los muchos factores que determinan el ranking de los resultados de búsqueda de Google, PageRank continúa proporcionando la base para todas las herramientas de búsqueda web de Google. [22]
El nombre "PageRank" hace referencia al nombre del desarrollador Larry Page, así como al concepto de una página web . [23] La palabra es una marca comercial de Google, y el proceso de PageRank ha sido patentado ( patente de EE . UU . 6,285,999 ). Sin embargo, la patente está asignada a la Universidad de Stanford y no a Google. Google tiene derechos de licencia exclusivos sobre la patente de la Universidad de Stanford. La universidad recibió 1.8 millones de acciones de Google a cambio del uso de la patente; Vendió las acciones en 2005 por $ 336 millones. [24] [25]
PageRank fue influenciado por el análisis de citas , desarrollado originalmente por Eugene Garfield en la década de 1950 en la Universidad de Pennsylvania, y por Hyper Search , desarrollado por Massimo Marchiori en la Universidad de Padua . En el mismo año en que se introdujo el PageRank (1998), Jon Kleinberg publicó su trabajo sobre HITS . Los fundadores de Google citan a Garfield, Marchiori y Kleinberg en sus documentos originales. [5] [26]
Algoritmo [ editar ]
El algoritmo PageRank genera una distribución de probabilidad utilizada para representar la probabilidad de que una persona que haga clic al azar en los enlaces llegue a cualquier página en particular. PageRank se puede calcular para colecciones de documentos de cualquier tamaño. En varios artículos de investigación se supone que la distribución se divide equitativamente entre todos los documentos de la colección al comienzo del proceso computacional. Los cálculos de PageRank requieren varios pasos, llamados "iteraciones", a través de la recopilación para ajustar los valores aproximados de PageRank para reflejar con mayor precisión 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 PageRank de 0.5 significa que hay una probabilidad del 50% de que una persona que haga clic en un enlace aleatorio se dirija al documento con el PageRank de 0.5.
Algoritmo simplificado [ editar ]
Supongamos que un pequeño universo de cuatro páginas web: A , B , C y D . Los enlaces de una página a sí mismos son ignorados. 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 en 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 En el resto de esta sección, suponga 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 en partes iguales 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.
Supongamos que, en cambio, 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, 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 . Página C transferiría la totalidad de su valor existente, 0,25, a la única página que conecta, A . Como 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.
En otras palabras, el PageRank otorgado por un enlace saliente es igual al puntaje de PageRank propio del documento dividido por el número de enlaces salientes L () .
En el caso general, el valor de PageRank para cualquier página u se puede expresar como:
- ,
es decir, el valor de PageRank para una página u depende de los valores de PageRank para cada página vcontenida en el conjunto B u (el conjunto que contiene todas las páginas que enlazan con la página u ), dividido por el número L ( v ) de enlaces de la página v .
Factor de amortiguación [ editar ]
La teoría del PageRank sostiene que un surfista imaginario que haga clic al azar en los enlaces 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 en general se asume que el factor de amortiguación se establecerá alrededor de 0.85. [5] En aplicaciones de PageRank a datos biológicos, un análisis bayesiano encuentra que el valor óptimo de d es 0.31. [27]
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 Puntuaciones de PageRank entrantes. Es decir,
Así que el PageRank de cualquier página se deriva en gran parte de los PageRank 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, lo que ha llevado a cierta confusión:
La diferencia entre ellos es que los valores de PageRank en la primera fórmula de la suma 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" [5] y las afirmaciones de otros empleados de Google [28] 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 esta última fórmula formaba una distribución de probabilidad en las páginas web. [5]
Google recalcula los puntajes de 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 surfista aleatorio que se aburre después de varios clics y cambia a una página aleatoria. El valor de PageRank de una página refleja la posibilidad de que el internauta aleatorio aterrice en esa página haciendo clic en un enlace. Puede entenderse como una cadena de Markov en la que los estados son páginas, y las transiciones, que son todas igualmente probables, son los enlaces entre las páginas.
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 surfista aleatorio llega a una página de fregadero, elige otra URL al azar y continúa navegando nuevamente.
Al calcular el PageRank, se supone que las páginas sin enlaces salientes se vinculan a todas las demás páginas de la colección. Sus puntuaciones de PageRank se dividen por lo tanto uniformemente 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, estimada a partir de la frecuencia en que un internauta promedio utiliza la función de marcador de su navegador. Entonces, la ecuación es la siguiente:
dónde son las páginas en consideración, es el conjunto de páginas que enlazan a , es el número de enlaces salientes en la página y es el número total de páginas.
Los valores de PageRank son las entradas del vector propio derecho dominante de la matriz de adyacenciamodificada reescalada para que cada columna sume una. Esto hace que el PageRank sea una métrica especialmente elegante: el vector propio es
donde R es la solución de la ecuación
donde funciona la adyacencia es la relación entre el número de enlaces salientes de la página j a la página i al número total de enlaces salientes de la página j. Y el enlace es 0 si la página no se enlaza a , y normalizado de manera que, para cada j
- ,
es decir, los elementos de cada columna suman hasta 1, por lo que la matriz es una matriz estocástica (para más detalles, consulte la sección de cálculos 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, [29] los valores del eigenvector de PageRank se pueden aproximar dentro de un alto grado de precisión en solo unas pocas iteraciones.
Los fundadores de Google, en su artículo original, [26] informaron que el algoritmo PageRank para una red que consta de 322 millones de enlaces (bordes y bordes) 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, 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 pasa a igual dónde es la expectativa de la cantidad de clics (o saltos aleatorios) necesarios para volver de la página a sí misma.
Una desventaja principal de PageRank es que favorece 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. [30]
Se han empleado diversas 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 gravemente la confiabilidad del concepto de PageRank, [ cita requerida ] que pretende determinar qué documentos son realmente 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 .
No hay comentarios:
Publicar un comentario