en Ciencia y Tecnología, InterNEX

Algoritmos de Google: El Page Rank

Method for node ranking in a linked database

absmiddle

(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: 

sumideroQué 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

Deja una respuesta a Ergodic Cancelar respuesta

Escribe un comentario

Comentario

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

95 Comentarios

  1. Ya podí­a… he he, pero bueno. Toda la información estaba disponible en internet (en Google para ser mas exactos).

    James P. Wack:

    De verdad que con entender que las matrices son formas de organizar grupos de numeros en forma de «tablas». Y que tienen sus propias reglas para sumarlas y multiplicarlas no necesitas nada más. La Wikipedia en español lo explica muy bien:

    http://es.wikipedia.org/wiki/Matriz_(matemáticas)

  2. Hombre… es cierto que no me gusta google… pero no creo que haya hecho pactos con el diablo… creo más en la fuerza del trabajo que en la intervención divina (wow… me ha salido una frase de galleta de la fortuna)

    Eso sí­… creo que el end game de google es dominar el mundo, por supuesto. Como primer paso, dominar internet… luego conocer los gustos y la vida de todo el mundo (sus correos, contactos, notas en la agenda, calendarios, documentos, etc.) así­ pueden crear mejores estrategias de control… y como resultado final el control total… un auténtico Matrix en la vida real.

    Un gran artí­culo… y si google te ofrece trabajo mucho cuidado… porque puede que acabes trabajando en una isla en medio de un océano que tiene un extraño monstruo

  3. Cierto, deberí­a haber puesto [dramatización de los hechos] en el asterisco. Yo también estoy de acuerdo en que Google aspira indexar los gustos (hasta los secretos) de todos los ciudadanos del mundo y venderselos al resto de las empresas tanto de publicidad como convencionales. La cantidad de pasta que hay en ese negocio es simplemente inimaginable.

  4. Me ha encantado tu artí­culo; muy bien explicado.

    Una consecuencia inquietante es que cuantos más enlaces te pongas a tu propia web (siempre que pongas enlaces algún enlace a otros y siempre que otros te enlacen) más pagerank te repartes a ti mismo, y más pagerank tendrás…

  5. He quedado impresionado. No he entendido absolutamente nada porque, sencillamente es imposible para mi dado, entre otros impedimentos, que no he pasado del antiguo bachiller de seis cursos. Pero he podido leerlo (me tiran «las letras») y eso es de aplaudir.
    Como demostración del interés que me ha causado, te haré una corrección que no por nimia deja de ser jugosa: En el párrafo intitulado «Gran Solución» usas la expresión «a boleo» queriendo decir «a voleo». Esta locución viene de cuando se sembraba el grano a mano, esparciéndolo a puñados. Sin embargo, aquélla, tiene más que ver con lanzar pelotas o bolas.
    Muchas gracias por tu esfuerzo.

  6. Cierto, cierto Nial. Nunca se me ha dado la forma en el lenguaje escrito ni en el matemático. Siempre me ha ido más el fondo. No obstante la forma es vital, especialmente en matemáticas donde el lenguaje no es redundante. Disculparas que no corrija el error porque eso generarí­a otra entrada en los feeds.

    A todos los agradecidos, muchas gracias, me alegra el haber aportado algo interesante.

    espectacles, me conoces? como sabes que cuando bebo unas copas de más, me da por explicar algoritmos?.

  7. Y yo que estoy haciendo los cursillos de ingreso a Licenciatura en Ciencias de la Computación.. y me preguntaba por que la carrera tenia mas matematica que informatica… copado, esto me alcanzo como respuesta =)

  8. Muy completo el artí­culo… demasiadas veces no se tiene en cuenta no ya el esfuerzo de cálculo realizado, sino la potencia y capacidad de los servidores de google para hacer que ésto funcione…

  9. Cierto Enrique. Yo además destacarí­a la implementación óptima de los algoritmos de forma que la tarea se pueda repartir entre baratos ordenadores convencionales. Esa es otra de las grandes ventajas competitivas de Google. Su escalabilidad.

  10. Muy bien hecho, y explicado el articulo…

    La verdad es que me ha hecho mucha ilusion esto de saver como rula en el fondo el google.

    Suerte!

  11. Yo es que soy de letras, ¿no hay una explicación filosófica al page rank?. Es que por muchas vueltas que le doy no consigo entender como un flujo de electrones a través de un cable o un material metálico puede saber lo que estoy buscando en Internet. Gracias por tu explicación, pero no me la creo en absoluto, mas bien me creo lo de la intervención no mesiánica.

  12. ¡Plas! ¡Plas! ¡Plas! Magní­fica explicación, nunca entendí­ por qué diablos tení­a que haber un Google Dance.

    Creo que gracias a ti hemos comprendido todos como funciona, en su base, el PageRank.

    Saludos!

  13. @Ergodic: ok, si se lo que es una matriz, como se suman, multiplican, etc. Lo que no domino es teorí­a de transformaciones lineales (esa chorrada de los kernels) y lo que nunca dominaré es toda la teorí­a de tensores (estudio electrónica, no mecanica ni nada similar)

  14. Wow! me gustó mucho :), sospechaba que funcionaba de esa forma, pero pensaba que para manejar tal cantidad de «agua» utilizaba ecuaciones diferenciales, que sexy ecuación y algoritmo 🙂

  15. El page Rank valora la popularidad. No la importancia de un site y no tiene nada que ver con salir antes o no por un resultado. Ten en cuenta que la optmización es a nivel de palabra, no genérica, por lo que un page rank elevado no implica nada

  16. @James P. Wack

    En realidad entender completamente el transfondo matemático del asunto esta solo reservado a los de ciencias puras. Como ingeniero uno se para en un nivel en el que ya puede sacar partido de la analogí­a entre un problema matemático y un problema de la realidad (los que nos pagan por resolver). Fí­jate que incluso la solución que plantean los de Google al problema no es de gran profundidad teórica.

    Si te soy sincero, yo tampoco entiendo completamente porqué el vector propio de mayor valor propio de la matriz de transferencia de energí­a de un determinado sistema dinámico representa su equilibrio termodinámico. Eso si, se lo que representan los valores y vectores propios propios (sin comparacion, el algebra más util que puedes aprender en primero de carrera). También sé lo que es el equilibrio termodinámico (y mira que siempre lo pongo como ejemplo de cosas inútiles que aprendi en la carrera). Gracias a eso entiendo tanto la analogí­a con la web como la solución que plantean.

    @Demetzell

    Obviamente la búsqueda se limita a un conjunto de páginas que muestran relacción con las palabras clave que tú buscas. Qué tan «bien» encaje el contenido de la página con tus palabras clave es también un criterio para ordenar los resultados (otro algoritmo interesante). Cómo Google pondera exactamente la «importancia» de la página frente al «keyword match» no lo sé. Si que sé que en un principio el Page Rank tení­a más importancia que ahora porque al haber tanta pasta metida hay que hacer un monton de parches para despistar a las empresas. Tú sostienes que el Page Rank ya no se considera en absoluto. Me dejas de piedra. No obstante, me parece dificil de creer porque:

    1. Google estarí­a mintiendo. (bueno esta la podemos quitar 😉 )

    2. Páginas como Digg con tal variabilidad de Keywords no saldrí­an en absoluto. Se necesita algún criterio orientativo basado en el flujo teórico de visitantes (que es lo que es al fin y al cabo el Page Rank).

    3. Si yo fuese Google, preferiria dedicar mi esfuerzo a detectar links sospechos, hacer listas negras y yo que sé, incluso dejarí­a informacion falsa aparcada por la red (eso no es mentir ;)) con tal de no renunciar a un principio tan universal.

    He echado un vistazo a tu blog y me ha dejado más impresionado aún. Sobre todo la página «holy grail of pagerank» que enlazaban en tus comentarios (No pongo el enlace por si está en una lista negra de Google). Pareces vivir en un mundo muy curioso (lo digo sin faltar, eh?, me has dejado flipando). Si tienes una explicación técnica o información de primera mano al respecto de tu afirmación anterior te aseguro que, a mi por lo menos, me interesa mucho.

  17. Seguramente por ahi van los tiros del algoritmo base, pero faltan muchas cosas que solamente ellos saben.

    Lo que explica este post que no se actualize el pagerank cada dia. Requiere una enorme potencia de calculo, por eso lo realizan cada X tiempo.

  18. Hola, he trabajado en buscadores de Internet y tengo cierto conocimiento sobre algoritmos de búsqueda y ranking de resultados.
    Es sobradamente conocida la potencia de google en cuanto a la búsqueda y obtención de resultados, puede que el algoritmo anteriormente explicado sea ingenioso y sorprendente, pero la red es tan compleja que este algoritmo no nos asegura encontrar los resultados que búscamos.
    Un buscador bueno, para mi es aquel que es capaz de devolverme lo que estoy buscando de la manera más rápida y fácil posible, no he dicho nada que todo el mundo sepa ya; y es evidente que una página con muchas visitas y enlaces a/desde otras páginas se puede situar en el primer lugar, pero muchas veces movidas por intereses comerciales, los cuales otorgan a este tipo de algoritmos cierto margen de incertidumbre sobre los resultados. Todo el mundo que trabaja sobre la red sabe sobradamente que contra mas invierta en publicidad, mas visitas y mejor funcionará su página, ¿por esto tiene que ser la mejor o la más buscada?
    Hoy en dí­a, muchos buscadores son capazes de devolvernos unos resultados que para nuestra búsqueda pueden resultar mas acertados que los de google, les invito a comparar los distintos buscadores como sin encerrarnos en Google.
    No es por criticar a Google, ni siquiera he mencionado (o ahora sí­) lo que dicen las malas o las buenas lenguas sobre que se puedan favorecer determinados resultados según el dinero que se invierta en publicidad en Google.

    Saludos cordiales a todos los red-lectores.

  19. @manu_drac

    En realidad lo mejor de este método es la cantidad de datos que puede manejar en un tiempo razonable. Lo que me pregunto es como lo harán los competidores.

  20. Por fin !!!

    Ahora entiendo para que coño estudié el maldito teorema de Ruelle-Perron–Frobenius en la Facultad de Ingeniera !!!!

    Pero si mis profes eran profetas !!!!
    Sabian que estos dos enfermitos 15 años después lo iban a utilizar en internet 🙂

    Muy buen trabajo, te felicito.

    Kilme

  21. Me encanta que me expliquen cosas que no entiendo en absoluto. voy a imprimirme al señor frobenius a ver si a la de tres me entero. 🙂
    si algún dí­a te enteras de cómo funciona el algoritmo que rige la lista «interesting» de Flickr avisas, vale?

  22. Me pongo a ello @A, si encuentro algo al respecto lo postearé. Os recuerdo que en la página principal tenemos el link Colabora/Contacto y estamos encantados de oir sugerencias.

  23. acabo de descubrir la página de contacto. Esto de la navegación lineal es lo que tiene. De todas formas me falla la ironí­a en las cajas de comentarios. Ese algoritmo no es público. Claro que mi conocimiento sobre los algoritmos se basa en este artí­culo el de frobenius de la wikipedia y en los chistes de xkdc :S
    mmm Oye, ¿Te vas a comer ese Post it?

  24. Vaaaalla, no albergaba la esperenza de poder explicar el algoritmo exacto pero ya me habí­a puesto manos a la obra.

    De momento ya sé que el 70% del codigo del algoritmo ese es para evitar que salga porno. Dicho por un administrador de Flickr eso suena a que tiene mucho parche y que el sistema de puntuación «positiva» es relativamente sencillo.

    De momento parece tener al menos una relacción limitada con la inclusion en los grupos. Si yo fuese un duende de flickr intentarí­a hacer algo como el Page Rank pero más web 2.0. Flickr es un entorno infinitamente más pequenio y controlable que la WWW, donde tienes toneladas de datos bien conocidos. Puedes empezar por contar las visitas, los enlaces, los comentarios y dar una importancia ponderada segun el nivel de envolvimiento en flickr que tiene el usuario que las realiza… yo que sé… se pueden hacer un monton de cosas… Si encuentro algo interesante descuida que lo posteo.

  25. que buen rollo, 🙂 La verdad es que no soy un Pichichi, tres veces en mi vida he jugado en campo grande, pero me encanta jugar. Y me pirro por las cervezas. Me paso un dí­a a charlar por el campo a partir de abril. Me toca estar de viaje tres semanas fuera de Berlí­n.
    te dejo mi correo en flickr ergodic.
    Long life XXI Century

  26. Me gustarí­a que me explicaran didáctica y prácticamente con un ejemplo el ¿cómo se aplica la fórmula de Page Rank u otra aplicable como algoritmos, en el sistema de loto para hallar los próximos 5 de 35 ó 6 de 45 a salir en la próxima balotada, teniendo el historial de los 5 últimos resultados?
    Escribir a: dagagore51@yahoo.com
    Saludos y felicitaciones por el análisis y la exposición

  27. Ergodic:

    tengu todavia una duda… google busca el criterio de busqueda que solicitas solo en las paginas que tiene indexadas??? es decir, si yo subo a la red una pagina con mis tareas de la universidad y en cada una de ellas firmo con mi nombre, y despues realizo una busqueda en google de mi nombre… google encontraria mi nombre en dicho sitio web nuevo?

    preguntado de otra forma… como hago para que google encuentre un criterio determinado mediante el uso de comillas?? no quiero que encuentre una pagina determinada sino un nombre determinado en la red, que obviamente ahorita no encuentra.

    Te agradecere tus comentarios yava_mex@yahoo.com

  28. Muy chulo, pero yo habí­a leí­do que algunas páginas tení­an asignado un 10 de PageRank por definición, vamos, porque a Google le daba la gana. ¿Cuáles son estas páginas? Pues google.com -por supuesto-, w3c.org -porque no puede ser de otra forma-, http://www.adobe.com -por ser los propietarios del Acrobat Reader y del Plugin de Flash-, microsoft.com -por ser los propietarios del navegador más usado del mundo-, etc.

    ¿Es esto cierto?

    ¡Gracias y saludos!

  29. 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).

  30. 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.

  31. 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…….

  32. 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

  33. 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.

  34. 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

  35. 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. 😐

  36. 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.

  37. 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.

  38. 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

  39. …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.

  40. 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

  41. 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

  42. 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

  43. 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

  44. 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

  45. 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.

