Tendencias21

Explorando redes de forma eficiente

Las hormigas deducen la densidad de población que hay a su alrededor a partir del número de encuentros con otros individuos, en sus paseos aleatorios por el entorno. Científicos de MIT han demostrado matemáticamente que este método es tan bueno como el mejor, y que el dato podría usarse para analizar y mejorar las redes sociales y de comunicaciones. Por Carlos Gómez Abajo.

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.

RedacciónT21

Hacer un comentario

RSS Lo último de Tendencias21

  • La evolución no sería exclusiva de los seres vivos: afecta también a los minerales 4 noviembre, 2024
    Cualquier sistema está sujeto a procesos evolutivos siguiendo un supuesto principio fundamental que impulsa el aumento de la complejidad en cualquier sistemas físico, no solo en la biología. Una propuesta que ya encuentra aplicaciones en la oncología, ecología microbiana o en las ciencias de la computación.
    Redacción T21
  • Las hormigas invasoras hacen autostop para encontrar un nuevo hogar 3 noviembre, 2024
    Se sabe que los insectos son especialistas en utilizar todo tipo de formas de transporte para atravesar amplias distancias, pero un nuevo estudio ha revelado que las hormigas también dominan el autostop: estos insectos sociales recogen a toda la familia, incluida su reina, y se suben al primer vehículo que encuentran para emprender un viaje […]
    Pablo Javier Piacente
  • La electricidad podría producir oro 2 noviembre, 2024
    Un nuevo estudio sugiere que la formación de pepitas de oro podría ser impulsada por un fenómeno eléctrico único: la piezoelectricidad es un proceso que resulta de la polarización eléctrica que ocurre dentro de sustancias, incluidos cristales como el cuarzo, cuando se colocan bajo tensión mecánica. Esto explicaría la formación de enormes pepitas de oro […]
    Pablo Javier Piacente
  • La vida extraterrestre podría prosperar sin necesidad de un planeta que la cobije 1 noviembre, 2024
    Los investigadores sostienen que las condiciones de soporte vital creadas únicamente por estructuras biológicas podrían de hecho existir, haciendo completamente posible que algunas formas de vida prosperen en hábitats espaciales muy diferentes a los existentes en la Tierra. Incluso, podrían existir civilizaciones extraterrestres en hábitats autosustentables vagando en el espacio, sin necesidad de contar con […]
    Pablo Javier Piacente
  • Un nuevo tratamiento para eliminar residuos cerebrales podría extender la vida humana 1 noviembre, 2024
    La prevención de la acumulación de F-actina en el envejecimiento de las moscas de la fruta, a través de la modificación de genes específicos, optimizó el reciclaje celular, disminuyó la acumulación de desechos cerebrales y prolongó su vida útil saludable en aproximadamente un 30 %, según un nuevo estudio. El hallazgo podría propiciar el futuro […]
    Pablo Javier Piacente
  • La IA puede procesar ilusiones ópticas como lo hace el cerebro humano 1 noviembre, 2024
    Un nuevo sistema de inteligencia artificial (IA) puede imitar por primera vez cómo las personas interpretan ilusiones ópticas complejas, gracias al gato de Schrödinger. Un impulso a la visión artificial, la seguridad aérea y la navegación espacial.
    Eduardo Martínez de la Fe
  • Objetos desconocidos podrían existir en los confines del Sistema Solar 31 octubre, 2024
    Una serie de observaciones realizadas con el Telescopio Subaru han permitido descubrir nuevos objetos en el Sistema Solar exterior, sugiriendo la existencia de una población de cuerpos más grande y no identificada hasta el momento más allá del Cinturón de Kuiper. El hallazgo de los misteriosos 11 objetos se concretó en el marco de la […]
    Pablo Javier Piacente
  • Un implante ocular logra restaurar la visión de pacientes ciegos 31 octubre, 2024
    Una startup biotecnológica anunció que ha desarrollado una interfaz cerebro-ordenador que puede ayudar a los pacientes con pérdida severa de la visión: mediante un implante ocular conectado al sistema, lograron restaurar la capacidad de leer con fluidez y reconocer rostros en personas ciegas. Es un gran avance contra la degeneración macular relacionada con la edad, […]
    Pablo Javier Piacente
  • El cambio climático amenaza con una futura hambruna global 31 octubre, 2024
    El calentamiento global no solo está disparado, sino que pone en peligro la vida de millones de personas en todo el mundo. También está provocando una disminución de la productividad agrícola que podría llevar a una escasez de alimentos y a un aumento de la desnutrición a nivel global.
    Redacción T21
  • La lluvia colabora con el océano para atrapar más carbono 30 octubre, 2024
    Hasta el momento, la lluvia ha sido ignorada en los cálculos de la capacidad del océano para absorber dióxido de carbono (CO2), pero una nueva estimación indica que las precipitaciones mejoran la capacidad del océano para atrapar las emisiones entre un 5 % y un 7 %, cumpliendo un papel vital en el ambiente. Este […]
    Pablo Javier Piacente