Los jugadores de tenis más prestigiosos de la historia según el algoritmo PageRank

Una variante del algoritmo PageRank de Google aplicada al análisis de 133.261  partidos de tenis de la ATP jugados por 3.700 tenistas profesionales entre 1968 y 2010 indica que el jugador de tenis “más prestigioso” de la historia es Jimmy Connors (EE.UU. 1970-1996), seguido de Ivan Lendl (EE.UU. 1978-1994), John McEnroe (EE.UU. 1976-2002) y Guillermo Vilas (Argentina, 1969-1992). Manuel Orantes (España 1968-1984) es el número 15, y Rafael Nadal (España 2002-2010) es el número 24; no hay ningún otro español entre los 30 primeros puestos. Los datos analizados se han obtenido de la web de la ATP (Association of Tennis Professionals). Solo se han considerado los partidos de Grand Slam y del ATP World Tour (un total de 3640 torneos entre 1968 y 2010). El artículo técnico es Filippo Radicchi, “Who is the best player ever? A complex network analysis of the history of professional tennis,” ArXiv, 20 Jan. 2011.

El algoritmo PageRank se basa en la idea de que el prestigio de un jugador no está relacionado con su número de victorias sino con la calidad de las victorias: un jugador gana más prestigio cuando le gana a jugadores con más prestigio que a jugadores con menor prestigio. Para determinar el prestigio, Radicchi ha construido un grafo que conecta los tenistas de la ATP de tal forma que el jugador j se conecta con el i cada vez que el jugador i le gana un partido al jugador j. Cada conexión entre los jugadores j e i recibe un peso w(j,i) igual al número de veces que el jugador j ha perdido con el jugador i. Para determinar el “prestigio tenista” de cada jugador se asume que cada jugador inicialmente tiene un prestigio igual a la unidad y que el prestigio se transmite a través de los enlaces de la red multiplicada por el peso. El cálculo del prestigio requiere resolver un problema de álgebra lineal (un sistema acoplado de ecuaciones lineales).

Los interesados en todos los detalles del análisis realizado disfrutarán con la lectura del artículo original. Me limitaré a resumir algunos resultados curiosos. Entre los 10 jugadores de mayor prestigio se encuentran 9 jugadores que han sido número 1 de la ATP. Jimmy Connors es el jugador con la trayectoria más regular y más larga de entre todos los jugadores, llegando a estar en el top 10 de la ATP durante 16 años consecutivos (1973-1988). Rafael Nadal, el número uno actual del ránking de la ATP, ocupa el puesto 24 en el ránking de prestigio aunque tiene una trayectoria muy corta por su gran calidad como jugador; si solo se tienen en cuenta el número de sus victorias ocuparía el puesto número 40.

Rod Laver fue el mejor jugador entre 1968-1971 (cuando el ránking de la ATP todavía no existía). Por décadas, los mejores jugadores fueron Jimmy Connors (1971-1980), Ivan Lendl (1981-1990), Pete Sampras (1991-2000) y Roger Federer (2001-2010). Los mejores jugadores en tierra batida, césped y cemento son Guillermo Vilas, Jimmy Connors y Andre Agassi, respectivamente.

En resumen, un artículo curioso del que disfrutarán todos los aficionados al tenis. Acabaré copiando el listado de los 30 tenistas más prestigiosos.

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!