Usuarios de Internet en Argentina por Provincia a Octubre de 2011

Usuarios de Internet en Argentina
Según Comscore, líder mundial en mediciones del mundo digital, en octubre de 2011 había 13.277.000 usuarios únicos de Internet en la Argentina. Resulta difícil encontrar estadísticas que indiquen cuántos usuarios hay de Internet en la Argentina por cada provincia. En cambio, hay varias mediciones sobre la cantidad total de usuarios de Internet en nuestro país. Por ejemplo, de acuerdo al Banco Mundial, en el 2009 el 30% de la población argentina estaba conectada a Internet (ver gráfico abajo). Esto es cerca de 12 millones de personas. Otras estimaciones establecían que en el 2007 Argentina tenía 16 mlls de usuarios (1). El sitio argentina.ar del Gobierno Nacional recientemente publicó una noticia que establecía en 21 mlls la cantidad de internautas argentinos (2).



De acuerdo a la American Registry for Internet, en la Argentina hay 13,8 mlls de IP´s. La IP es única por cada dispositivo que se conecta a la Web. El número de IP´s podría usarse como aproximado de la cantidad de usuarios de Internet. Sin embargo, hay que tener presente que varias personas pueden usar una misma computadora, por lo tanto habrían más usuarios que cantidad de IP´s. Y, también, hay servidores y otros dispositivos que se conectan a Internet y que no son utilizados por humanos, lo cual nos haría sobreestimar la cantidad de usuarios. Teniendo en cuenta estas salvedades, la cantidad de IP´s puede servir como una variable aproximada a la cantidad de usuarios de Internet.

El problema de determinar la cantidad de usuarios de Internet está en la definición. ¿Quién es un usuario de Internet? ¿El que navegó alguna vez? ¿El que navega todos los días? ¿El que tiene un dispositivo con acceso a Internet? Ese no es el único problema, también está el problema del método. Por ejemplo, la metodología de Comscore para determinar la cantidad de usuarios se basa en una gran cantidad de parámetros. Esos parámetros son analizados con criterios biométricos para identificar los comportamientos humanos de los realizados por máquinas. Por ejemplo, la forma en que realizan los clics, cómo mueven el mouse, etc. De los demás estudios desconozco qué metodología usan. Por esa misma razón es que para determinar la cantidad de usuarios de Internet por provincia me baso en las estimaciones de Comscore.

Cantidad de usuarios de Internet en Argentina por provincia
Más del 90% de los usuarios de Internet en Argentina usan alguna herramienta de Google. En otras palabras, casi todos los navegantes argentinos pasan alguna vez en el mes por el buscador de Google o por Youtube. Cada vez que pasan por alguno de esos sitios una cookie se guarda en la computadora del usuario. Esa cookie permite distinguir al dispositivo que pasó y/o que vuelve al sitio. Dada la gran penetración que tiene Google, la cantidad de dispositivos inseminados con esas cookies permite tener una aproximación muy certera de dispositivos que se conectan desde la Argentina.

El acceso a la información de Google desagregada por provincia me habilitó a aplicar esa distribución al total de 13,2 mlls de usuarios de Internet determinado por Comscore.
Por otra parte, el Indec genera estadísticas cada 3 meses de cantidad de conexiones a Internet por provincia. Los datos incluyen las conexiones desde hogares y desde las empresas. El criterio del Indec es considerar que hay una conexión por cada relación contractual existente entre una persona y un proveedor de servicios de Internet. En junio de 2011 había 6.441.330 conexiones desde hogares y 986.628 desde organizaciones. Lo que hace a un total de 7.397.958 conexiones. (3)

Con la información de Google de cookies por provincia y con los datos del Indec pude realizar tres estimaciones sobre la cantidad de usuarios de Internet por provincia en Argentina. La estimación “Google” consiste en aplicar al dato de Comscore la distribución de las cookies por provincia. Mientras que las estimaciones basadas en los datos del Indec distribuyen los 13,2 mlls de usuarios de acuerdo a 1) la cantidad de conexiones por hogares y 2) la cantidad de conexiones totales (hogares más organizaciones) por provincia. La tabla expuesta a continuación exhibe los datos de las tres estimaciones. (4)

