La fascinante historia del algoritmo de Google

El algoritmo PageRank no es una idea original de Google. El mérito fue su implementación eficiente en una red de miles de millones de nodos.

Larry Page y Sergei Brin querían ser académicos, no empresarios. En 1997 ofrecieron el algoritmo a Yahoo por un millón de dólares, pero la empresa declinó la oferta. En 2002, Yahoo intentó hacerse con PageRank por 3.000 millones de dólares, y Google la rechazó.

Quizás la primera aplicación práctica conocida del algoritmo se debe a un economista: Wassily Leontief (premio Nobel en 1971), de la Universidad de Harvard. Lo utilizó para representar el funcionamiento de una economía mediante un modelo de red Input-Output.

“La importancia de una página web es un problema inherentemente subjetivo que depende del interés de los lectores, de su conocimiento y de sus inclinaciones. Aun así, se puede decir objetivamente mucho sobre la importancia relativa de las páginas web. Este artículo describe PageRank, un método para valorar las páginas web de forma objetiva y mecánica, midiendo de forma efectiva la atención e interés humanos dirigidos hacia cada página. Comparamos PageRank con un “web surfer” aleatorio idealizado. Mostramos como calcular de forma eficiente el PageRank para un número grande de páginas y mostramos cómo utilizar el PageRank para la búsqueda y navegación de los usuarios”.

Así comienza uno de los artículos científicos más importantes de la historia, al menos en términos de su impacto inmediato sobre la realidad económica y social: “ The PageRank Citation Ranking: Bringing Order to the Web”, en el que Larry Page y Sergey Brin sentaban las bases de lo que sería el buscador de Google.

Internet es hoy lo que es gracias al ingente esfuerzo de un grupo de ingenieros por ordenar la información de forma relevante en un entorno en el que los grandes portales habían vendido los resultados de las búsquedas al mejor postor. Mientras tanto, dos estudiantes de doctorado de Stanford proponían un método para calcular la importancia de cada web a partir de los vínculos (links) que cada web recibía, así como de la importancia relativa de las páginas que emitían cada vínculo.

Pero, a pesar de la importancia del artículo, la cultura popular ha inflado la importancia real del propio algoritmo e ignorado lo que convirtió a Google en lo que es hoy: su implementación eficiente en una red de miles de millones de nodos.

De los 24 millones de páginas web que su primera versión consiguió indexar, Internet ha crecido hoy hasta superar, según estimaciones razonables, los 4.000 millones de direcciones distintas. Dado que el algoritmo ha de buscar no solo los vínculos de primer orden que una página recibe, sino también los de órdenes superiores, el problema real no se encuentra en la idea original de cómo medir la relevancia en Internet, sino en lograr indexar el mayor porcentaje de sitios existentes de Internet (¡miles de millones!) y en evaluar los vínculos que entran y salen de cada web.

Como afirmaba Thomas Alva Edison, “el genio consiste en una parte de inspiración y 99 de trabajo duro”. Aunque nos gusta creer que un momento de inspiración puede dar lugar a esa idea que nos hará ricos, lo cierto es que, tras esa inspiración inicial que todo el mundo experimenta de vez en cuando, se encuentran 99 partes más de durísimo trabajo para dar forma e implementar la idea para que sea socialmente útil. Y, de la misma forma, la idea del PageRank es solo un pequeño momento de inspiración al que siguió un enorme esfuerzo por parte de varios de los mejores ingenieros informáticos del mundo. Además, como veremos, la idea ni siquiera era original: solo se trataba de un concepto bien conocido por los matemáticos, una variante de la medida de centralidad basada en el “vector propio” (eigenvalue), para el cual muchos científicos habían ya desarrollado métodos de cálculo y aplicaciones prácticas.

Los orígenes del algoritmo PageRank

El análisis de redes había nacido, lógicamente, mucho antes que internet. Una de las medidas más corrientes que los matemáticos habían desarrollado para evaluar la centralidad o influencia de un nodo sobre una red es la “ centralidad del vector propio”.

Un reciente artículo de Massimo Franceschet ( “PageRank: Standing on the Shoulders of Giants”) ha rastreado los usos históricos de esta medida, encontrando sorprendentes casos:

* Jon Kleinberg, profesor de la Universidad de Cornell, había desarrollado un algoritmo muy similar al PageRank, tratando a las páginas como “receptoras de votos” (hubs) o “emisoras de votos” (authorities).

* Otro campo muy susceptible de ser analizado mediante medidas de centralidad son las publicaciones científicas. Al igual que las páginas de Internet, las publicaciones contienen citas a otros artículos y son a su vez citadas. Gabriel Pinski y Francis Narin definieron también la importancia de un artículo a partir de su centralidad. El impacto de artículos y revistas se puede consultar hoy en el proyecto www.eigenfactor.org.

* Quizás la aplicación más sorprendente, y además la aplicación práctica más antigua que se conoce, se debe… ¡a un economista! Wassily Leontief, por aquel entonces profesor de Harvard, desarrolló su modelo Input-Output –que mide los flujos de factores intermedios entre sectores- tratando la economía como una red (en su representación matricial). El objetivo de Leontief era identificar qué sectores económicos constituían un “cuello de botella” al requerir demasiados factores productivos cuando la demanda de su producto aumentaba, para lo cual recurrió a una versión primitiva del PageRank de Google. Finalmente, Leontief recibió el Premio Nobel de Economía de 1971 por su conocido modelo.

A estos usos históricos de la idea de centralidad hay que añadir, por supuesto, nuevas aplicaciones recientes, como su uso para la modelización de sistemas evolutivos. Stefano Alesina y Mercedes Pascual, de las universidades de Chicago y Michigan, han aplicado el algoritmo para el estudio de las extinciones de especies, en el que la importancia de las mismas se basa en el soporte vital que ofrecen para la supervivencia de otras especies.

Epílogo

Es necesario aclarar que, como es lógico y ético en la comunidad científica, en ningún momento Page y Brin se atribuyen la invención de su medida, ya que citan como fuentes anteriores usos de la misma y dejando bien claro que su aportación se centra en la computación eficiente del mismo en una red gigantesca y en el método de lectura y almacenamiento de las webs.

Además, Page y Brin tampoco pretendían convertirse en grandes empresarios, sino que sus aspiraciones estaban puestas en el mundo académico. Tras desarrollar el buscador hoy conocido como Google, intentaron vender su producto al mejor postor por todo Silicon Valley para así poder centrarse en terminar sus estudios de doctorado. ¿Y qué precio pedían? ¡Solamente un millón de dólares! Google fue incluso ofrecida a Yahoo, que rechazó la compra.

La frustración de no encontrar comprador les animó a seguir adelante con su idea, y el fin de la historia es conocida por todos: Google es hoy una de las empresas más poderosas del planeta. Quizá no tenga tantos beneficios como las empresas petrolíferas (y ni siquiera más ingresos que Apple), pero es la empresa con la mayor capacidad de obtención y procesado del petróleo del siglo XXI: la información.

Fuente: Abel Fernández – @Sintetia en Diario Turing – La verdadera (y fascinante) historia del algoritmo de Google