Pagerank: El algoritmo que llevó a Google a la cúspide

La historia de internet se puede dividir en antes y después de Google. El impacto del buscador facilitó al acceso de millones de páginas a los usuarios ávidos de encontrar en forma rápida y eficiente un contenido. Desde una página simple que contiene un campo de texto y un botón podemos buscar contenidos en base a unas simples palabras y en la mayoría de los casos encontramos rápidamente lo que estamos buscando.

Para los que accedieron por primera vez a la web con Google como un actor ya establecido es algo que no sorprende. Pero una mirada a los números de la web nos indican que algo están haciendo en Google a lo grande:

• Utiliza más de 1 millón de servidores en sus diferentes datacenters alrededor del mundo (número estimado y no develado)
• Tiene indexado más de 300 trillones de páginas
• Retorna resultados de búsquedas en menos de 1 segundo. (ejemplo: una búsqueda de la palabra "internet" retorna 4.140.000.000 resultados en 0,38 segundos. Buscar "google" retorna 7.380.000.000  resultados en 0,69 segundos).

y lo más importante, las búsquedas que retorna suelen ser bastante acertadas. Pero qué algoritmo hay detrás de eso? quién lo creó?



En el año 1998 se lanza el sitio de búsqueda de Google. La página de inicio - que incluía un aviso de ser un desarrollo "beta" - permitía buscar entre 26 millones de páginas indexadas. Fundada por Larry Page y Sergey Brin dos estudiantes de la Universidad de Stanford, Google no fue el primer buscador de la Web.

La World Web Wide, existente desde 1991 fue creciendo de manera vertiginosa de unas pocas decenas de servidores y sitios a millones de ellos. Para la creciente población buscando un contenido determinado próntamente se hizo necesario herramientas que lo acerquen a la respuesta de la forma más rápida y satisfactoria posible. En el año donde apareció Google ya existían varios buscadores que eran utilizados por quienes surfeaban por la red: Altavista (Enero 1994), Yahoo (Abril 1994), Lycos (Julio 1994),  Excite (Diciembre 1995) y Hotbot (Mayo 1996). Desde simples colecciones de páginas categorizadas por humanos como Yahoo pasando por indexadores de metadatos, hasta indexadores de contenido completo que recorrían la web autónomamente para mantener actualizado los contenidos era la oferta de buscadores. La búsqueda podía ser algo frustrante. Las colecciones manuales solían tardar bastante tiempo en agregar o actualizar las páginas que brindaban como resultados. Los indexadores automáticos solían retornar información no relevante para el usuario. La tarea de buscar podía ser extenuante.

En ese contexto, Page y Brin comenzaron a trabajar en un buscador que combinara lo último en la tecnología disponible y se enfocaron en la forma de mejorar la calidad de los resultados. El algoritmo PageRank vio la luz como aporte fundamental a los métodos de indexación. Hoy en el paper altamente citado "The PageRank Citation Ranking: Bringing Order to the Web" se puede leer como presentaron al mundo este método.

PageRank trata a la web como un grafo dirigido donde cada nodo es una página y cada arista es un enlace de una página a otra. Cada página tiene asociado un valor que determina la importancia de la misma en la red. Esa importancia se calcula en base a la cantidad y a la importancia relativa de páginas que linkean a la misma. Es decir la centralidad de una determinada página en el grafo de la web. Una página importante tiende a ser referenciada por muchas otras páginas. Pero su importancia aun es mayor si aquellas páginas que lo referencian son en si mismas importantes.

El principio matemático de PageRank no es en si algo novel, sino que es una aplicación que se estaba realizando en otros campos.  Massimo Franceschet, en su paper “PageRank: Standing on the Shoulders of Giants”, rastrea los usos históricos del principio utilizado por PageRank en otros campos y las condiciones necesarios para poder resolverse en forma satisfactoria la operatoria. Aun así la gran innovación de PageRank fue lograr representar en una matriz la representación de la web y agregar las restricciones y condiciones para poder calcular el valor de importancia de cada pagina.

Utilizan una explicación sencilla para graficar el método: el caminante aleatorio (random walker). Un caminante inicia un recorrido desde una página web aleatoria y va seleccionando al azar entre los diferentes enlaces disponibles la página de destino. Luego de varias traslaciones se puede observar que ciertas páginas tendrán más probabilidad de estar siendo visitada en ese momento. Esas páginas son mas centrales y por lo tanto más importantes.

El problema fundamental que solucionó PageRank es que hacer en los casos donde el visitante llega a una página o a un ciclo sin salida. En esos casos el cálculo de la importancia se desvirtua, puesto que esas paginas a la larga terminan atrapando al caminante, conviertiéndose en las únicas importantes en el circuito. Para eso inventan la teletransportación, o la capacidad del caminante de 1 de cada 5 veces transportarse a una página tomada al azar.

Page y Brie crean un buscador que inicialmente llaman BackRub en 1996 y lo instalan en los servidores de Stanford. Deciden vender su desarrollo a alguna empresa interesada para seguir sus estudios y carreras académicas. Entre las firmas visitadas se encontraban Yahoo, Altavista y Excite. En su libro "The Google Story" David A. Vise y Mark Malseed narran diferentes anécdotas de diferentes rechazos a esta idea. También se pueden encontrar otros puntos de vista en el libro "In The Plex: How Google Thinks, Works, and Shapes Our Lives". Las razones son diversas: Empresas que no vieron la potencialidad del algoritmo, compañias con resistencia al cambio interno y emprendimientos cuyo negocio era proporcionar resultados de búsqueda no satisfactorios para mantener al usuario dentro de su portal y ganar plata con publicidades.
Page Y Brie finalmente cambian el nombre del buscador por Google, crean la compañia Google Inc gracias al aporte de inversores y el resto es historia conocida.