Usuarios de Internet por provincia en Argentina a octubre de 2011:
Según estas estimaciones, entre el 62% y el 69% de los usuarios de Internet se encuentran en la zona Provincia de Buenos Aires más Ciudad de Buenos Aires.

Un problema serio de consistencia de estas tres estimaciones es que la Ciudad de Buenos Aires tiene una penetración de Internet (i.e. Usuarios de Internet / Población Total) superior al 100%. La estimación más baja da una penetración del 139%. Es interesante notar que esta incoherencia también se da con los datos de cookies únicas de Google. Quizás esto esté relacionado a la mala asignación de las IP en la Argentina que no permite saber con exactitud desde qué locación se está conectando el usuario. También es posible que debido a que muchas personas viven en Prov. de Buenos Aires pero trabajan en la Ciudad, se genere un solapamiento en el conteo de cookies.

El resto de las provincias obtienen una penetración consistente con su población (ver mapa inicial). Si dejamos de lado a Ciudad de Buenos Aires, según las estimaciones realizadas con los datos del Indec, Tierra del Fuego (59%), Chubut (34%), Neuquén (33%), Córdoba (33%) y Santa Fé (32%) tienen las mayores tasas de penetración. Mientras que la estimación realizada con los datos de Google ubica en el Top 5 a Santa Fe (44%), Santa Cruz (41%), Córdoba (32%), Neuquén (29%) y Buenos Aires y Mendoza con 25%.


Modelo explicativo de la cantidad de usuarios por provincia
Con el fin de evaluar la coherencia de los datos y a modo explorativo armé un modelo predictivo que relaciona la penetración de Internet en cada provincia con a) el porcentaje de hogares con necesidades básicas insatisfechas (NBI) b) la población total de la provincia y c) una variable de densidad.

Es de esperar que exista una relación negativa entre el porcentaje de hogares con NBI y la cantidad de conexiones a Internet. Una mayor población de bajos ingresos tiene menos posibilidades de adquirir servicios de este tipo.

La población total de la provincia debería correlacionar positivamente con la cantidad de usuarios. Donde hay más población es más factible que haya más consumidores capaces de adquirir el servicio. Además, esta variable está relacionada con la masa crítica necesaria para que las empresas de Internet estén dispuestas a realizar la inversión para proveer el servicio.

La variable de densidad es el cociente entre el departamento que más viviendas tiene, dentro de cada provincia, respecto del total de viviendas censadas en toda la provincia. Debido a que los costos de distribuir el tendido de fibra óptica aumentan cuanto más disperso están los potenciales usuarios, es esperable que a mayor concentración de viviendas, más conexiones de Internet.

En la estimación del modelo no tuve en cuenta los datos de Prov. de Buenos Aires y de Ciudad de Buenos Aires. En el caso de Prov. de Buenos Aires la exclusión se basa en que la medida de densidad no es adecuada. La Matanza es el departamento con mayor proporción de las viviendas de la provincia. Sin embargo, hay otros departamentos que también están muy densamente poblados. Ciudad de Buenos Aires no ingresa en el modelo porque la penetración de Internet excede el 100%.

La tabla expuesta a continuación exhibe los resultados de las tres estimaciones.

En gris se encuentran descatadas las variables que son significativas al 5%. Como se puede apreciar, las dos variables que son significativas en los tres modelos son la medida de densidad (Centralidad) y la medida de pobreza (NBI).

El porcentaje de la población con necesidades básicas insatisfechas resulta ser la variable explicativa más fuerte. En efecto, por cada 1% más de población con NBI, la penetración de Internet se reduce en un 1%. Mientras que por cada 1% más de densidad de viviendas, la penetración de Internet aumenta un 0,5%.
En la estimación de Google la variable población es significativa. La lectura en este caso es: por cada 1.000.000 de habitantes, la penetración aumenta un 9%.

Las tres estimaciones tienen un alto poder explicativo, las variables son significativas y tienen signos coherentes. En función de los resultados de las estimaciones, la distribución de usuarios de Internet por provincia con los datos de Google parece ser la que mejor se puede explicar con las variables seleccionadas. La segunda mejor es la distribución que tiene en cuenta el total de conexiones (residenciales + organizaciones) censadas por el Indec.

