Method for node ranking in a linked database
(Método para la jerarquización de nodos en una base de datos enlazada)
La patente más famosa de Google es una de las principales ventajas competitivas que permitió a esta compañia aplastar a sus competidores en el campo de las busquedas en internet y hacerse el gigante que son hoy*. El Page Rank, como todos la conocemos, es una idea genial para hallar el valor o "importancia" que tiene una página web determinada. Esta "importancia" se emplea después para mostrar los resultados de mayor calidad cuando realizamos una búsqueda en Google. La calidad de los resultados de Google empleando este método (combinado, por supuesto, con otros algoritmos) es lo que nos hizo a todos abandonar nuestros antiguos buscadores (Altavista, Metacrawler) y pasarnos al buscador de Larry y Sergei. Aquí en The Smoke Sellers estamos un poco quemados con el hecho haber bajado de Page Rank y hemos estado intentando hincarle el diente estos días. En este post vamos a explicar el algoritmo hasta el final intentando emplear la cantidad mínima de matemáticas posibles.
(*) goran opina que otra de las principales ventajas competitivas de Google fue llenar una piscina olimpica de sangre de niños no bautizados y ofrecer su buscador a Satan.
Si alguna vez te has interesado por el tema, habras leido que:
1. La "importancia" de una página web sólo depende de las paginas web que la enlazan.
Si tienes una página web y esta es enlazada desde páginas importantes (de alto Page Rank, pongamos www.microsiervos.com) tú recibiras una parte de esa importancia. Todas las páginas que enlaces desde tu página web (ese blog de tu colega con solo dos posts, por ejemplo) recibiran, a su vez, una parte de la importancia de TU página. Para ser más exactos:
2. Una página web reparte por igual su importancia entre todas las páginas a las que enlaza.
Es decir: Si te enlaza una página importante que enlaza 3 o 4 páginas a parte de la tuya es mucho mejor que si te enlaza una página igual de importante que enlace 30 o 40 (toca más Page Rank a repartir).
Tambien habras oido hablar de los Spiders (arañas). Esto no son más que veloces programas automáticos que van recorriendo internet como si fuesen un usuario humano, pulsando todos los enlaces posibles, extendiendose así por la "red" (de ahi el nombre) y creando un mapa de la misma. Asi que tenemos:
3. Los Spiders proporcionan a Google un mapa de la red donde se puede ver qué página apunta a que página
Esto no significa que sepamos ya el Page Rank. De hecho, todo esto es muy bonito pero… como leches calculamos el Page Rank?. Por qué página empezamos?. Suponiendo que empezasemos por una, si no tenemos el Page Rank de las que enlazan a esta, como podemos calcular algo?. Y lo que es peor: En internet hay venticincomil millones de páginas apuntandose unas a otras (número subiendo rápidamente), cómo crear un algoritmo que sea capaz de lidiar con semejante brutalidad de enlaces. En el peor caso todas las páginas se apuntan entre si y el numero total de enlaces es de venticincomil millones, al cuadrado!!.
Aqui es donde realmente llega la artilleria matemática. Prometemos que si sabes lo que es una matriz, como se suman y como se multiplican (y tienes un poco de fe) ya puedes entender el algoritmo de Larry y Sergei hasta el final.
La Matriz de reparto de Page Rank H
Vale, no sabemos cual es el page Rank de ninguna página antes de empezar, pero si hay una cosa que sabemos: Cuanto de su desconocido Page Rank reparte una página entre las páginas que enlaza. Por lo dicho en (2), si una página enlaza 5 páginas transmitira un 1/5 de su Page Rank a cada una. Debido a (3) el número de páginas que enlaza cada página lo sabemos. Es más, podemos construir una tabla H de veinticinco mil millones de filas por veinticinco mil millones columnas (no, no cabe en un A4), que contenga todos los enlaces posibles. Para dos páginas cualesquiera (una como enlazadora y la otra como enlazada) tenemos un recuadro de la tabla que nos indica que proporción del Page Rank transfiere la enlazadora a la enlazada. Para orientarnos un poco: La diagonal de esta tabla representaría lo que la página se transmite a si misma (si se enlazase). Cualquier recuadro por debajo de la diagonal y su simetrico por encima de la diagonal indican respectivamente lo que se transmiten dos páginas cuando una actua como enlazadora y la otra como enlazada y viceversa. Si una página no enlaza a otra, se pone un 0 en el recuadro (lógicamente no le puede transmitir nada de Page Rank).
Matriz (Vector) Invariante I
Lo que viene a continuación no es idea de Larry Page o Sergei Brin, hace un siglo que se conoce, pero si que requiere la poca de fe que te pedimos reservar. Esta tabla (lease Matriz), que hemos creado con la ayuda de la información proporcionada por los Spiders, representa en realidad la dificultad (o facilidad) para el "flujo" de Page Rank de una página a otra. Podemos ver el flujo como agua que pasa con menor o mayor dificultad de una página a otra de acuerdo al valor correspondiente al recuadro de la tabla H. Este agua/transferencia de Page Rank fluiría de una página a otra a traves de sus enlaces sin cesar y eventualmente podría llegar a un equilibrio (si no llegase no habria Page Rank alguno). Pues bien las matemáticas, concretamente el teorema de Ruelle-Perron–Frobenius (ingles) nos garantiza lo siguiente:
4. Bajo determinadas condiciones, que veremos, se acabará alcanzando ese equilibrio. No es que Frobenius (ingles) supiese lo que es una página web en 1900, si no que el problema es matemáticamente idéntico a un conocido problema de dinámica de sistemas (ingles). Luego, hay gente que dice que Larry y Sergei son licenciados en filosofía.
5. El equilibrio queda representado por el vector invariante I. Esto es: Una tabla de una sola columna (una matriz, más concretamente vector) de venticincomil millones de valores, que cumple que al multiplicarla por la matriz de reparto H nos da otra vez ella misma (I). Lo que expresaríamos:
Este vector invariante I de venticincomil millones de valores, que casualidad, uno para cada página web, es el Page Rank. Faltará refinarlo, escalandolo de 1 a 10, y discretizarlo para que no de valores intermedios. Intuyo que el valor discretizado (1 a 10 sin decimales), que se muestra en la google toolbar, es solo de cara al publico e internamente emplearan los decimales que salgan también.
Sí, muy guay pero y lo de las 25.000.000.000 páginas?
Cierto, cierto. La gente que haya sufrido algebra de primero habra reconocido a I como un vector propio de valor propio 1 de la matriz H. Y seguramente recordará con horror que para calcularlo hay que resolver un polinomio que en este caso tendría grado 25.000.000.000. Vamos no lo calculamos asi ni de blas. Afortunadamente, sobre todo para las personas a las que lo anterior les ha sonado a chino, existe un método para calcular I iterativamente (en pasos sucesivos) y muy muy sencillo. Tan sencillo que consiste en que nos inventamos una tabla de 25.000.000.000 valores del Page Rank a voleo (un vector I0 creado aleatoriamente), lo multiplicamos por H y el resultado será otra tabla de 25.000.000.000 valores I1 pero más cercanos al valor correcto del vector invariante I. Repítase esto un monton de veces hasta que el resultado de multiplicar por H ya no produzca nigun cambio y ya está. Ya tenemos el vector invariante. Este algoritmo, que se llama el método de las potencias (ingles), se expresaría matemáticamente asi:
Donde k no es más de que el índice que indica cuantas veces hemos multiplicado por la matriz H. El primer vector, que creariamos a boleo sería k = 0, el segundo, procedente de mutiplicar por H sería k =1, etc. Para expresar de forma general que cada término se obtiene mediante una transformacion del anterior se emplean los índices k+1 y k. Hay que tener en cuenta que los métodos iterativos tienen la ventaja de que no necesitamos acumular demasiados valores, lo cual reduce la cantidad de memoria que necesitamos para computar el Page Rank y acelera todo el proceso de cálculo. Siguen siendo una burrada de números pero al menos es factible.
Gran problema
Que facil, no?. Obviamente falla algo y ese algo es el punto (4). Resulta que no se cumplen las condiciones de convergencia del teorema Ruelle-Perron–Frobenius. Es decir que aplicando el método arriba explicado no hay garantía de que lleguemos al vector invariante. No entraré en detalles, no hace falta. Utilizando la analogía del "flujo" de Page Rank se puede entender perfectamente que es lo que falla y como se puede solucionar.
Página Sumidero:
Qué ocurre cuando el flujo de Page Rank llega a una página como la 2 que no tiene enlaces a nigún sitio?. Pues simplemente que no sale de ahi. Esa página se vuelve un sumidero de Page Rank y el algoritmo dará resultados incorrectos. Como lo resolvemos?. Si hacemos la página 2 enlace todas las páginas de la web por igual (imagina millones de pequeñas flechas saliendo de 2 hacia todas lás páginas), esto dará salida al flujo de Page Rank pero la influencia en los resultados es minima, puesto que cada página recibe solo 1/25.000.000.000 del Page Rank de 2. Matemáticamente, esto equivale a sumarle a H una matriz A que tenga todo 0s menos en las columnas de las páginas sumidero que tendrán toda la columna llena de 1/25.000.000.000. De esta forma en vez de la matriz H emplearíamos la matriz S=H+A en el método de las potencias.
Red-Sumidero:
Un caso similar es el de las sub-redes de páginas dentro de la red, como la 5-7-6-8, que no tienen enlaces de vuelta. Estas redes se convierten en redes-sumidero. El problema es que estas páginas sí enlazan otras páginas y no podemos simplemente cargarnos esa información y enlazar todas las páginas de la red desde ellas. Para dar salida al flujo de Page Rank, vamos a recurrir a una solución al más puro estilo "ingeniero".
Gran solución
Necesitamos garantizar la salida del flujo de Page Rank de cualquier página o sub-red, es decir, que toda página apunte a otra página. No nos vale con crear un enlace a cualquier página a boleo porque (a parte de estar falseando el Page Rank), si resulta en una red cerrada como 5-7-6-8 no hemos solucionado nada. Ahora, imaginemos un caso ideal en donde todas las páginas apuntasen a todas las páginas. Ahi el Page Rank siempre tendría algún enlace por donde escapar, incluso de las sub-redes, y el algoritmo funcionaría. Pero claro, se perdería toda la jerarquia que dan los enlaces, la matriz de reparto tendría todos sus elementos iguales a 1/25.000.000.000 y todas las páginas tendrían el mismo Page Rank.
Pues nada, sumo la matriz de reparto real, calculada con la información de los Spiders con la ideal en la que todas las páginas se apuntan entre si y lo divido por dos. La matriz resultante tendrá siempre enlaces saliedo de cada página y tenemos el flujo de Page Rank garantizado. Que al mezclar a partes iguales la matriz real y la ideal me salen los resultados demasiado aleatorios? (por inlfuencia de la ideal). Bueno, pues en vez de mitad y mitad las mezclo con 85% de la matriz real y un 15% de la ideal y pista. Y ya esta señores. Con ustedes la famosa matriz de Google:
Donde recordemos que S=H+A es la matriz real con el problema de los sumideros individuales resuelto, 1/n×1, con n = 25.000.000.000 es la matriz ideal y α = 0.85 nos da la citada mezcla al 85%. Algún lector avispado puede decir: Pero… el meter ahi un 15% de aleatoriedad, no falsea de alguna manera el Page Rank?… Bienvenido al mundo de la ingeniería chaval!.
Para terminar si empleamos G en vez de H en el método de las potencias y jugamos un poco con los términos obtenemos la formula que aparecía al principio del post. Empleando la fórmula a la derecha del igual obtendremos cada nuevo vector Ik+1 en cada iteración.
Anotaciones finales
Este artículo esta confeccionado a partir de esta maravillosa página (ingles) (de la que también tomé "prestadas" las imágenes) y la imprescindible ayuda de la Wikipedia. En la página tambien hay enlaces a los pdf originales de Larry y Sergei asi como a algún libro sobre el tema. Si alguien se toma la molestia de echarle un vistazo, ahi van algunas aclaraciones:
- El valor óptimo del parámetro α se determina experimentalemente y regula también la velocidad de convergencia del metodo de las potencias, a mayor porcentaje de matriz real, menor velocidad de convergencia. Google dice que con basta con k=50-100 iteraciones para calcular el Page Rank, cosa que tarda varios días. Imagino que trabajando con varios ordenadores en paralelo. Esto se conoce como Google Dance y en TSS no nos hace ni puta gracia.
- Matemáticamente, la condición de convergencia del algoritmo empleado por Google es que todos los elementos de la matriz de reparto de Page Rank sean estictamente mayores que 0, cosa que cumple la chapucilla que acabamos de ver. Esto no es una condición de convergencia del metodo de las potencias si no una condición para la existencia del vector invariante según el teorema de Ruelle-Perron–Frobenius.
Mmm, no creo que sea muy elegante eso de fijar el PageRank, no obstante sospecho que lo deben de tener bastante parcheao. Lo que esta claro es que depues de la ordenacion por PageRank hay un podado posterior de los resultados. En su día era eso del LocalRank que estuve a punto de postear. A estas alturas no se muy bien lo que haran. Luego esta por supuesto que tanto coincida el contenido de tu página con los parámetros de búsqueda introducidos, esto es un factor muy determinante a la hora de salir arriba en las búsquedas (como apunta por ahi arriba @Demetzell, que se dedica a ese negocio).
Esto del pagerank es una loteria, y nadie sabe la formula como la cocacola o de lo contrario que me lo expliquen.
es enredad igual la formula…
ojala que le suba el page rank luego a mi pagina
pq es como un efecto domino…
para los que la quieran conocer esta es
http://www.venuzcomplex.blogspot.com/
saludos!
Quiero hacer mas popular mi pagina cobroar por visitas pero que sea una una pagina seria y sin publicidades esto puede ser
valen verga
Muy Bueno!
Lo puse en mi blog… ;-)
Saludos!
excelente articulo, la verdad es que muy pocos mortales tenemos idea de la complicidad de la pagina, que es de las mas faciles de usar, es por eso su gran nivel de aceptación y constante uso por todos las que navegamos en la red.
ellos hacen todo lo dificil, para dejarnos a nosotros lo mas facil y asi, se hacen millonarios.
Compran nuestra pereza, y nosotros pagamos para ser mas perezosos… esa es la calve del exito.
felicidades.
Que nada, que gracias por la explicación.
Me has aclarado muchas cosas, pero creo que google maneja de alguna manera a su antojo el PR , mas alla de cualquier algoritmo
me parece que google da el page rank deacuerdo a la cantidad de enlaces hacia nuestra web, y el rankig de pagina notablemente sube tambien con la cantidad de enlaces hacia otras web.
para mi es como una calificacion de los buscadores a el esfuerzo, dedicacion y ingenio del webmasters, el cual sube y baja un poquito mas deacuerdo a la cantidad de enlaces salientes o entrantes, ojala alguna vez llegue a 8 con mi web, que es algo meramente imposible, pero si uno lo busca capaz lo encuentre…….
Lo hermoso de la matematicas, y lo importante de un algoritmo en realidadestas personas se lucieron
Pues no estaría mal que nos dieran tu opinión sobre lo que ha pasado en la última revisión del Page Rank donde hay un mosqueo generalizado en las web mas conocidas por la pérdida de 2 y 3 puntos en su PR
Pues en mi caso con un mes de existencia he pasado de o a 3 en PR en http://www.hipotecasypisos.com
Si, la verdad es que la gente anda un poco desesperada. No hay más que echar un vistazo a los foros de SEO. El asunto tiene que ver con la lucha contra los enlaces pagados y el intercambio fraudulento de enlaces. Google ya hace tiempo que tiene un monton de mecanismos implementados para luchar contra esto, la novedad es que ahora “parece” que ha preferido cortar por lo sano, llevandose por delante a unas cuantas páginas importantes. Digo “parece” porque dado el tamanio maisvo de la Web no creo que tengan facil el explorar los resultados de los Google Dance a priori e igual implementaban alguna version nueva y se les ha ido de las manos (y lo reparan lentamente). Confiemos en el gran hermano. Si no hicimos trampas el danio* no puede ser excesivo y si, aun así, lo es deberá ser revertible de alguna forma, pronto. Al fin y al cabo Google depende de ello.
*Siempre cabe preguntarse hasta que puento el Pagerank™ publicado incluye todas las penalizaciones y bonus que Google usa internamente. Podrían, por ejemplo, estar dandonos simplemente los resultados del algoritmo de ahi arriba sin postprocesar y técnicamente no estarian mintiendo. En ese caso hay que esperar y ver como se comporta el tráfico. Al fin y al cabo el Pagerank™ es solo una parte. La optimización por palabras debería seguir siendo una forma efectiva de whitehat SEO.
Antes de abandonar el Pagerank™ por cuestiones de trabajo vi un par de patentes interesantes. A ver cuando me pongo en serio y hago un nuevo post.
Muy bueno el post, estoy con papel y lapiz intentandolo digerir.
espero saber mas de los tipos de conexciones existentes pero el informe de google es muy parametrado y no da explicacion a muchos misterios de dominacion que ejerce en la mente de los seres humano por la adiccion a la misma esperando saber mas desearia algun interesado me envie cortezmente alguna informacion extra para que me preocupe un poco mass de las razones de tamaña expacion que ya parece no tener limites esto es evolucion caeran muchos solo los fuertes sobreviven que misterio
Coches usados, muchas cosas tienen su explicación , en este caso
solo Google sabe la formula actual.
impresionante artículo
soy de ciencias y me pierdo…jejej
quizas por eso no gano lo que serge and company
saludos
francisco-madrid
Esto es demasiado compliado lo del page rank hay alguna formula para subir rapido?
Voy a mejorar mis matematicas y vuelvo… :-)
Muy bueno tu artículo, pero lo que me parece medio sinietro es que si un website tiene mayor Pagerank debido a que los links que apuntan al sitio, no entiendo porque http://www.whitehouse.gov está entre los primeros lugares, porque no creo que haya tantos links hacia ellos. No es que sea envidioso, sólo que me gustaría ver mi website http://www.bananatools.com más arriba será esperar un poco. :-|
Buenisimo el articulo , lo mas gracioso de todo no es la propia formula de google si no el haber vendido la idea a los millones de usuarios , eso si que tiene merito , ya podemos inventar lo que quieras que si no lo vendes solo te sirve a ti.
Lo que quiero saber es: ¿Y falta mucho para que Google domine el mundo??
Porque los que lo dominan hoy por hoy me tienen los cocos inflados…
muy bueno! el teorema de Teorema Perron-Frobenius en español,por si os interesa:
Sea A una matriz (cuadrada) con entradas no negativas ,A 0. Si A es irreducible, entonces
(a) existe un autovalor (simple) λ> 0 tal que Av = λv, donde el autovector es v > 0. Además λ |µ|, para cualquier otro autovalor µ de A.
(b) Cualquier autovector w 0 es un múltiplo de v.
(c) Si hay k autovalores de módulo máximo, entonces son las soluciones de xk – λ k = 0.
Luego… ¡Victoria! -siempre y cuando el teorema quede demostrado, pero… ¿Sería entonces Teorema?- Se invita a los incrédulos, a leer la demostración aportada por Fabien en el último enlace de la Conclusión (pág 151). Para los más apasionados, cualquier libro que tenga en el título “Nonnegative matrices”. Aquí no se incluirá ninguna por problemas con la librería simbólica.
El teorema de Perron-Frobenius nos asegura que el autovector que buscábamos existe, y además es, en módulo, el mayor de todos los posibles de la matriz que modeliza a la red, sólo hay un pequeño problema, hace falta que la matriz que modelice nuestra red sea irreducible. Y ¿Qué significa Irreducible?
Hay varias maneras de entenderlo:
1. No existe ninguna permutación (de filas y columnas) que transforma A en una matriz del tipo
donde A11 y A22 son matrices cuadradas.
2. La matriz (I + A)ˆ n-1, donde I es la identidad n × n, tiene todas sus entradas positivas.
3. Si A es la matriz de adyacencia de un grafo, entonces el grafo está fuertemente conectado.
Necesitamos pues que la matriz M -o ¿Será M´?- Sea irreducible pues sino no podemos asegurarnos que nuestro (auto)vector x de los Page-Rank exista. Claramente de las tres posibles definiciones, la más apta para nuestro caso es la tercera pues en realidad estamos tratando con la matriz de adyacencia del grafo que modeliza la red. Veamos a ahora si es el caso.
Alquien me puede explicar esactamente ese sentido de esa ecuacion
que porqueria la matematica…………………………..
si solo de enfoca a una página web, acotando los limites y pensando en que no es un sumidero, existiría algún TRUCO para encauzar ese agua/equilibrio del page rank?, que tipo de relación entre webs propones como la mejor para disponer de todo un depósito de page rank en una web?
Thx. bYes.
humberto
buen post muy bien explicado y completo
…buen trabajo, mis felicitaciones.Hoy se conocen conceptos mas avanzados para el ranqueo de datos aleatorios que mezclan procesos matematicos de seleccion con sofware spider evolucionados, los entendidos sabran a que me refiero. Recuerden que el exito de Google no yase ni en su rapidez o su diseño…sus seguidores estan convencidos de que forman parte de una comunidad para la revolucion. Saludos cordiales.
concuerdo con ‘anonimo’, que porqueria la matematica!!!! pero que buen post :)
Muy interesante conocer esos métodos!
Hola;
Actualmente estudio la Maestria en Tecnolgía educativa, y para mi ha sido muy clara la explicación, aunque no entienda nada de los algoritmos y teoremas, fué muy precisa la informacion y pude analizar como es que las páginas que se crean en la web pueden obtener mejores posiciones y porque llegan a permanecer más tiempo en ese lugar.
Gracias. Saludos Mil
Que complicado hay gente para todo.
Muy buena aportación ahora, leeré el PDF de la página que recomiendas.. aunque te seré sincera no le entendí mucho..
Demaciado complejo para mi!!
Aun asi gran post,todo muy bien explicado y detallado.
Yo tengo un tutorial de Pagerank que explica cómo conseguir muchos enlaces entrantes sin ser baneado por el google.
El Magnate de Internet, un emprendedor contra la crisis
Excelente, super complicado pero excelente, esta informacion es importante para los que nos dedicamos al posicionamiento, pero no es entendible para el ser humano convencional (el que tiene dos patas y escribe con dos dedos), deberìas de poner el ejemplo con manzanitas … saludos desde Cancùn, MEXICO
Para mi entender es un poco lioso. Además el pagerank parece que solo tiene que ver con los enlaces… no?
Muy buena la info . en mi caso no puedo hacer que mi web suba de un page rank 2 .
saludos.
me he quedado pasmada con lo poco que sé de matrices
pues creo que no entiendo bien ese algoritmo complicado pero les dejo mi web para que suba en pagerank y espero que no me qiten este comentario pr spam ja ja
El otro día estuve viendo un documental “El mundo según google”. Y según ellos lo que importa solo son los enlaces y quien te los da. Dan más importancia a un enlace de Washintong Post que a una página personal…
Las visitas tienen más que ver con Alexa
hemm…. miren, la perfeccion de google no está en que hayan aplicado ese algoritmo matemático. El uso de ese algortimo es obvio, porque eran matematicos.
Solucionalo como ingeniero y te respondo lo siguiente.
El ranking de tu sitio o pagina, depende netamente del contenido lexico asociado a las búsquedas…¿cómo comprobarlo?
estudia las consultas que haces al motor y verás que es lo que tiene mayor relevancia
tu ejemplo: mayor cantidad de enlaces. La página que contiene mayor cantidad es el sitio k vendia 1 pixel para juntar el millon de dolares pero aun así, ingresas el nombre y no aparece ne los primeros rankings.
Lo que hace potente a google, es el lo que rescata de las paginas y el análisis semántico en cada sitio.
También lo que hizo hablar de google, fue también la manera en que comprimen la cantidad de sitios en su servidor transformando a archivos planos las paginas html.
No pensemos en que son gigantes, porque en los 90 no desde que nacio habian otros buscadores, porque el cambio a él?… por el manejo de la tecnología agilizando los servicios web.
Saludos
Muy buen post. Ahora les cuento a todos que yo soy un quality rater, o sea contratado por la empresa para perfeccionar el ranking de resultados. Esto es así porque los algoritmos de Google no dan una perfección exacta en los resultados, ya sea en base a los links que direccionan a el sitio web en cuestión o la coincidencia de palabras en ese sitio con respecto a la búsqueda. No soy matemático pero creo que todo este tema de las fórmulas y los algoritmos se reducen a estas coinciencias. Por favor ayudadme si me equivoco porque no entendí nada.
no sirve para nada hijos de su pinche madre hijos de la chispa