Investigadores de la la Universidad Carlos III de Madrid
(UC3M) han desarrollado un algoritmo para acelerar las búsquedas de
caminos entre dos nodos dentro de una red social. El algoritmo se basa
en el comportamiento que siguen las hormigas mientras buscan comida.
Una de las principales cuestiones técnicas en el ámbito de las redes
sociales, cuyo uso cada vez está más generalizado, consiste en localizar
la cadena de referencia que lleva de una persona a otra, de un nodo a
otro. El mayor reto que se plantea en este ámbito es el enorme tamaño de
estas redes y que la respuesta debe ser rápida, dado que el usuario
final espera resultados en el menor tiempo posible.
Para solucionar este problema, investigadores de la Universidad Carlos III de Madrid (UC3M) han desarrollado el algoritmo SoSACO, que acelera la búsqueda de caminos entre dos nodos pertenecientes al grafo que representa a una red social.
El
funcionamiento de SoSACO se inspira en el comportamiento que ha
perfeccionado a lo largo de miles de años uno de los insectos más
disciplinados del planeta a la hora de buscar comida, las hormigas. En
general, los algoritmos de las colonias imitan cómo estos insectos son
capaces de encontrar el camino entre el hormiguero y la fuente de
alimento mediante la deposición y seguimiento de un rastro químico
depositado en el suelo, denominado feromona.
“En este estudio
–explican sus autores– se incorporan además otros rastros olorosos para
que las hormigas puedan seguir tanto la feromona como el aroma de la
comida, con lo que consiguen encontrar la fuente de alimento de forma
mucho más rápida”. Los principales resultados de esta investigación,
realizada por Jessica Rivero en el marco de su tesis doctoral en el
Laboratorio de Bases de Datos Avanzadas (LABDA) de la UC3M, se resumen en un artículo científico publicado en la revista Applied Intelligence.
“Los
primeros resultados muestran que la aplicación del algoritmo a redes
sociales reales consigue obtener una respuesta óptima en muy poco tiempo
(decenas de milisegundos)”, indica Jessica Rivero.
Múltiples aplicaciones
Gracias
a este nuevo algoritmo de búsqueda, el sistema puede encontrar estos
caminos más fácilmente y sin necesidad de modificar la estructura de un
grafo (una imagen que representa mediante nodos y enlaces las relaciones
entre un conjunto de elementos). “Este avance permite resolver gran
cantidad de problemas que encontramos en el mundo real, ya que los
escenarios sobre los que ocurren se pueden modelar mediante un grafo”,
explican los investigadores.
De esta manera, podría encontrar
aplicación en muchos escenarios, como para mejorar la localización de la
ruta en los sistemas GPS o los juegos on line, para la
planificación del reparto de los camiones de mercancías, para saber si
dos palabras guardan algún tipo de relación o simplemente para conocer
con más exactitud las afinidades que tengan en común dos usuarios de
Facebook o Twitter, por ejemplo.
Esta investigación, que ha
contado con el apoyo de la Comunidad de Madrid y el Ministerio de
Educación y Ciencia, surgió dentro del proyecto SOPAT ante la necesidad
de guiar a los clientes de un hotel empleando un sistema de interacción
natural. Esta tesis, titulada Búsqueda Rápida de Caminos en Grafos de Alta Cardinalidad Estáticos y Dinámicos, ha sido dirigida por los profesores de LABDA del Departamento de Informática Fco. Javier Calle y Mª Dolores Cuadra.
Referencia bibliográfica:
Rivero, J (Rivero, Jessica); Cuadra, D (Cuadra, Dolores); Calle, J (Calle, Javier); Isasi, P (Isasi, Pedro). "Using the ACO algorithm for path searches in social networks". APPLIED INTELLIGENCE 36 (4): 899-917, junio de 2012. ISSN: 0924-669X
Fuente:
http://www.agenciasinc.es/Noticias/Las-hormigas-inspiran-un-buscador-para-redes-sociales
No hay comentarios:
Publicar un comentario