Links y Notas:
Todos los datos se pueden bajar haciendo clic aquí: https://docs.google.com/spreadsheet/ccc?key=0Ah_ZMWRG754hdFdaUmhXSVBxZC14Z1piSTNTOUpBdlE

(1) http://www.lanacion.com.ar/970128-en-la-argentina-hay-16-millones-de-usuarios-de-internet

(2) http://www.argentina.ar/_es/pais/C4719-mas-del-50-por-ciento-de-los-argentinos-ya-son-usuarios-de-internet.php

(3) El Indec cometió un error en el informe de Septiembre 2011. La suma de conexiones desde organizaciones por provincia no coincide con el total. Asumo que el total es el que está equivocado.

(4) Usuarios de Internet en Argentina por Provincia a Octubre de 2011: https://docs.google.com/spreadsheet/ccc?key=0Ah_ZMWRG754hdENCRHplVXlkcEpHVnZzVTVBc2Ffb1E

Gracias a Julián Rodriguez Orihuela por la ayuda con el mapa.

Network Motifs

Se le llama motifs a los subgrafos que aparecen con una frecuencia mayor que la observada en los grafos construidos de forma aleatoria. Por ejemplo, el lado izquierdo de la imagen muestra una red real, mientras que el lado derecho muestra cuatro redes construidas de forma aleatoria. En la red real el patrón triangular aparece 5 veces. En las redes aleatorias esta forma sólo aparece en 2 oportunidades. Esa mayor frecuencia podría estar indicando una característica intrínseca de la red real.

Para descubrir estos patrones se desarrollan algoritmos que comparan las frecuencias en las que aparecen los motifs en redes reales versus en redes construidas de forma aleatoria. En primer lugar se escanea el grafo original para obtener todos los subgrafos de n-nodos que existen en él y la cantidad de veces que aparecen. Luego se comparan la frecuencia en la que efectivamente aparecen con la frecuencia en la que aparecerían si el grafo se construyera de forma aleatoria. Aquellos subgrafos que aparecen en mayor frecuencia se entiende que son característicos de la red.

Para que la comparación entre la red real y aleatoria sea equivalente se construyen redes aleatorias respetando la cantidad de links entrantes y salientes que tiene cada nodo en la red real. Además, la red aleatoria está construida con la misma cantidad de nodos y enlaces que tiene la red real:

“For a stringent comparison, we used ramdomized networks that have the same single-node characteristics as does the real network: each node in the randomized networks has the same number of incoming and outgoing edges as the corresponding node has in the real network”.(1)

En general se establece una probabilidad menor o igual a 0.01 para indicar si el patrón es estadísticamente significativo. Así, por ejemplo, se dice que es un motif si la probabilidad de que aparezca ese patrón en una red construida de forma aleatoria es menor o igual a 0.01.

Detección de Network Motifs

En el trabajo Network Motifs: Simple Building Blocks of Complex Networks, Milo et al aplicaron el algoritmo desarrollado por ellos a varias redes. Las redes que analizaron eran genéticas, de neuronas, de la cadena alimenticia, de circuitos electrónicos y de Internet. La tabla de abajo muestra los resultados de sus investigaciones.

Por ejemplo, las redes Food webs en donde cada nodo representa grupos de especies y los enlaces indican qué nodo es predador de otro nodo revelaron dos tipos de motifs, el Three chain y el Bi-parallel. El Three chain quiere decir que los X´s se comen a los Y´s y los Y´s a los Z´s. El motif Bi-Parallel revela que si un predador tiene a dos especies como presas, es probable que esas dos especies compartan su presa.
Un aspecto interesante de la investigación es que los motifs que surgieron son diferentes según la red se trate de neuronas, circuitos electrónicos, páginas webs o genes. Esto podría indicar que es posible distinguir entre redes según los patrones dominantes.

Otra característica de las redes reales es que a medida que la red se van aumentando su tamaño, la concentración de motifs se mantiene constante. En cambio, en las redes creadas de forma aleatoria los patrones se van perdiendo. El gráfico de arriba muestra la concentración del motif Feedfoward loop en la red de Escherichia coli (círculos negros) y en las redes aleatorias semejantes (círculos blancos). En el caso de la red real la concentración se mantiene relativamente estable a medida que aumenta el tamaño de la red, mientras que en la red aleatoria la concentración decae.

