jueves, 15 de septiembre de 2011

El PageRank aplicado a la Red de Subte de la Ciudad de Buenos Aires

PageRank y Matrices
El PageRank es un eigenvector. Es el eigenvector asociado a la matriz markoviana que reúne todas las probabilidades de pasar de cualquier nodo de la red a cualquier otro. Lo característico de los eigenvectores es que al multiplicar la matriz por este vector, volvemos a obtener el mismo vector. En este caso esto es precisamente así porque el eigenvalor dominante de una matriz de Markov es el 1.


Así, por ejemplo, si a la matriz A la multiplico por el vector v=<-0.200724,-0.25976,-0.944582> voy a volver a obtener el vector v. Ese vector v es el eigenvector asociado a la matriz A y es el vector que tiene la información para crear el PageRank.


El PageRank de la Red de Subte
La red de subte de la Ciudad de Buenos Aires tiene 76 estaciones (nodos). Esos 76 nodos están unidos por 80 enlaces. Considerando que cada estación está enlazada con su adyacente por dos vías, una para ir y otra para volver, los enlaces son indirectos. Los enlaces indirectos no tienen dirección, es decir, expresan la idea de que se puede ir desde X hacia Y como de Y hacia X. La imagen muestra la red de subte (no está a escala, no tuve tiempo de ajustarla):


(Clic en la imagen para agrandar)

Consideré que los casos en que las estaciones están unidas por túneles donde los pasajeros tienen que caminar, el enlace también es indirecto. Por ejemplo, Carlos Pellegrini, 9 de Julio y Diagonal Norte están unidas entre sí y se puede ir de una a la otra en cualquier dirección.
En primer lugar, para reproducir el PageRank hay que generar la matriz de adyacencia. La matriz de adyacencia sintetiza toda la información de los nodos que están conectados entre sí. Como es una red con enlaces indirectos esta matriz es simétrica y su diagonal está compuesta por ceros. Una matriz de adyacencia en donde la diagonal está compuesta por ceros significa que ningún nodo se enlaza a sí mismo. Esta matriz tiene 76 filas y 76 columnas; una por cada estación.

Una vez armados de la matriz adyacencia tenemos que establecer de qué manera se ponderará cada enlace. La forma más práctica de hacerlo es suponer que nuestro pasajero imaginario al llegar a la parada elige aleatoriamente entre ir a la estación anterior o la estación siguiente. En otras palabras, todos los links se consideran inicialmente semejantes. Al calcular el eigenvector de la matriz del subte, y luego de normalizarlo, obtenemos un ranking probabilístico de cada nodo. En el gráfico de abajo se puede ver la red del subte en donde el tamaño de cada nodo está en función de su PageRank.

(Clic en la imagen para agrandar)

Queda claro que los nodos 9 de Julio, Carlos Pellegrini, Perú y Diagonal Norte son los más relevantes. Mientras que Congreso de Tucumán, Parque Chas, Carabobo, Caseros, Alem, Retiro, Constitución, Plaza de Mayo y Plaza de los Virreyes son los que menos puntaje obtienen.
En una red como esta, con pocas conexiones, en donde hay rayos que salen de un núcleo más conectado, las puntas de los rayos son las que menos PageRank obtienen. Es interesante notar que incluso Alem y Plaza de Mayo, dos nodos que se encuentra a poca distancia del núcleo más importante, obtienen tan poco PageRank como las más lejanas estaciones (e.g. Plaza de los Virreyes).
En la tabla se exhibe de mayor a menor PageRank las 76 estaciones. Como se puede apreciar, hay 4 grandes grupos. El PageRank terminó organizando las estaciones en un Top 4 que incluye a 9 de Julio, Carlos Pellegrini, Perú y Diagonal Norte. Un segundo grupo compuesto por 9 estaciones, un gran tercer grupo compuesto por 54 paradas y un último grupo de 9 estaciones.

(Clic en la imagen para agrandar)

Nota sobre el número de iteraciones necesarias para determinar el PageRank de esta pequeña red
La red del subte es muy pequeña; tiene pocos nodos y pocos enlaces. Por eso mismo es posible resolver el sistema y obtener una solución sin tener que recurrir a la fuerza bruta. De todos modos, para apreciar mejor cómo evoluciona el PageRank de cada estación de subte por cada nueva iteración a la que se somete el sistema, probé en Excel iterar hasta alcanzar una estabilidad apreciable. Esto permite observar como cada nueva iteración lleva el resultado más cerca de la convergencia. En el gráfico queda incluso aún más claro como se van generando estos 4 grupos de estaciones antes mencionados.


Notas:
PDF con la Red de Subte.
PDF con la Red de Subte con el tamaño de los nodos de acuerdo a su PageRank.


No hay comentarios: