Un algoritmo para descubrir el origen de epidemias o el ataque a las Torres Gemelas

En los tres casos existe una red en la que los pueblos infectados, los amigos de Facebook o los terroristas de Al Qaeda son los nodos y un flujo de información en forma de contagio, comentarios y comunicaciones. Teniendo controlados a unos pocos nodos de esas redes, un algoritmo puede determinar dónde o quién empezó todo.

Tres investigadores de la Ecole Polytechnique Fédérale de Lausanne (EPFL) han creado el algoritmo SparseInf con el que intentan inferir la localización de una fuente partiendo del control de unos pocos y dispersos (sparse, en inglés) nodos. Conociendo, al menos parcialmente, la topografía de una red compleja, el sentido de la circulación de la información y el momento en que los dos o tres nodos convertidos en sensor u observador la reciben, SparseInf llega al momento y fuente original con un alto grado de acierto.

Como los móviles
Pedro Pinto, principal autor del algoritmo y de la investigación que publica hoy la revista Physical Review Letters, explica su funcionamiento básico sin recurrir a complicadas ecuaciones matemáticas. ”El algoritmo es similar al sistema para la localización de los móviles. Si tu móvil se encuentra a 100 metros de la antena 1, a 200 metros de la antena 2 y 300 metros de la antena 3, podemos dibujar tres grandes círculos. El punto de intersección de los tres se corresponde con la ubicación de tu móvil, es lo que se llama triangulación”, explica. En SparseInf usan el mismo principio, pero aplicado a otro tipo de redes.

Una de ellas es la de los 64 terroristas y sus colaboradores que participaron en los atentados del 11 de septiembre de 2001. Con la información obtenida de los periódicos, los investigadores pudieron dibujar la estructura de la red. “En la gráfica de los terroristas, una conexión entre el terrorista A y el terrorista significa que A se ha comunicado con B”, concreta Pinto. Usando a dos nodos dispersos (Alnami y Zubeida,ver gráfico) pudieron determinar la centralidad de Mohamed Atta en el ataque basándose en cuándo y desde quién recibieron los mensajes los dos observadores.

¿Significa esto que si se hubiera estado vigilando las comunicaciones de al menos dos de los terroristas y se hubiera aplicado SparseInf, se habrían podido evitar los atentados? “Nuestro algoritmo podría haber ayudado sin duda a entender mejor la situación, pero yo no iría tan lejos como para afirmar que podría haberlo evitado. Todavía estamos lejos de eso”, aclara Pinto. Su algoritmo funciona bien con epidemias y contaminaciones pero tiene que ser mejorado cuando se enfrenta a una red terrorista. “Necesita conocer la estructura de la red, quién está conectado a quién y esto es difícil de determinar en el caso de los terroristas”, añade.

Mitigación de epidemias
Pero en la epidemia de cólera desatada en la provincia sudafricana de KwaZulu-Natal en 2000, los investigadores contaban con los datos de cada caso (tiempo y lugar). En esta red, los nodos eran los pueblos y sus fuentes de agua donde la bacteria podía medrar. Con controlar sólo el 20% de las comunidades, lograron determinar el origen de la epidemia y el primer pueblo infectado con un margen de error muy reducido. “Este pequeño error en la distancia podría permitir una reacción más rápida de las autoridades para frenar el brote”, escriben en el informe.

Aunque Pinto sostiene que hay que seguir perfeccionándolos, cree que “en el futuro este tipo de algoritmos que hemos presentado pueden ser de una importancia vital para ayudar a las agencias de seguridad públicas a limitar y contener contaminaciones y ataques”.

Posibles usos

El algoritmo creado por los investigadores de la EPFL puede usarse en diferentes redes complejas, desde las biológicas hasta las sociales, pasando por las tecnológicas. La moderna teoría de redes sostiene que, independientemente de su tipo, todas estas redes comparten una serie de elementos comunes.

En el terreno de las redes sociales humanas, SparseInf podría localizar el origen de un rumor en Facebook, por ejemplo, que ha llegado a 500 personas, amigos e incluso amigos de amigos. ¿Cómo encontrar al que inició la cadena? “Controlando los mensajes recibidos sólo por 15 de tus amigos y teniendo en cuenta el factor tiempo, nuestro algoritmo puede rastrear la ruta de la información y enconttrar la fuente”, asegura Pedro Pinto. Pero el autor de la investigación insiste aquí que lo difícil es saber la velocidad de propagación del rumor, elemento clave para ajustar el resultado.

Pero ese parámetro puede ser mejor controlado en sistemas artificiales como internet o la red eléctrica. SparseInf podría servir para detectar el origen de un virus informático o el emisor de una cadena de spam o el punto donde se ha producido un fallo eléctrico.

En su investigación también aseguran poder localizar la fuente de una contaminación en las redes de infraestructuras. Por ejemplo, en 1998, la principal red de suministro de agua potable se contaminó por un parásito microscópico, obligando a las autoridades a alertar a tres millones de personas. Otro de los casos que incluyen en su trabajo fue el ataque con gas sarín en el metro de Tokio en 1995. Los investigadores modelaron un escenario similar en el metro de Nueva York. SparseInf les desveló que bastaría colocar sensores en el 20% de las estaciones para determinar donde se originó el supuesto ataque.


Informe completo: 'Locating the Source of Diffusion in Large-Scale Networks', by P. Pinto, P. Thiran, and M. Vetterli, 'Physical Review Letters', Aug. 2012

Publicado por Materia (republicado bajo licencia CC)