Detección de motifs en las redes del Subte y de Aerolíneas Argentinas

En general las redes que trabajaron Milo et al tienen una gran cantidad de nodos y enlaces. La red más grande que analizaron, la de páginas webs, tiene 325.729 nodos y 1,4 mlls de links. También analizaron redes más pequeñas, como las de presa-predador. Pero en esos casos tuvieron la posibilidad de analizar varias redes pequeñas.

La detección de motifs requiere que el análisis sea extenso. Lo que sigue es sólo un acotado ejercicio para observar qué resultados se obtienen al analizar la red del subte de la Ciudad de Buenos Aires y la red aérea de Aerolíneas Argentinas.

La detección de motifs la realicé con el algoritmo desarrollado por Wernicke. En la red del subte de Buenos Aires el motif que se encuentra es este:

Aparece con una frecuencia de 6,6 veces en la red real mientras que en las redes aleatorias aparece con una frecuencia aproximada de 0,062 y una desviación estándar de 0,003.

 En la tabla se muestran los resultados que obtuve para el análisis de la red del subte y de Aerolíneas Argentinas para la detección de motifs de 3 y 4 nodos. En ambos casos los resultados generan motifs en donde uno de los nodos recibe más links que el resto.

Notas y Links:
(1) Network Motifs; Simple Building Blocks of Complex Networks. Milo et al Science 2002

Algoritmo desarrollado por Wernicke: Link

A excepción de la última tabla, el resto pertenece al trabajo de Milo.

Aerolíneas Argentinas: Análisis de su red aérea

El mapa muestra la red aérea de Aerolíneas Argentinas y Austral para los vuelos de cabotaje en Argentina. La fuente de la información es la revista Alta de octubre de 2011.
A simple vista se nota que el aeropuerto de la Ciudad de Buenos Aires es el nodo más relevante de la red. Todos demás nodos están conectados con Aeroparque Jorge Newbery. También es notorio que la mayoría de los nodos sólo pueden ser alcanzados si antes se pasa por Buenos Aires.

Una característica de esta red es que desde el punto de vista del pasajero, la red está dada. Si el pasajero quisiera transportarse desde La Pampa a Mar del Plata tendría primero que ir a Buenos Aires y luego viajar a la costa. Pero desde el punto de vista de la línea aérea, la red puede tomar cualquier forma. Los aviones pueden alcanzar cualquier aeropuerto sin necesidad de visitar algún otro en particular. Por eso mismo los instrumentos de medición utilizados para describir la red adquieren sentido sólo si se los piensa desde el lugar de pasajero.

En esta otra representación, que no tiene en cuenta la posición geográfica de los aeropuertos, se revela aún más la relevancia del nodo Buenos Aires dentro de la red.

Con el objetivo de tener una métrica que permita identificar las diferentes relevancias de los aeropuertos, calculé el PageRank y la Betweenness Centrality de cada nodo. El siguiente mapa muestra sobre cada aeropuerto un círculo cuyo tamaño es proporcional al valor de Betweenness Centrality.


Como se puede apreciar, el aeropuerto de Buenos Aires obtuvo un valor tan grande que no permite observar las diferencias entre los demás aeropuertos. Para reparar esto, en los siguientes dos mapas exhibo la Betweenness Centrality y el PageRank para todos los aeropuertos exceptuando a Buenos Aires.

Betweeness Centrality

PageRank

Los nodos que más PageRank obtienen –después de Aeroparque Jorge Newbery- son: Córdoba, Ushuaia, El Calafate, Salta, Bariloche, Mendoza y Trelew. En el siguiente link se encuentra la tabla con todos los datos.

Notas:
En este link se puede jugar con la tabla que contiene los datos de PageRank y Betweenness Centrality y las coordenadas de los aeropuertos: http://www.google.com/fusiontables/DataSource?snapid=S2969542lxz

Aquí están las coordenadas y los enlaces entre aeropuertos: http://www.google.com/fusiontables/DataSource?snapid=S296956HwTP

La fuente de los datos es la revista Alta de octubre 2011.

Distribuciones de Frecuencia Ocultas en Escaleras, Puertas y Canchas de Fútbol

