Conéctese Regístrate


27/11/2014

Tendencias 21
25 Aniversario




Un nuevo buscador acelera el descubrimiento de afinidades en las redes sociales

Un algortimo basado en el comportamiento de las hormigas establece relaciones en decenas de milisegundos


Un algoritmo inspirado en el comportamiento de las hormigas mientras buscan comida permite conocer las afinidades que tengan en común dos usuarios de Facebook o Twitter en decenas de milisegundos. El algoritmo se puede aplicar también para 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 o para saber si dos palabras guardan algún tipo de relación.




El algoritmo busca el camino entre dos nodos del grafo. Imagen: UC3M.
El algoritmo busca el camino entre dos nodos del grafo. Imagen: UC3M.
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

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

Lunes, 4 de Junio 2012
UC3M/T21
Artículo leído 39979 veces




Nota


Comente este artículo

1.Publicado por missy adedla el 05/06/2012 19:49
Este articulo esta muy interesante tienen que verlo.

2.Publicado por sara el 13/12/2012 02:10
thai dating sites I recently came across your blog and have been reading along. I thought I would leave my first comment. I don’t know what to say except that I have enjoyed reading. Nice blog. I will keep visiting this blog very often.

Nuevo comentario:
Twitter

Los comentarios tienen la finalidad de difundir las opiniones que le merecen a nuestros lectores los contenidos que publicamos. Sin embargo, no está permitido verter comentarios contrarios a las leyes españolas o internacionales, así como tampoco insultos y descalificaciones de otras opiniones. Tendencias21 se reserva el derecho a eliminar los comentarios que considere no se ajustan al tema de cada artículo o que no respeten las normas de uso. Los comentarios a los artículos publicados son responsabilidad exclusiva de sus autores. Tendencias21 no asume ninguna responsabilidad sobre ellos. Los comentarios no se publican inmediatamente, sino que son editados por nuestra Redacción. Tendencias21 podrá hacer uso de los comentarios vertidos por sus lectores para ampliar debates en otros foros de discusión y otras publicaciones.

Otros artículos de esta misma sección
< >



Forma parte de nuestra comunidad y contribuye al desarrollo e independencia de los contenidos de Tendencias21. Opta a becas.