Explorando redes de forma eficiente

Las hormigas estiman muy bien la concentración de otras hormigas en sus proximidades. Esta capacidad parece desempeñar un papel en varias actividades comunitarias, en particular en el procedimiento de votación mediante el cual una colonia de hormigas selecciona un nuevo nido.

Los biólogos sospechan desde hace mucho tiempo que las hormigas basan sus estimaciones de densidad de población en la frecuencia con la que -literalmente- chocan con otras hormigas mientras exploran al azar sus entornos.

Esa teoría tiene nuevo apoyo de un artículo teórico que investigadores de Ciencias de la Computación y del Laboratorio de Inteligencia Artificial del Massachusetts Institute of Technology (MIT, Boston, EE.UU.) presentarán en el Simposio de la Asociación de Maquinaria de Computación este mes. El artículo muestra que las observaciones de la exploración aleatoria del entorno convergen muy rápidamente en una estimación precisa de la densidad de población. De hecho, convergen tan rápidamente como es teóricamente posible.

Más allá de ofrecer apoyo a las suposiciones de los biólogos, este marco teórico también se aplica al análisis de redes sociales, de la toma de decisiones colectivas en los enjambres de robots y de la comunicación en las redes ad hoc inalámbricas, que son descentralizadas.

"Es intuitivo que si un grupo de personas está caminando al azar alrededor de un área, el número de veces que chocan entre sí será un sustituto de la densidad de población", dice Cameron Musco, estudiante de posgrado de MIT en ingeniería eléctrica y ciencias de la computación y co-autor del nuevo artículo, en MIT News. "Lo que estamos haciendo es dar un análisis riguroso que sostenga esa intuición, y también decir que la estimación es una estimación muy buena. Como función del tiempo, se vuelve más y más precisa, y va casi tan rápido como es posible".

Caminos aleatorios

Musco y sus coautores caracterizan el ambiente de una hormiga como una cuadrícula, con varias otras hormigas esparcidas al azar a través de ella. La hormiga estudiada -la "explorador"- comienza en una célula de la red y, con la misma probabilidad para cada una, se traslada a una de las celdas adyacentes.

Luego, con la misma probabilidad, se mueve a una de las células adyacentes, y así sucesivamente. En las estadísticas, esto se conoce como "paseo aleatorio". El explorador cuenta el número de hormigas que habitan en cada célula que visita.

En su artículo, los investigadores comparan el paseo aleatorio con un muestreo aleatorio, en el que se seleccionan células de la red al azar y se cuentan el número de hormigas. La precisión de ambos enfoques mejora con cada muestra adicional, pero notablemente, el paseo aleatorio converge en la verdadera densidad de población casi tan rápidamente como lo hace un muestreo aleatorio.

Eso es importante porque en muchos casos prácticos, el muestreo aleatorio no es una opción. Supongamos, por ejemplo, que desea escribir un algoritmo para analizar una red social en línea: por ejemplo, para estimar qué fracción de la red se auto-describe como de un partido político. No hay ninguna lista pública de los miembros de la red; la única manera de explorarla es escoger un miembro individual y empezar a trazar conexiones.

Del mismo modo, en redes ad hoc, un dispositivo dado sólo conoce la ubicación de los dispositivos en sus inmediaciones; no conoce la disposición de la red en su conjunto. Un algoritmo que utilice paseos aleatorios para agregar información desde múltiples dispositivos sería mucho más fácil de implementar que uno que ha de caracterizar la red en su conjunto.

Repeticiones

Esta consecuencia es sorprendente porque, en cada paso de un camino aleatorio, el explorador tiene una alta probabilidad de volver a una célula que ya ha visitado. Una estimación derivada de paseos aleatorios tiene así una probabilidad mucho mayor de sobremuestreo de células particulares que uno basado en un muestreo aleatorio.