Las distribuciones de frecuencia se encuentran en la base de la estadística. Gráficamente una distribución de frecuencia se construye dividiendo el eje de las mediciones en intervalos de igual longitud. Y sobre cada intervalo se construye un rectángulo cuya altura es igual a la cantidad de observaciones que se encuentran dentro del intervalo.

Ejemplo de Distribución de Frecuencia

Las distribuciones de frecuencia exponen un cúmulo de datos que nos permite distinguir con rapidez qué valores se están repitiendo más a menudo. A su vez, la acumulación de datos nos permite descubrir los patrones de repetición sin tener que pasar por la experiencia de vivenciar todos los casos nuevamente. Una persona que ha vivido muchos años en el campo es capaz de con sólo mirar el cielo, sentir la temperatura e identificar la dirección del viento, predecir si lloverá. Es capaz de hacer eso porque ha acumulado una experiencia que le permite descifrar los patrones que traen lluvia de los que no. Si esta persona plasmara esa información en tablas, gráficos y otros instrumentos seguramente podría transmitir esa experiencia y ahorrarnos todo el tiempo necesario para acumularla.

Las formas que asumen las distribuciones de frecuencia están asociadas con los procesos que las generan. Si, por ejemplo, arrojamos un dado y contabilizamos cuántas veces sale cada una de las seis caras, nos vamos a encontrar con que cada cara sale con la misma probabilidad; 1/6 (si el dado está bien diseñado). La distribución de frecuencias que genera el experimento de contabilizar las caras que salen de arrojar un dado se denomina uniforme. Otros procesos generan distribuciones normales, sesgadas hacia la izquierda o hacia la derecha, bimodales, exponenciales, con más acumulación de datos alrededor de la media, con colas pesadas, etc.

Si observamos a nuestro alrededor podemos descubrir cientos de  diferentes distribuciones que nuestros pies y manos han plasmado en diversos materiales. La foto de abajo muestra la puerta de mi casa. Como la cámara de fotos no logró reproducir los colores con la intensidad que tienen, del lado derecho incluí una imagen editada que intensifica las diferencias de color.

Encima del picaporte se ve una mancha que se vuelve más intensa en el centro. Ese centro corresponde con la altura en la que me queda cómodo abrir la puerta. La mancha representa la distribución de frecuencia de donde suelo apoyar la mano para tomar la puerta. La mancha debajo del picaporte podría ser la distribución de frecuencia asociada al evento "poner la llave en la cerradura".

En esta otra imagen vemos el teclado de una computadora. A juzgar por la mancha sobre la barra espaciadora, la persona que usa esta Mac acciona con muchísima más frecuencia el espacio con el pulgar derecho. Si asociásemos a cada punto de la superficie de la tecla un par de coordenadas x e y, entonces podríamos obtener una distribución de frecuencia de 2 variables semejante a la de este ejemplo interactivo (darle clic para probar):

   

La fotografía de abajo corresponde a los escalones del edificio de la Casa de la Cultura del Gobierno de la Ciudad de Buenos Aires. El edificio fue inaugurado en 1898. Desde hace 113 años por esas escaleras han pasado cientos de personas que provocaron un desgaste en los escalones de piedra. El desgaste es tan pronunciado que nos permite identificar con facilidad por dónde han pisado la mayoría de las personas que pasaron por ahí.

La Distribución de Frecuencia es ilustrativa

Podríamos, incluso, trazar una curva estimativa que pase por el centro de cada una de las distribuciones de frecuencia de los diferentes escalones. Esa curva nos daría una estimación de la trayectoria típica que describen las personas que suben esa escalera.

Una cancha embarrada con poco mantenimiento es también una oportunidad para observar un "mapa de calor" de los lugares donde más se juega. Las zonas sin césped tienen la forma de un reloj de arena, se vuelven grandes en las áreas y más delgadas en el centro de la cancha. También los córners tienen menos césped, el punto del centro de la cancha y los puntos de penal.

Visualización de Datos: Pantimedias

La imagen corresponde al envase de unas pantimedias para mujer. Las pantimedias vienen dentro de un paquete cerrado que por lo general, por ser ropa interior, no está permitido abrir para probarse. Por eso mismo dos de los tres gráficos que incluye el paquete están orientados a mostrar cualidades del producto que no pueden ser observados en el envase cerrado. La imagen de la derecha arriba muestra la puntera reforzada, mientras que la de la derecha abajo indica que las medias llegan hasta la cintura.
El mayor de los gráficos, el de la izquierda, es de una índole diferente. Su objetivo es permitirle a la compradora saber qué tamaño de medias le corresponde. El eje de ordenadas (vertical) indica la altura de la persona. El rango de altura que cubre el gráfico va de 145 centímetros a 190 cm. Mientras que en el eje de abscisas se muestra el peso en kilos, donde el rango de peso va de 40 a 100 kilos. Una cualidad interesante del gráfico es que tanto el peso como la altura están en kilos y centímetros como en libras y pulgadas. Eso permite hacer la transformación de un sistema de medidas al otro sin tener que hacer ningún cálculo. Otro aspecto interesante es que este es un gráfico de tres dimensiones exhibido en dos dimensiones. Tenemos la altura, el peso y también el tamaño (S, M, L, XL, XXL) de media asociado a aquellas dos dimensiones. En tres dimensiones el gráfico hubiera resultado mucho más difícil de leer. Cada una de los talles habría sido una columna, en donde la más pequeña habría tenido 1 piso y la más grande 5 pisos. Además, en tres dimensiones el gráfico debería haber sido exhibido desde el ángulo superior izquierdo, de lo contrario la altura de las columnas más altas hubiera impedido ver la altura de las más pequeñas.

La Red de Subte de la Ciudad de Buenos Aires: Distancia entre Nodos y Betweenness Centrality

Distancia entre nodos
La distancia d(u,v) entre nodos en un grafo finito se mide como la longitud mínima de enlaces necesaria para conectar los nodos u y v. Así, por ejemplo, entre la estación de subte Constitución de la línea C y Humberto 1° de la línea H, la distancia mínima es 8 enlaces. La matriz de distancia de la red del subte contiene todas las distancias mínimas entre los distintos nodos de la red. Esa matriz reúne las 5776 combinaciones posibles con los 76 andenes que posee el subte de la Ciudad de Buenos Aires. El menor trayecto posible es 0; eso ocurre cuando medimos la distancia de una estación respecto de sí misma. El trayecto más largo, en esta red, es entre Plaza de los Virreyes y Congreso de Tucumán. Para unir esas dos estaciones es necesario transitar 30 enlaces. Con la información que nos otorga la matriz de distancia podemos generar la distribución de frecuencia de distancia entre nodos. En el siguiente gráfico se enseña esta misma información. En esta red el promedio de enlaces necesarios para unir dos estaciones cualesquiera es 10,79 y el valor que más se repite es 8.

Betweenness Centrality
La betweenness centrality es un instrumento de medición que permite establecer la importancia de cada nodo de la red. La importancia de los nodos se establece en función de las distancias mínimas y la frecuencia en que aparece cada nodo en cada uno de los senderos más cortos. Cuanto mayor es el valor de betweenness centrality asociado a un nodo, mayor será el poder que tendrá para controlar o modificar el mensaje dentro de la red. En el caso del subte de Buenos Aires las estaciones 9 de Julio, Avenida de Mayo y Diagonal Norte tienen los valores más altos de betweenness centrality. Esas estaciones se encuentran, más que ninguna otra, en mayor cantidad de caminos más cortos. Por ejemplo, para ir de Plaza Italia a Entre Ríos, es necesario pasar por alguna de estas 3 estaciones. En cambio las estaciones de los extremos, como son Retiro, Plaza de Mayo, Alem o Plaza de los Virreyes reciben los valores más pequeños. La capacidad que tienen estas últimas estaciones de interrumpir la transmisión de un mensaje es nula. 

Datos
En la tabla se pueden ver las métricas que obtuvieron respecto de PageRank, Betweenness Centrality y Distancia promedio cada uno de los nodos de la red. El PageRank está calculado con una probabilidad de teleportación igual a 0. La distancia promedio indica el promedio de enlaces mínimos necesarios para conectar ese nodo con el resto de los nodos. Y, por último, el Betweenness Centrality está calculado en su forma original.

Powered by Tableau

PageRank: Loops y la Creación de un PageRank Personalizado

Loops