Webmenciones

  • BIM en Google | ATANGA enero 27, 2010

    […] Ya es habitual buscar en Google la solución a todas nuestras dudas. Y de ello se pueden establecer algunas conclusiones que reflejen el interés de una mayorí­a sobre algunos temas. Las búsquedas en este robot se organizan según su propia metodologí­a y está de sobra documentada  y justificada. […]

  • La historia de Google en 4 pasos del diseño | Región Creactiva enero 27, 2010

    […] http://www.thesmokesellers.com/?p=819 […]

  • Tiempos de barbarie « GT-Itc enero 27, 2010

    […] entre ambas cuestiones. El Page Rank de Google es un algoritmo matemático de gran complejidad (aquí­ hay un artí­culo sobre el mismo, del cual apenas entendí­ los primeros párrafos), pero la idea principal es simple: la importancia […]

  • Cambio en el algoritmo de Google « Blog Sistemas de Información enero 27, 2010

    […] El Page Rank: http://www.thesmokesellers.com/?p=819 […]

  • Internet de Nueva Generación » Blog Archive » PageRank: Una aproximación enero 27, 2010

    […] Y echando unas cuentas podemos hacernos una idea y comprender la maravilla de este sistema. En The Smoke Sellers lo han hecho por nosotros, o mejor dicho, han entendido primero y traducido después, una aproximación del […]

  • zibo » Acerca del Page Rank enero 27, 2010

    […] Google, y a grandes rasgos, la lógica de búsqueda —el “Pagerank”— funciona a partir de un algoritmo matemático que le otorga mayores puntos a las páginas más importantes; es decir, aquellas que han sido más […]

  • Tiempos de barbarie « El gato y el felpudo enero 27, 2010

    […] entre ambas cuestiones. El Page Rank de Google es un algoritmo matemático de gran complejidad (aquí­ hay un artí­culo sobre el mismo, del cual apenas entendí­ los primeros párrafos), pero la idea principal es simple: la importancia […]

  • Aplicaciones Asesinas » Blog Archive » El nuevo modelo wiki de buscador enero 27, 2010

    […] Google, y a grandes rasgos, la lógica de búsqueda —el “Pagerank”— funciona a partir de un algoritmo matemático que le otorga mayores puntos a las páginas más importantes; es decir, aquellas que han sido más […]

  • el blog del morsa » Jóvenes y exclusión digital enero 27, 2010

    […] necesaria) sobre la calidad de información, que la información se modele al usuario (gracias al famoso y oscuro algoritmo de Google, la realidad): un buscador cuyos resultados son modelados (en parte) por el/los propio(s) […]

  • Google - PageRankâ„¢ « qbitácora enero 27, 2010

    […] The Smoke Sellers > Algoritmos de Google: El Page Rank […]

  • Crí²nica de la conferí¨ncia de Google a la UPC « Programari lliure, una opció lliure? enero 27, 2010

    […] entre el postor que pagui més i la relació que hi hagi amb el que l’usuari cerca (el famós PageRank). També han citat que la seva interfí­cie simple amb anuncis a la part superior i a la dreta és […]

  • michaelmuller.net | Diseño y Desarrollo Web enero 27, 2010

    Google Page Rank al detalle!…

    Este excelente artículo de Smashingmagazine expone un detallado análisis de qué es y cómo funciona el tan conocido PageRank de Google.
    "Everybody is using it, but (almost) nobody really knows how it works. Google PageR…

  • elTecnoBlog » Blog Archive » El algoritmo pagerank de google enero 27, 2010

    […] Pagerank (The Smoke Sellers) […]

  • Como funciona… Un motor de búsqueda at Pisito en Madrid enero 27, 2010

    […] Por supuesto el PageRank es muy complejo, depende de muchí­simas más variables pero como descripción general para que se entienda está bien. Para los interesados pueden echarle un vistazo a este artí­culo que explica el PageRank según su fórmula. […]

  • Blogs Conexion Central » Por qué Google es tan famoso e importante? enero 27, 2010

    […] Todo se basa en la creación de un algoritmo matemático de parte de sus creadores Larry Page y Sergey Brin que permite determinar que tan importante o tan poco importante es un sitio web en Internet, basado en los enlaces externos desde otros sitios… es algo sencillo no ?, bueno pues a quien quiera conocer a profundidad este millonario algoritmo le dejo aca el enlace: http://www.thesmokesellers.com/?p=819 […]

  • linfati.cl » Blog Archive » De saloon y aleatoriedad vs Ingenieria enero 27, 2010

    […] Ergodi (TheSmokeSellers) en Algoritmos de Google: El Page Rank […]

  • Blumex » El top 25 de las páginas con mayor PageRank enero 27, 2010

    […] tiempo en The Smoke Sellers hacian un estudio, bastante interesante, del funcionamiento del Pagerank de Google (Obligada […]

  • El Blog de Fernando Chimeno » Archivo del Blog » Así­ funcionan las tripas de Google enero 27, 2010

    […] descripción de The Smoke Sellers del funcionamiento de PageRank, la tecnologí­a que permite que Google ordene los resultados de las búsquedas de tal forma que se […]

  • RuidoDigital » ¿Cómo se calcula el PageRank? enero 27, 2010

    […] solucionar eso, tenemos la gran explicación de The Smoke Sellers sobre cómo utilizando un poco de matemática y mucha capacidad computacional (de la que Google […]

  • Monopolio Podcast .... el podcast más demandado enero 27, 2010

    […] Algoritmo de Google […]

  • HispaLibertas » 300 millones enero 27, 2010

    […] Aquí­, en el terreno patrio, sigue destacando el empeño de nuestros emprendedores de las TI en hacernos ver las virtudes del Networking. No paran de organizar eventos, interesantí­simos por el contenido y por los ponentes. La noche del congreso es el último, y se intuye que estará dedicado, entre otras cosas, cómo no, al posicionamiento en buscadores, el pagerank, el spam, el marketing viral y otros temas de rabiosa actualidad internetera. Puede que un dí­a, a base de persistencia, estos soñadores hispanos y empresarios maltratados logren atraer la atención mediática que merece su esfuerzo, y con ello el reconocimiento por parte de los estamentos polí­ticos que llevan años mirando hacia otro lado, pero apoyando, curiosamente, la parcela que les interesa: la piraterí­a , la de verdad. […]

  • Ando muy ocupado at Michoacano.Com.Mx enero 27, 2010

    […] SmokeSellers publica una traducción sobre algoritmo matemático del pagerank de google. […]

  • Mi Brain-Training Personal» Blog Archive » Funcionamiento del PageRank de Google enero 27, 2010

    […] En esta web hay un documento muy interesante en el que se explica (en castellano) el complejo funcinamiento del algoritmo PageRank, utilizado por Google para clasificar la importancia de las webs. Hay que tene conocimientos del algebra de matrices para entenderlo, pero es muy interesante. Concretamente, este es elgoritmo: […]

  • Noticias rápidas at Pisito en Madrid enero 27, 2010

    […] Ví­a The Smoke Sellers encuentro una impresionante y extensa explicación de cómo funciona, matemáticamente hablando, el PageRank de Google. Plantea la fórmula principal y poco a poco la va desglosando y explicando cada término… […]

  • Algoritme del PageRank del Google at Arnau enero 27, 2010

    […] En aquesta pí gina hi ha un article molt interessant on s’explica d’una manera molt entenedora el PageRank. […]

  • Blogueando.com — Cómo funciona el Page Rank de Google enero 27, 2010

    […] Pues ahora podrás encontrar toda la explicación del algoritmo del Page Rank en español, perfectamente desglosado en su fórmula matemática (gracias a The Smoke Sellers -ví­a Microsiervos-), representada en la imagen siguiente: […]

  • TechTear :: T_T » Cómo funciona el PageRank de Google enero 27, 2010

    […] Ví­a The Smoke Sellers encuentro una impresionante y extensa explicación de cómo funciona, matemáticamente hablando, el PageRank de Google. En el post muestra la fórmula principal que determina el resultado del PageRank y poco a poco la va desglosando y explicando cada término. No es complicado seguirlo aunque en ocasiones se requiere de unos conocimientos matemáticos un poco más avanzados. […]

  • kbglob - tecnologia para geeks, no para tu mamá » Pagerank en fórmula matemática enero 27, 2010

    […] En microsiervos comentan un sitio que explica la fórmula del pagerank basándose en lo que se dice la patente, lo que hay en la web y lo que ha trascendido desde Google. Bastante interesante lnteresante lectura para un sábado a la tarde… […]