Inicialmente, dice Musco, él y sus colegas asumieron que se trataba de un problema que un algoritmo para la estimación de la densidad de población tendría que superar. Sin embargo, sus intentos de filtrar los datos de estos sobremuestreos parecían empeorar el rendimiento de su algoritmo en lugar de mejorarlo. En última instancia, fueron capaces de explicar por qué, en teoría.

"Si estás caminando al azar alrededor de una rejilla, no vas a topar con todo el mundo, porque no vas a cruzar toda la red", dice Musco. "Así que hay alguien al otro extremo de la rejilla con el que tienes más o menos una probabilidad del cero por ciento de toparte. Pero mientras me toparé con esos tipos menos, tropezaré más con los que están cerca. Necesito contar todos mis interacciones con los cercanos para compensar el hecho de que existen estos tipos lejanos con los que nunca voy a chocar. De alguna manera se equilibra perfectamente. Es muy fácil demostrarlo, pero no es muy intuitivo, por lo que nos llevó un tiempo darnos cuenta de esto."

Cuadrícula

La cuadrícula que los investigadores utilizaron para modelar el entorno de las hormigas es sólo un caso especial de una estructura de datos llamada grafo. Un grafo consta de nodos, normalmente representados por círculos, y bordes, por lo general representados por segmentos de línea que conectan los nodos. En la cuadrícula, cada célula es un nodo, y comparte bordes sólo con aquellas células inmediatamente adyacentes a ella.

Las técnicas de análisis de los investigadores, sin embargo, se aplican a cualquier grafo, tales como una descripción de qué miembros de una red social están conectados o qué dispositivos de una red ad hoc se encuentran dentro del alcance de comunicación los unos de los otros.

Si el grafo no está muy bien conectado -si, por ejemplo, es sólo una cadena de nodos, cada uno conectado sólo a los dos nodos adyacentes a él- el sobremuestreo puede convertirse en un problema. En una cadena de, por ejemplo, 100 nodos, un explorador que de un paseo aleatorio podría atascarse atravesando los mismos cinco o seis nodos una y otra vez.

Pero siempre y cuando sea probable que dos paseos al azar a partir del mismo nodo se ramifiquen en diferentes direcciones, como suele ser el caso en los grafos que describen las redes de comunicaciones, los paseos aleatorios siguen siendo prácticamente tan buenos como el muestreo aleatorio.

Por otra parte, en el artículo, los investigadores analizan paseos aleatorios ejecutados por un único explorador. La puesta en común de las observaciones de muchos exploradores convergerían en una estimación precisa con mayor rapidez. "Si fueran robots en lugar de hormigas, podrían obtener mejor resultado compartiendo sus datos", señala Musco.

"La gente siempre debate si las hormigas o las abejas pueden reconocer a otros individuos", explica Anna Dornhaus, profesora de ecología y biología evolutiva en la Universidad de Arizona, que estudia insectos sociales. "Este trabajo muestra que, al menos, en este contexto, no es necesario. Para mí, ese es el principal resultado sorprendente aquí, aparte de la cuestión matemática".

Tráfico

Un estudio realizado el año pasado en la Universidad de Halle-Wittenberg (Alemania) demostró que los insectos pequeños auto-organizan el tráfico en sus senderos para dar cabida a un mayor número de ellos y una mayor velocidad.

En lugar de disminuir la velocidad, las hormigas aceleran en respuesta a una mayor densidad de tráfico en sus caminos. Cuando los investigadores aumentaron el suministro de alimentos dejanndo comida al lado de la pista, las hormigas aceleraron su velocidad en un 50 por ciento.

Esto a pesar de tener una densidad de tráfico de más del doble: cuando el tráfico es bajo o medio, prefieren las vías centrales; cuando el tráfico es denso, se dirigen a las periféricas.

Asimismo, un modelo computacional realizado en la Universidad Estatal de Arizona (EE.UU.) ha permitido determinar cómo se organizan jerárquicamente las hormigas, a partir de su comportamiento. Morderse, vigilar o los duelos sin ganador determinan aspectos como si las hormigas tienen dominancia compartida o individual o si son despóticas.