Un posible problema del PageRank son los loops. Por ejemplo, si dos páginas web se linkean entre sí, el algoritmo se quedaría atrapado entre esas dos webs. Cuando ocurre eso el método falla porque no logra distribuir adecuadamente la reputación de esas dos webs al resto de la red. En el trabajo “The PageRank Citation Ranking: Bringing Order to the Web”, Page propone una sencilla solución para este problema. La idea consiste en pensar que nuestro navegante aleatorio cada tanto salta al azar a cualquier otra página de la red. Uno podría imaginarse que el usuario se cansa de dar vueltas entre estos dos sitios que se referencian mutuamente y pasa a visitar otro sitio cualquiera. La solución técnica consiste en distribuir de forma homogénea una porción de la reputación total a cada una de las webs de la red. En concreto, sea u una página web. Luego, definamos a Fu como el conjunto de páginas a las cuales u apunta y a Bu al conjunto de webs que apuntan hacia u. Sea Nu=|Fu| el número de links que salen de u y c el factor de normalización. Entonces el PageRank de cada página web queda definido como:

En donde E(u) es el vector que otorga una fuente inicial de ranking a cada web. Obsérvese que es una función recursiva.

PageRank Personalizado
La solución a los loops abre también una variante para personalizar el PageRank. Si bien uno puede trabajar de manera que a cada web de la red le corresponda la misma cantidad inicial de ranking, esto es alterable. Page indica que originalmente comenzaron a estudiar Internet otorgando a cada sitio un porcentaje inicial ídentico de reputación, independientemente de qué sitio fuera. Por el sólo hecho de existir cada página recibía un:

en el cómputo inicial de su PageRank. Sin embargo, si se modifica el vector E(u) y en vez de distribuir ese 0,15 entre todas las páginas se lo concentra en una sola o en unas pocas, podemos generar un PageRank personalizado que dé más relevancia a ciertas páginas en función de algún criterio que seleccionemos a priori.

PageRank Personalizado aplicado al Subte
Cuando uno realiza una búsqueda en Google.com suele obtener resultados diferentes que cuando la realiza en Google.com.ar. Por ejemplo, los primeros cuatro resultados de búsqueda de la palabra “economía” en Google.com son:

Mientras que los cuatro primeros resultados de Google.com.ar son:

Esto sucede porque Google trabaja con PageRank´s personalizados por países. Google reconoce que cada cultura tiene su propia valoración de los documentos que están en Internet. El idioma, por ejemplo, es una barrera que divide muy marcadamente lo que un argentino mira en Internet de lo que un chino observa. Y eso hace que los chinos enlacen páginas que están escritas en su idioma y los argentinos generen links a páginas que toquen temas de su interés y que estén en castellano. Google trabaja con PageRanks personalizados por países, por idioma, de imágenes, de videos, de libros, de blogs, académicos, etc. Todas esas herramientas trabajan con un ranking personalizado para que la respuesta sea más ajustada a lo que el usuario está interesado en encontrar.

Como decíamos, una forma de lograr la personalización del PageRank es alterando el vector E(u). Imaginemos que en la línea C del subte de la Ciudad de Buenos Aires se habla castellano, mientras que en el resto de las líneas se hablan otros idiomas. Dado que nosotros hablamos en castellano, estamos más interesados en aquello que se haya dicho en ese idioma. Si la red de subte fuera Internet, entonces nuestro buscador personalizado debería priorizar aquellas conversaciones que se hayan dado en la línea C. Para hacer eso alteré el vector E(u) distribuyendo el 0,15 del PageRank inicial sólo entre las 9 estaciones de subte de esa línea. Como se puede observar en la imagen esto provocó que el PageRank se distribuyera más entre los nodos de la línea C y sus adyacentes más cercanos. Esta forma de personalizar el ranking permite agregar mayor valoración a aquello que quien diseña el método quiera priorizar.

Click aqui para ver la imagen más grande (pdf)

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.

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

¿Es posible agotar todo lo que se puede decir en 140 caracteres en Twitter?

En La Biblioteca de Babel, Borges comienza citando esta oración de The Anatomy of Melancholy:

“By this art you may contemplate the variation of the 23 letters…”

