viernes, 9 de septiembre de 2011

El PageRank y las Cadenas de Markov

A comienzos de 1998, Larry Page (uno de los dos creadores de Google), que estaba cursando su Ph. D. en Stanford University, publica “The PageRank Citation Ranking: Bringing Order to the Web”. Page estaba investigando de qué manera se podía ordenar Internet. Su intención era crear un método que, a diferencia del de Yahoo, no tuviera intervención humana. Y que a su vez fuera más eficaz que Altavista.

El método
En los años ´70 se comenzó a desarrollar técnicas para determinar cuáles eran los trabajos científicos más importantes y quiénes eran los autores más influyentes. Eugene Garfield, uno de los creadores de la bibliometría, propuso rankear a los científicos en función de la cantidad de citas que recibían sus trabajos. Es razonable pensar que si un autor es muy citado debe ser porque es muy relevante en la materia. Lo mismo podría decirse de una página web. Un link es el símil de una cita bibliográfica. Cuantos más links apunten a una dirección web, esa dirección se supone que es más relevante. Sin embargo, este método adolece del problema de que no todas las citas son igual de valiosas. Si, por ejemplo, nos citara un científico que ganó un premio Nobel, esta referencia debería tener más peso que una que fue realizada por un investigador que acaba de graduarse. Ocurre lo mismo con los links. Un link en el nytimes.com debería pesar más que un link en un pequeño blog. Para incluir un ponderador que tenga en cuenta estas diferencias, Page utiliza una variación probabilista del método propuesto por Garfield.

Cadenas de Markov
Imaginemos que todo nuestro universo son tres ciudades, Cipolletti, Mendoza y Ciudad de Buenos Aires. En donde cada una de estas ciudades tiene 100 habitantes. Cada año, el 10% de los habitantes de Cipolletti decide irse a vivir a Mendoza, mientras que el 20% prefiere partir a Buenos Aires. Sólo el 70% se queda a vivir en Cipolletti. En Mendoza cada año emigra el 5% de su población a Cipolletti y el 10% a Buenos Aires y sólo el 85% prefiere quedarse donde está. Por último, el 5% de los habitantes de Buenos Aires deciden, cada año, retirarse a vivir al sur, y el 2% se van a Mendoza. Supongamos, además, que estos porcentajes son siempre los mismos. Entonces, cómo será la población de cada ciudad después de que se produzcan todos los movimientos migratorios. Una forma de solucionar este problema es mediante las matrices de Markov. Su nombre hace referencia a Andrey Markov (1856 -1922), quien fuera un matemático ruso que estudió procesos estocásticos como este. Por ejemplo, en este caso, esta matriz resume toda la información antes expuesta.
Cada renglón y cada columna representan a Cipolletti, Mendoza y la Ciudad de Buenos Aires. Los valores de la matriz son los porcentajes de la población que saltan de una ciudad a la otra. Así, si las tres ciudades comienzan con 100 habitantes cada una, luego de transcurrido un año Cipolletti tendrá 80 habitantes, Mendoza 97 y Buenos Aires 123. Al segundo año Cipolletti tendrá 67 habitantes, Mendoza 92 y Buenos Aires 140. Si seguimos iterando, el proceso convergerá en que Cipolletti tendrá 42 habitantes, Mendoza 55 y Buenos Aires 201. A partir de ese momento ya no cambiarán más las poblaciones de las tres ciudades. Todas las migraciones se cancelarán entre sí y el sistema entrará en un estado estacionario.

PageRank (el caso más sencillo)
La estrategia de Page para atacar el problema fue aplicar esta noción de las cadenas de Markov a la Web. Cada página web tiene links entrantes (aquellos que dirigen hacia ella) y links salientes. Imaginamos que quien navega internet es una persona que cliquea de forma aleatoria cualquier link que encuentra. Si hiciera esto billones de veces veríamos que al cabo de un tiempo este navegador habría pasado más veces por ciertas páginas que por otras. Sencillamente porque es más probable encontrarse con un link que nos dirija al nytimes.com que a la web del gobierno de Formosa.
Por ejemplo, si la web fueran sólo 3 sitios en donde el sitio A tuviera dos links salientes, uno que dirige hacia B y otro que dirige hacia C, el sitio B tuviera un sólo link hacia C y, por último, C tuviera un link saliente hacia A, este navegador aleatorio generaría el siguiente comportamiento. Digamos que el usuario comienza en A. Allí tiene un 50% de probabilidades de darle clic al link que lo dirige a B o de darle clic al link que lo dirige a C. Supongamos que se dirige a B. En B sólo puede hacer clic en el único link que hay. Ese link lo dirige a C. En C le ocurre lo mismo y termina en A. Aquí el juego comienza otra vez; tiene 50% de probabilidades de dirigirse a C o de ir hacia B. Al fin y al cabo los sitios donde es más probable, en un momento cualquiera, encontrar a este navegante aleatorio son A y C. Por eso mismo esos sitios deberían ser más relevantes que B.
Una manera más formal de establecer el ranking consiste en señalar que cada página web tiene, como en el caso de las ciudades, inicialmente el mismo ranking. Ahora, cada sitio transfiere más ranking a otro cuanto mayor es el porcentaje de sus links salientes que apuntan hacia ese otro sitio. En el ejemplo anterior, A transferirá la mitad de su ranking a B y la otra mitad a C. Y cada sitio recibe ranking de los demás en función del porcentaje de links que estos tienen dirigiendo hacía él. Entonces, para este ejemplo de 3 sitios web la forma matricial es:
La solución de este sistema de transferencia nos da que hay un 40% de probabilidades de encontrar a nuestro navegante aleatorio en A, un 40% de probabilidades de encontrarlo en C y un 20% de encontrarlo en B. Larry Page utilizó estas probabilidades para establecer el ranking. El PageRank (Page parece haber sido nacido para esto; su apellido significa página. Y se llama PageRank por su apellido.) es justamente el ordenamiento de los sitios web de acuerdo a estas probabilidades. Siguiendo con nuestro ejemplo, si buscáramos alguna palabra que estuviera dentro del contenido de los sitios A y B, entonces el buscador devolvería en primer lugar a A como más relevante y a B en segundo lugar. Así es como se establece el orden de los resultados de búsqueda de forma matemática.

Nota: Hay casos más complejos en donde se tienen en cuenta otras variables (tamaño de letra, lugar donde está link en el sitio, fecha de última actualización del sitio, etc). Aquí sólo quería exponer el caso más sencillo del ranking.

Nota 2: Este post es una introducción al tema.

Links: The PageRank citation ranking bringing order to the web. Larry Page

No hay comentarios: