La historia oculta detrás del algoritmo PageRank de Google (o Keller, Keener, Page, Brin y Kleinberg)

¿Quién inventó el algoritmo PageRank que utiliza Google? El algoritmo está patentado por los fundadores de Google, Larry Page y Sergey Brin, cuando eran alumnos de doctorado en la Universidad de Stanford. Page fue alumno de doctorado de Terry Winograd, quien parece que le animó en la idea de trabajar en el PageRank, y Brin fue alumno de doctorado de Jeffrey D. Ullman, el famoso autor del libro de compiladores con Aho, aunque pronto se unió a Page para trabajar en temas “más interesantes” que los que le ofrecía su director (que le llevaron a hacerse multimillonario). Todo el mundo “sabe” que Larry Page inventó el PageRank, por eso se llama “Page Rank”. Eso lo sabe todo el mundo, ¿o no?

Acaba de publicarse el artículo del gran matemático aplicado Joseph B. Keller de la Universidad de Stanford, “Evaluation of Authors and Journals,” ArXiv preprint, 5 October 2008 , documento fechado originalmente en octubre de 1985, en el que aparece “calcado” el algoritmo PageRank de Google. En dicho artículo, que recomiendo, Keller “afirma” que lo inventó para clasificar equipos de béisbol (yo siempre lo leo como los cubanos: “beisból”). Un amigo y lector de este blog, JL, me pregunta “¿Sabes algo de esta historia? ¿Es conocida por los que estáis en el mundillo?” Me ha picado la curiosidad, lo confieso. No sé si Page y/o Brin conocieron a Keller, probablemente no. ¿Qué más puedo decir?

Ante todo, empecemos por el principio. Joseph B. Keller es un matemático famosísimo como inventor de la teoría de trazado de rayos difractivos (yo lo conocí hace años por eso). Sí, los rayos de la óptica geométrica (sin difracción ni interferencia) se pueden usar (convenientemente adaptados) para modelar la difracción. Esto es lo que se debería usar cuando se usa trazado de rayos en acústica arquitectónica, aunque muchos que la usan no los conocen. Su artículo “Geometrical theory of Diffraction,” Journal of the Optical Society of America, 52:116-130, 1962, es todo un clásico (citado más de 1000 veces en el ISI Web of Science). Pero Keller ha hecho muchas otras cosas importantes y conocidas, como sus trabajos sobre condiciones de contorno absorbentes con Givoli o sus modelos de la propagación de pulsos eléctricos en los axones de las neuronas. Es uno de los grandes matemáticos de la segunda mitad del s.XX en propagación de ondas y en el uso de métodos asintóticos en dicho contexto.

¿Alguna mención al trabajo de Keller sobre el PageRank antes de que Larry Page lo inventara? He encontrado el artículo “Who’s really #1?,” publicado en Science News, Dec 18, 1993, por Ivars Peterson (famoso escritor de noticias matemáticas por su Math Trek). En él nos hablaba ya de este algoritmo de Keller para clasificar equipos de fútbol (americano). Peterson comenta en dicha noticia el artículo ”The Perron-Frobenius Theorem and the Ranking of Football Teams,” SIAM Review, 35: 80-93, 1993, escrito por el matemático James P. Keener de la Universidad de Utah (autor del famosísimo y buenísimo “Mathematical Physiology“, dos volúmenes que hay leer si se quiere trabajar en matemática aplicada a la medicina). Por cierto, este artículo de Keener yo lo leí hace años, cuando leía todas las revistas de SIAM en papel (hace ya algunos años que no las leo con asiduidad porque online me quedo muchas veces sólo con los títulos y ¡¿selecciono más lo que leo?!). En dicho artículo, Keener estudia cuatro métodos para clasificar equipos que compiten dos a dos (como los de fútbol) y cómo estos métodos dependen del teorema de Perron-Frobenius. El artículo no cita a Keller en la bibliografía, pero sí en los Agradecimientos, literalmente ”Thanks to Joe Keller for introducing me to this fascinating topic over ten years ago.”

Peterson nos lleva más allá. Volvamos a él. Un equipo es bueno si vence a equipos buenos, que vencen a equipos buenos, … Una pescadilla que se muerde la cola. O en sus palabras, el problema de “quién fue primero, el huevo o la gallina”. Según Peterson, Keener logra resolver este dilema utilizando un algoritmo previamente sugerido por el matemático aplicado Joseph B. Keller de la Universidad de Stanford cuando era “alto cargo” de la organización matemática Society for Industrial and Applied Mathematics (SIAM). Keller quería saber cómo de buenas eran las revistas de SIAM comparadas con el resto de revistas en Matemática Aplicada (ahora mismo, las revistas de SIAM están entre las mejores y de más índice de impacto del campo de la Matemática Aplicada, destacando, como no, SIAM Review con factor de impacto 2.455 en el JCR 2007, la #3 de 165 en Matemática Aplicada).

¿Cómo resolvió Keller el problema de “la pescadilla que se muerde de la cola”? Utilizando el teorema de Perron-Frobenius (idea que Keener nos recupera en su artículo). El algoritmo actualmente conocido como PageRank de Google. Queréis más información en castellano, seguid los enlaces que os ofrecí en una entrada anterior sobre el “granadino” SCImago Journal Rank.

¿Y quién es Jon Kleinberg? ¿Qué pinta en el título de esta entrada? ¡Y tú me lo preguntas! Es uno de los especialistas mundiales en los algoritmo tipo PageRank, inventó al llamado algoritmo HITS, y ganó por ello el Premio Nevannlinna que se le concedió en el Congreso Internacional de Matemáticos de Madrid 2006 (premio al mejor trabajo en informática realizado por un matemático, foto). Los trabajos de Kleinberg han permitido desarrollar algoritmos muy eficientes para poder calcular métricas como el pagerank.

That’s all folks!

3 Comentarios

Participa Suscríbete

mno4k

Interesante. Los misterios de la internets, eh? La matemática no es lo mío, pero el artículo es claro y llevadero. Volveré por más!

Palapple

Thanks for sharing. Search engine optimization is indeed one of the most crucial areas in Internet marketing, it is a perfect bridge between technology and business.

Lyzanor

Muy curioso el artículo, se suele hablar mucho en la web de Google como empresa pero casi nada de la matemática y el pasado académico de esos dos informáticos.

Deja un comentario

Tu email nunca será mostrado o compartido. No olvides rellenar los campos obligatorios.

Obligatorio
Obligatorio
Obligatorio

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>