La lengua castellana posee 27 letras. Con esas 27 letras podemos formar todas las palabras existentes en castellano y, con menos de eso, también del inglés. Pero para formar una oración requerimos, necesariamente, de los espacios. Si, además, consideramos a las comas, los dos puntos, los guiones, los paréntesis, los corchetes, los signos de admiración y de pregunta, tenemos al menos 35 elementos gráficos para escribir oraciones en castellano y en inglés.

Escribir consiste en ubicar en diferente orden esos 35 elementos. Siendo que son tan pocos los elementos para escribir, uno podría preguntarse si todo lo que se podría decir es finito. Es válido pensar que si los elementos a variar son finitos, entonces el espacio de escritos posibles es, también, finito. ¿Podría ocurrir que ya no quedase nada nuevo por decir? Encontrar una respuesta afirmativa a esa pregunta sin duda produciría una gran tristeza. Ya todo se habría dicho; no habría lugar para nada más.

Lo inmensamente finito, es finito.
¿Se puede agotar el lenguaje? En Twitter uno puede escribir un máximo de 140 caracteres. Digamos que sólo utilizásemos las 27 letras de la lengua castellana más el espacio y los 7 signos de puntuación antes citados. ¿Es posible agotar todos los mensajes posibles de 140 caracteres? ¿Tendría Twitter un final?

Para determinar la cantidad de mensajes posibles deberíamos contar todas las combinaciones que se pueden hacer con esos 35 elementos en 140 espacios. Para el primer lugar podríamos ubicar cualquiera de los 35 elementos, en el segundo lugar también podríamos ubicar cualquiera de los 35 elementos y así seguiríamos hasta el espacio 140. En definitiva hay:

mensajes posibles de escribir en Twitter. Sin duda, muchos de esos mensajes no tendrán ningún significado. Combinaciones como dhcmrlchtdj significarían nada. Otras combinaciones contendrían mensajes para los que hoy no estamos preparados para comprender. Por ejemplo, hace 500 años la palabra Internet habría resultado ininteligible para cualquier persona. Hoy, sin embargo, forma parte de nuestro vocabulario cotidiano. Podríamos pensar que, en principio, ningún mensaje sería rechazable. Aquello que no comprendemos hoy, aún puede tener algún valor.

¿Qué tan grande es el número 35^140? Otra forma de escribir 35^140 es:

1477495640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

En tipografía Arial tamaño 11, escribirlo –sin pasar a otro renglón- nos demandaría casi 45 centímetros. Más o menos 2 veces el largo de un tallarín. Resulta difícil percibir la dimensión de un número tan grande. Pero, cuando lo comparamos con otras medidas, aparece una revelación.

Según Twitter se escriben aproximadamente 200 millones de tuits diarios. A ese ritmo, este año se habrán escrito cerca de 73.000.000.000 tuits. Entonces, ¿en cuántos años los usuarios de Twitter agotarán todo lo que se puede escribir en 140 caracteres? Por un momento imaginemos que los 73.000.000.000 mensajes que se escribirían en un año en Twitter fuesen todos diferentes. Entonces, si dividimos la cantidad de mensajes posibles por la cantidad de mensajes diferentes que se escriben en el año, tendremos la cantidad de años necesarios para escribir todo lo que se pueda realizar en 140 espacios con 35 caracteres. Concretamente eso es otro número inmenso:

La Edad del Universo

Posiblemente el tiempo más largo que uno se pudiera imaginar sea la edad del Universo. La edad del universo se cuenta desde el comienzo del Big Bang hasta el presente. Las observaciones astronómicas y los modelos matemáticos indican que el cosmos existe desde hace 13,75 miles de millones de años. Si bien el número es muy grande, resulta asombroso encontrarnos con que, al ritmo en que hoy se escribe en Twitter, requeriríamos de

veces el tiempo que pasó desde que nació el universo hasta ahora para agotar todo el espectro de creaciones posibles que ofrecen 35 caracteres y 140 espacios. Ni con todo el tiempo existente los usuarios de Twitter podrían haber agotado el pequeño univserso que tienen delante.

Links:
The Anatomy of Melancholy
http://en.wikipedia.org/wiki/The_Anatomy_of_Melancholy
Twitter - 200 mlls de tuits diarios
http://blog.twitter.com/2011/06/200-million-tweets-per-day.html
La Edad del Universo - Wikipedia
http://en.wikipedia.org/wiki/Age_of_the_universe#cite_note-0