La teoría de los «seis grados de separación» aseguraba que todas las personas del mundo estaban conectadas entre sí por, como máximo, ese número de pasos. Uno conoce a otro, que a su vez conoce a un tercero, y así hasta conectar a dos humanos cualquiera. No está demostrada, pero pone de manifiesto los problemas matemáticos que lidian con estos caminos de relaciones —grafos—. Además de encontrar la ruta más corta entre dos puntos, la búsqueda de ésta tiene que ser rápida.
Las colonias de hormigas han desarrollado estrategias muy eficientes para establecer rutas entre el hormiguero y alguna fuente de comida. Cada uno de estos artrópodos deja un rastro químico de feromonas allá por donde pasa. Esta sustancia se evapora con el tiempo, por lo que está más presente en los caminos más cortos, que son los que aprovechan la mayoría de hormigas, reforzando el efecto. Esta misma estrategia es la que han utilizado un grupo de investigadores de la Universidad Carlos III y la han aplicado a redes sociales.
«El rastro químico es más fuerte en el camino más corto», afirma Jessica Rivero, principal desarrolladora del algoritmo, al que ha bautizado SoSACO. «Es una versión del algoritmo ACO (Ant Colony Optimization) ampliada», explica. Aunque la técnica de usar los métodos de las hormigas ya era conocida, su propia aproximación, asegura, permite su utilización en redes más grandes, con muchos más nodos.
Una posible aplicación de su algoritmo podría estar en los GPS. «Cuando en un camino de hormigas pones una piedra encuentran rápidamente uno alternativo, y a veces es aún más corto», dice Rivero. Algo equivalente se podría aplicar para evitar los atascos y ofrecer alternativas optimizadas, explica.
Para poner a prueba su efectividad han probado SoSACO con las redes sociales a las que han tenido acceso. Entre ellas, Slashdot, que en el momento del estudio tenía «en torno a 86.000 usuarios». Rivero afirma que les habría gustado trabajar con alguna más grande, como Twitter o Facebook, pero son cerradas y no tuvieron acceso. En cualquier caso, afirma, «Los primeros resultados muestran que la aplicación del algorito a redes sociales reales consigue obtener una respuesta óptima en muy poco tiempo (decenas de milisegundos).
La investigación, enmarcada dentro de la tesis doctoral de Jessica Rivero, se ha realizado en el Laboratorio de Bases de Datos Avanzadas (LABDA) de la Universidad Carlos III y se ha publicado en un artículo en la revista Applied Intelligence.
sábado, junio 16, 2012
Las hormigas inspiran un algoritmo para búsquedas en redes sociales
Investigadores de la Universidad Carlos III de Madrid han desarrollado SoSACO, un modelo matemático que optimiza la búsqueda de rutas entre dos nodos de una red
La teoría de los «seis grados de separación» aseguraba que todas las personas del mundo estaban conectadas entre sí por, como máximo, ese número de pasos. Uno conoce a otro, que a su vez conoce a un tercero, y así hasta conectar a dos humanos cualquiera. No está demostrada, pero pone de manifiesto los problemas matemáticos que lidian con estos caminos de relaciones —grafos—. Además de encontrar la ruta más corta entre dos puntos, la búsqueda de ésta tiene que ser rápida.
Las colonias de hormigas han desarrollado estrategias muy eficientes para establecer rutas entre el hormiguero y alguna fuente de comida. Cada uno de estos artrópodos deja un rastro químico de feromonas allá por donde pasa. Esta sustancia se evapora con el tiempo, por lo que está más presente en los caminos más cortos, que son los que aprovechan la mayoría de hormigas, reforzando el efecto. Esta misma estrategia es la que han utilizado un grupo de investigadores de la Universidad Carlos III y la han aplicado a redes sociales.
«El rastro químico es más fuerte en el camino más corto», afirma Jessica Rivero, principal desarrolladora del algoritmo, al que ha bautizado SoSACO. «Es una versión del algoritmo ACO (Ant Colony Optimization) ampliada», explica. Aunque la técnica de usar los métodos de las hormigas ya era conocida, su propia aproximación, asegura, permite su utilización en redes más grandes, con muchos más nodos.
Una posible aplicación de su algoritmo podría estar en los GPS. «Cuando en un camino de hormigas pones una piedra encuentran rápidamente uno alternativo, y a veces es aún más corto», dice Rivero. Algo equivalente se podría aplicar para evitar los atascos y ofrecer alternativas optimizadas, explica.
Para poner a prueba su efectividad han probado SoSACO con las redes sociales a las que han tenido acceso. Entre ellas, Slashdot, que en el momento del estudio tenía «en torno a 86.000 usuarios». Rivero afirma que les habría gustado trabajar con alguna más grande, como Twitter o Facebook, pero son cerradas y no tuvieron acceso. En cualquier caso, afirma, «Los primeros resultados muestran que la aplicación del algorito a redes sociales reales consigue obtener una respuesta óptima en muy poco tiempo (decenas de milisegundos).
La investigación, enmarcada dentro de la tesis doctoral de Jessica Rivero, se ha realizado en el Laboratorio de Bases de Datos Avanzadas (LABDA) de la Universidad Carlos III y se ha publicado en un artículo en la revista Applied Intelligence.
La teoría de los «seis grados de separación» aseguraba que todas las personas del mundo estaban conectadas entre sí por, como máximo, ese número de pasos. Uno conoce a otro, que a su vez conoce a un tercero, y así hasta conectar a dos humanos cualquiera. No está demostrada, pero pone de manifiesto los problemas matemáticos que lidian con estos caminos de relaciones —grafos—. Además de encontrar la ruta más corta entre dos puntos, la búsqueda de ésta tiene que ser rápida.
Las colonias de hormigas han desarrollado estrategias muy eficientes para establecer rutas entre el hormiguero y alguna fuente de comida. Cada uno de estos artrópodos deja un rastro químico de feromonas allá por donde pasa. Esta sustancia se evapora con el tiempo, por lo que está más presente en los caminos más cortos, que son los que aprovechan la mayoría de hormigas, reforzando el efecto. Esta misma estrategia es la que han utilizado un grupo de investigadores de la Universidad Carlos III y la han aplicado a redes sociales.
«El rastro químico es más fuerte en el camino más corto», afirma Jessica Rivero, principal desarrolladora del algoritmo, al que ha bautizado SoSACO. «Es una versión del algoritmo ACO (Ant Colony Optimization) ampliada», explica. Aunque la técnica de usar los métodos de las hormigas ya era conocida, su propia aproximación, asegura, permite su utilización en redes más grandes, con muchos más nodos.
Una posible aplicación de su algoritmo podría estar en los GPS. «Cuando en un camino de hormigas pones una piedra encuentran rápidamente uno alternativo, y a veces es aún más corto», dice Rivero. Algo equivalente se podría aplicar para evitar los atascos y ofrecer alternativas optimizadas, explica.
Para poner a prueba su efectividad han probado SoSACO con las redes sociales a las que han tenido acceso. Entre ellas, Slashdot, que en el momento del estudio tenía «en torno a 86.000 usuarios». Rivero afirma que les habría gustado trabajar con alguna más grande, como Twitter o Facebook, pero son cerradas y no tuvieron acceso. En cualquier caso, afirma, «Los primeros resultados muestran que la aplicación del algorito a redes sociales reales consigue obtener una respuesta óptima en muy poco tiempo (decenas de milisegundos).
La investigación, enmarcada dentro de la tesis doctoral de Jessica Rivero, se ha realizado en el Laboratorio de Bases de Datos Avanzadas (LABDA) de la Universidad Carlos III y se ha publicado en un artículo en la revista Applied Intelligence.
Suscribirse a:
Enviar comentarios (Atom)
No hay comentarios:
Publicar un comentario