PageRank
PageRank™ es un algoritmo que utiliza el motor de búsqueda de Google para clasificar los sitios web en los resultados de búsqueda. PageRank mide la importancia de una página contando la cantidad y la calidad de los enlaces que apuntan a ella. No es el único algoritmo que utiliza Google para clasificar las páginas web, pero sí el primero que utilizó la compañía y el más conocido. Sus propiedades son ampliamente analizadas por expertos en optimización de motores de búsqueda (SEO). El proceso PageRank fue patentado por la Universidad de Stanford en Estados Unidos con el número 6.285.999. Solo el nombre PageRank es una marca registrada de Google. Google posee los derechos exclusivos de licencia de la patente PageRank. La Universidad de Stanford recibió 1,8 millones de acciones de Google a cambio del uso de la patente. Las acciones se vendieron en 2005 por 336 millones de dólares. ==Descripción== Para construir la métrica PageRank, la web se concibe como una red de citas; cada nodo corresponde a una página y cada enlace corresponde a una referencia de una página a otra (hipervínculo). La métrica asigna un valor a cada nodo (página) de la red; un valor más alto corresponde a un nodo más importante. Desde la perspectiva de la teoría de redes, PageRank es una métrica de centralidad. Esta métrica aprovecha la estructura de los hipervínculos en la web para generar un valor para cada página de la red. Un hipervínculo a una página se considera un "voto" de apoyo. El valor de PageRank de una página depende del número de páginas y de la métrica de PageRank de las páginas que enlazan a ella. Una página tiene un valor de PageRank más alto si: * muchas páginas enlazan a ella * algunas páginas enlazan a ella con una métrica de PageRank alta (una página es importante si páginas importantes enlazan a ella). [Imagen:PageRanks-Example.svg|derecha|tamaño|400px|Métrica de PageRank para nodos en una red simple, expresada en porcentajes. (Google utiliza una escala logarítmica).] El nodo C tiene un valor de PageRank superior al del nodo E. Aunque existen pocos enlaces a C, el enlace a C proviene de un nodo importante y, por lo tanto, tiene un valor alto. Si un usuario comienza en un nodo aleatorio con una probabilidad del 85 % de elegir un enlace aleatorio del nodo que está visitando y una probabilidad del 15 % de saltar a un nodo elegido al azar de toda la red, ese usuario llegará al nodo E el 8,1 % de las veces. (Una probabilidad del 15 % de saltar a un nodo arbitrario corresponde a un factor de amortiguación del 85 %). Sin amortiguación, cualquier usuario terminaría en los nodos A, B o C, y todos los demás tendrían un valor de PageRank de cero. Al utilizar el factor de amortiguación, el nodo A se conecta con todos los nodos de la red, incluso si no tiene conexiones con otros nodos. == Google y PageRank == El sistema PageRank es utilizado por el motor de búsqueda Google para determinar la relevancia o importancia de una página. Fue desarrollada por los fundadores de Google, Larry Page y Sergey Brin, mientras eran estudiantes en la Universidad de Stanford en 1998. Google mantiene una lista de miles de millones de páginas ordenadas por importancia; es decir, cada página tiene su relevancia en la web en su conjunto. Esta base de datos de páginas contiene información desde la página más importante del mundo hasta la menos importante. Esta importancia se determina por el número de votos que recibe una página. Un voto es un enlace a esa página en cualquier parte de la web. Los votos para las páginas más importantes tienen mayor valor que los votos para las menos importantes. Este criterio de clasificación de páginas, según muchos, es bastante democrático, ya que refleja la opinión de la web sobre un término determinado. Cabe recordar que se tienen en cuenta unos diez mil millones de páginas. La relevancia de las páginas más importantes está garantizada, clasificada y elegida por la propia web. Además, todas las páginas tienen la misma probabilidad de ascender en esta clasificación, obteniendo votos en toda la web. Una buena unidad de medida para definir el PageRank de una página puede ser el porcentaje (%) de páginas en las que es más importante. Por ejemplo, si una página tiene un PageRank del 33%, significa que es más importante que un tercio de toda la web. Si su PageRank es del 99%, significa que es superior a casi todas las páginas web. Sin embargo, es posible manipular el PageRank asignando "enlaces" que no guardan relación con el propósito de la página, modificando el orden de los resultados en las búsquedas de Google e induciendo resultados irrelevantes o sesgados. Un ejemplo reciente de esto es la búsqueda de [[Google:failure|failure]] o [[Google:miserable+failure|miserable failure]], que devolvió como primer resultado la biografía oficial de la [[Casa Blanca]] del presidente de los [[Estados Unidos]], [[George W. Bush]], y luego la página de [[Michael Moore]], un declarado enemigo del presidente estadounidense. Este proceso se conoció como «Googlebombing». A pesar de ello, Google ha eliminado algunos resultados derivados de este tipo de ataques. == Historia == PageRank fue desarrollado en la Universidad de Stanford por Larry Page (de ahí su nombre) y Sergey Brin en 1996, como parte de un proyecto de investigación sobre un nuevo tipo de motor de búsqueda. Sergey Brin tuvo la idea de que la información en la web podía ordenarse en una jerarquía de «popularidad de enlaces»: una página es más importante si tiene más hipervínculos que apuntan a ella. Rajeev Motwani y Winograd Terry fueron coautores del proyecto. El primer artículo sobre el proyecto, que describía la métrica PageRank y el prototipo inicial del motor de búsqueda de Google, se publicó en 1998.Poco después, Page y Brin fundaron Google Inc., la empresa responsable del motor de búsqueda Google. La métrica PageRank se inspiró en el análisis de citas, desarrollado por Eugene Garfield en 1950 en la Universidad de Pensilvania, y en el método de "Hyper Search", desarrollado por Massimo Marchiori de la Universidad de Padua. En el mismo año en que se introdujo PageRank (1998), Jon Kleinberg publicó su trabajo sobre HITS. Los fundadores de Google citaron a Marchiori y Kleinberg en su artículo original. El motor de búsqueda RankDex, de IDD Information Services y diseñado por Robin Li, explora desde 1996 una estrategia similar para puntuar y clasificar páginas. La tecnología empleada en RankDex se patentó en 1999 y posteriormente se utilizó cuando Li fundó Baidu en China. El trabajo de Li se cita en varias patentes, incluyendo los métodos de búsqueda de Google y los de Larry Page. El algoritmo: La métrica PageRank de una página representa la probabilidad de que un usuario acceda a ella haciendo clic aleatoriamente en enlaces. El cálculo de PageRank es escalable, lo que significa que puede ejecutarse con rapidez incluso si el número de páginas en la red aumenta considerablemente. El cálculo de PageRank es iterativo, es decir, requiere varias iteraciones, donde los valores obtenidos en cada una convergen a los valores de PageRank deseados. En la primera iteración, se asigna un valor inicial de PageRank por igual a todas las páginas (N es el número total de páginas). === Algoritmo simplificado === Imaginemos una red de solo 4 páginas: "A", "B", "C" y "D". Se ignoran los enlaces de una página a sí misma y los enlaces múltiples entre dos páginas. Inicialmente, la suma de los valores PageRank de todas las páginas web correspondía al número de páginas en la web. En versiones posteriores, PageRank comenzó a tomar valores entre 0 y 1, representando una distribución de probabilidad, es decir, la probabilidad de que un usuario, navegando por enlaces aleatoriamente, llegue a una página específica. En el primer paso del proceso iterativo de cálculo de PageRank, todas las páginas tienen el mismo valor PageRank. En nuestro ejemplo de 4 páginas, el primer paso consiste en asignar un valor PageRank de 0,25 a cada una de las cuatro páginas. Nótese que la suma de los valores PageRank de todas las páginas es 1. [[File:Simple 4 nodes graph 3 nodes link to one.jpg|thumb|center|alt=Fig. 1- All pages have only one reference to page A.|Fig. En una red con la configuración mostrada en la figura anterior, en la segunda iteración, cada enlace transfiere el valor 0.25 al PageRank de A, es decir: [[File:Pagerank.pt.fig2.jpg|thumb|center|alt=Fig. 2- Páginas que hacen referencia a más de una página|Fig. 2- Páginas que hacen referencia a más de una página.]] En el caso de la red anterior, en la segunda iteración, el valor de "B" se transfiere en partes iguales a "A" (0.125) y a "C" (0.125). Como "D" hace referencia a 3 páginas, su valor a transferir se divide entre tres; en este caso, el PageRank de "A" recibe los siguientes valores. Por lo tanto, la contribución de un enlace al PageRank de la página referenciada es igual al valor de PageRank de la página con el enlace, dividido por el número de enlaces que contiene la página. Si representamos el número de enlaces de una página mediante L(), podemos reescribir la expresión anterior para nuestra red de 4 páginas: Generalizando, el valor de PageRank para una página u se puede expresar de la siguiente manera: El valor de PageRank de una página "u" depende de los valores de PageRank de cada página "v" contenida en el conjunto "B".uEl conjunto de todas las páginas que hacen referencia a "u" dividido por el número de referencias "L" ("v") existentes en "v". === Páginas sin enlaces === El proceso iterativo de cálculo de PageRank presenta problemas cuando una página no tiene enlaces a otras páginas. [[File:Pagerank.pt.fig3.jpg|thumb|center|alt=Fig. 3- Page without links|Fig. 3- Page without links.]] Si se aplica el cálculo a la red de la figura anterior, se obtiene un valor de cero para las páginas "A" y "B". En cada iteración, "B" recibe parte del PageRank de "A" (en este caso particular, "B" recibe todo el PageRank de "A", pero en una red más compleja donde "A" tuviera enlaces a otras páginas, "B" recibiría solo una parte del PageRank). Dado que "B" no tiene enlaces, no transmite su valor a otras páginas, en este caso, a "A". Esto produce un efecto de drenaje de PageRank en la red. === Sumidero de Rank === Otro problema que se presenta en el cálculo de PageRank ocurre cuando una red contiene un sumidero de ranking. [[File:Pagerank.pt.fig4.jpg|thumb|center|alt=Fig. 4- Ejemplo de un sumidero de ranking|Fig. 4- Ejemplo de un sumidero de ranking.]] Considere un bucle cerrado de páginas interconectadas, pero ninguna de las páginas se conecta a una página fuera del bucle. En tal caso, el cálculo de PageRank se "atasca" en un bucle infinito; en cada iteración, el valor de PageRank se transmite de una página a otra dentro del bucle, sin distribuirse nunca a las páginas fuera del mismo. ...y sin que los valores converjan a valores PageRank estacionarios. === Factor de amortiguación === Los problemas descritos anteriormente se resuelven mediante un concepto introducido por PageRank llamado factor de amortiguación. La teoría de PageRank considera que un usuario hipotético (o navegante) que sigue aleatoriamente los enlaces entre páginas eventualmente se aburrirá y dejará de seguirlos. La probabilidad, en cada paso, de que el usuario continúe siguiendo los enlaces es el factor de amortiguación "d". El factor de amortiguación, al ser una probabilidad, puede variar entre 0 y 1. Por lo tanto, el valor de "PR(A)" tiene un componente que corresponde a la contribución de las páginas que apuntan a "A", ponderado por la probabilidad "d" de que el usuario siga los enlaces de la página, y un componente que corresponde a que el usuario haya seleccionado la página aleatoriamente, ponderado por la probabilidad de que el usuario no siga los enlaces de la página (1-d). Con la introducción del factor de amortiguación "d", el cálculo del valor de PageRank tiene la siguiente expresión, que representa el número total de páginas: Existen otras variaciones para calcular PageRank, pero la expresión anterior tiene la particularidad de que la suma de los valores de PageRank de todas las páginas es 1. Esto da una distribución de probabilidad, es decir, la probabilidad de que un usuario llegue a la página A. El factor de amortiguación introduce las siguientes características en el cálculo de PageRank: * Una página, simplemente por existir, tiene una probabilidad igual a la de todas las demás. Otras opciones incluyen ser seleccionada por elección aleatoria del usuario. Una página sin enlaces está conectada a todas las páginas de la red. Se resuelven problemas con páginas sin enlaces y bucles (sumidero de rango). El factor de amortiguación «d» puede tomar valores entre cero y uno, como ya se indicó. Con «d» = 1, se utiliza la forma simplificada del algoritmo; con «d» = 0, no se asigna peso a la estructura de hipervínculos entre las páginas de la red, y todas las páginas tienen un valor PageRank igual a n, donde n es el número de páginas en la red. Por lo tanto, cuanto más se acerque «d» a 1, mayor será el peso que se le dé a la estructura de la red. Normalmente se asigna un valor de 0,85 al factor de amortiguación. === Representación matricial === Suponiendo que la red consta de las páginas "'P1'", "'P2'", ..., "'Pn'", "'M(Pi)'" representa el conjunto de páginas que hacen referencia a "'Pi'", y "'L(Pj)'" representa el número de referencias a la página "'Pj'". La expresión para calcular el valor de PageRank se puede reescribir como sigue: : (*) El vector "'R'" que contiene el valor de PageRank para todas las páginas se puede representar como sigue: Construyendo una matriz de transición "'M'" de nxn, donde n es el número total de páginas, un elemento "'Mij'" (fila "'i'" y columna "'j'") viene dado por la función: :, si no hay ninguna referencia a la página "'p'".j"' a la página "'pi"' :, si hay una referencia a la página "'pj"' a la página "'pi”', : es el número de referencias existentes en ”'pj" (grado de salida o número de enlaces que salen de "pjNótese que la función está normalizada; es decir: La expresión para calcular PageRank para todas las páginas se puede escribir en la siguiente forma matricial: Si representamos con 1 el vector de unos, con el valor 1 en todos sus elementos, con n filas y una columna, tenemos: Dado que la suma de todos los elementos del vector "'R'" es 1 (es decir, "'PR(P1)+PR(P2)+...PR(Pn)" = 1), entonces el producto de "'R'" por la matriz "'E' nxn", con el valor 1 en todos sus elementos, es igual al vector "'1'". Por lo tanto, podemos reescribir la expresión para calcular R de la siguiente manera: Factorizando "'R'", obtenemos: Es decir, "'R'" es el vector propio de la matriz de adyacencia modificada, para el valor propio 1, donde: Por lo tanto, la métrica PageRank se puede considerar una variante de la métrica de centralidad de vector propio. === Cálculo iterativo de la métrica PageRank === Designemos los valores iniciales de PageRank como "x(0)" y los valores calculados en la iteración "t" como "x(t)". En la primera iteración "t=0", se asigna un valor a todas las páginas; es decir, cada elemento del vector "x(0)" tiene el valor: En cada iteración "t+1", calculamos el valor de "x(t+1)" multiplicando la matriz por el vector "x(t)" (valores de PageRank calculados en la iteración anterior): La matriz tiene las siguientes propiedades* irreducible * primitivo * estocástico Basándonos en estas propiedades de , se demuestra que "x(t)" converge al vector propio "R". El cálculo iterativo finaliza cuando la variación de x(t) con respecto a x(t+1) es menor que un valor predefinido. Este método de cálculo es escalable; en una red con 322 millones de conexiones, se observa convergencia, con una tolerancia razonable, en aproximadamente 52 iteraciones. La velocidad de convergencia, en este método de cálculo, depende del valor de amortiguamiento "d". == Determinación del PageRank == Para comprobar el PageRank de una página determinada, existen dos opciones: * Instalar la [[Google Toolbar]]
Publicar comentario