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

  • Descubren un helecho tropical que transforma sus hojas muertas en nuevas raíces 9 febrero, 2024
    Para sobrevivir en el suelo anegado y bajo en nutrientes del bosque de Quebrada Chorro, en el oeste de Panamá, una especie de helecho tropical arborescente reutiliza sus hojas muertas, convirtiéndolas en nuevas raíces. Los científicos descubrieron que el helecho reconfigura estas “hojas zombis”, invirtiendo el flujo de agua para atraer nutrientes de regreso a […]
    Pablo Javier Piacente
  • Descubren una extraña combinación de minerales en las muestras lunares de la misión Chang'e-5 de China 9 febrero, 2024
    Los minerales antiguos y nuevos identificados en las muestras lunares traídas por la misión Chang'e-5 de China están ayudando a los científicos a comprender mejor la historia de la Luna: ahora, los especialistas han descubierto más propiedades del sexto nuevo mineral lunar, llamado Changesite-(Y). Además, otros compuestos hallados, la seifertita y la stishovita, pueden coexistir […]
    Pablo Javier Piacente
  • Los robots que atienden a pacientes llegan a los hospitales 9 febrero, 2024
    Robots diseñados para brindar comodidad a los pacientes de edad avanzada y aliviar su ansiedad, han sido probados con éxito en un hospital de París: saludan, responden a preguntas, comprenden conversaciones grupales y apoyan las tareas de enfermería.
    Redacción T21
  • Una pequeña luna de Saturno parecida a la “Estrella de la Muerte” de Star Wars contiene un océano oculto 8 febrero, 2024
    Por debajo de la superficie repleta de cráteres de Mimas, una de las lunas más pequeñas de Saturno, se esconde un océano global de agua líquida de reciente formación. El satélite posee tan sólo unos 400 kilómetros de diámetro y presenta un notable parecido con la “Estrella de la Muerte”, una estación espacial imperial que […]
    Pablo Javier Piacente
  • Logran controlar un objeto virtual con la mente durante un sueño lúcido 8 febrero, 2024
    Un grupo de participantes en un nuevo estudio científico logró manejar un vehículo virtual a través de un avatar únicamente con su mente, mientras sus cerebros permanecían en la fase REM del sueño. Además de profundizar en los misterios de la consciencia humana, la innovación podría facilitar el acceso a nuevos desarrollos tecnológicos, como un […]
    Pablo Javier Piacente
  • Un proyecto global trabaja para crear de forma colaborativa un cerebro robótico general 8 febrero, 2024
    El auge de la inteligencia artificial generativa impulsa un proyecto global que trabaja para crear un cerebro robótico general, capaz de generar androides como los que hemos visto hasta ahora solo en la ciencia ficción. Pero es cuestión de tiempo que convivamos con ellos en perfecta armonía. Ya no es una utopía.
    Eduardo Martínez de la Fe
  • La IA está capacitada para resolver dilemas morales cuando conduce vehículos autónomos 8 febrero, 2024
    Los sistemas de IA muestran significativas similitudes éticas con las reacciones humanas ante dilemas morales, lo que los acreditan para conducir vehículos autónomos tal como lo harían las personas.
    Redacción T21
  • Los huracanes se están volviendo tan fuertes que ya no existen categorías para clasificarlos 7 febrero, 2024
    Cinco tormentas en la última década tuvieron velocidades de viento que pertenecen a una hipotética categoría 6 en la escala de huracanes Saffir-Simpson: el fenómeno obligaría a los científicos a crear una nueva clasificación, capaz de reflejar la virulencia de los huracanes en la actualidad. Las causas principales del fenómeno tienen su origen en el […]
    Pablo Javier Piacente
  • Un asteroide habría explotado sobre la Antártida hace unos 2,5 millones de años 7 febrero, 2024
    Un asteroide se desintegró sobre el continente antártico hace aproximadamente 2,5 millones de años: la evidencia proviene de un análisis químico de más de 100 pequeños trozos de roca extraterrestre, que se han preservado dentro de las enormes capas de hielo. Hasta el momento, solo se conocen otros dos eventos de explosiones aéreas antiguas en […]
    Pablo Javier Piacente
  • Crean la primera niña de inteligencia artificial del mundo 7 febrero, 2024
    La primera niña IA del mundo ha sido creada por científicos chinos, que la han dotado de emociones e intelecto y de la capacidad de aprender de forma autónoma. Se comporta como si tuviera tres o cuatro años y representa un avance significativo para el campo de la inteligencia artificial general.
    Redacción T21