NOTICIAS

La mejor forma de explorar una red es…

Aleida Rueda
25/oct/2012

El sistema de energía eléctrica, el metro, Facebook, el sistema nervioso, las colaboraciones entre científicos, el internet... pueden responder a un mismo concepto: red. Estos sistemas están compuestos por nodos (postes de luz, estaciones, amigos, neuronas…) conectados entre sí.

Diversos procesos dinámicos se dan en estas estructuras, en particular: los caminantes aleatorios. Fue este movimiento lo que llevó a Alejandro Pérez Riascos, estudiante de doctorado del IFUNAM, a adentrarse en los procesos de búsqueda dentro de redes complejas y a presentar algunos de sus resultados en el Seminario de Estudiantes el pasado 8 de octubre.

“¿Cómo se mueve una maleta en los aeropuertos? ¿Cómo se propaga un virus informático? ¿Cómo se realizan las búsquedas en internet?”, se preguntó el físico. Para descubrirlo, explicó, existe “una ecuación ‘maestra’ que me indica cómo voy a pasar yo (o la maleta o el virus) de un nodo a otro en la red”.

Al ponerlo en términos de búsqueda, esta ecuación maestra permite predecir el recorrido de un caminante clásico. Este caminante sigue un patrón de pasos al azar a nodos vecinos (conectados), lo que significa que será prácticamente imposible evitar que pase por un nodo más de una vez.

Si lo vemos en una red como Facebook, es como si sólo estableciéramos relación con nodos conectados a nosotros, es decir, si sólo aceptáramos solicitudes de amistad de con quienes tenemos amigos en común. En este modo, nuestro nivel de exploración de toda la red quedará limitado a “contactos vecinos”.

Alejandro propone algo distinto: explorar las redes con vuelos de Lévy. Como parte de su trabajo de doctorado, el joven investigador propone una forma de exploración en redes en la que el movimiento no está restringido a pasos a primeros vecinos en la red.

Este tipo de recorridos, que reciben el nombre de su creador, el matemático francés Paul Lévy, establecen recorridos aleatorios que siguen un patrón que mezcla trayectorias largas y cortas.



Modelos de las dos estrategias de búsqueda: la clásica (arriba) y la que se hace con vuelos de Lévy (abajo). Videos: Alejandro Pérez Riascos.

El caminante analizado con vuelos de Lévy ya no sigue un recorrido de búsqueda determinado por la conexión con nodos vecinos sino que seguirá un patrón caracterizado por ‘saltos’: explora un nodo, pasa a los nodos vecinos y, de pronto, da un salto a otro sitio de la red, vuelve a dar pasos a lugares próximos y, de nuevo, da un salto a otro sitio.

Siguiendo el ejemplo de Facebook: el que explora la red con vuelos de Lévy ya no establece solamente conexiones con gente con quien tiene amigos en común sino con gente totalmente ajena a su red social; ‘recorre’ la red de este nuevo amigo y, después, vuelve a establecer contacto con alguien totalmente nuevo.

“Este tipo de exploración en redes es mejor”, concluye Pérez Riascos, porque permite un conocimiento de la red más rápido y eficiente.

Aunque Facebook es un buen ejemplo, en realidad, debido a la propiedad de mundo pequeño de las redes sociales en los dos casos (los vuelos de Lévy y la estrategia de búsqueda clásica) se obtienen eficiencias de exploración similares. Este resultado cambia drásticamente en redes denominadas de mundo grande donde la estrategia de Lévy permite explorar en forma muy eficiente la red.

La idea de analizar redes con vuelos de Lévy surgió a partir de los estudios de los investigadores del IFUNAM, José Luis Mateos, Denis Boyer y Octavio Miramontes, quienes encontraron que los monos araña hacen recorridos determinados por los mismos patrones: vuelos de Lévy.

Los monos, por ejemplo, no recorren un árbol una y otra vez en busca de comida sino que hacen un patrón de saltos; exploran una zona, se mueven a lugares cercanos y, luego, saltan a otra.

Lo que hace Alejandro, entonces, es justo llevar el paralelismo a sistemas que determinan muchas de nuestras redes sociales, económicas, culturales e informáticas con potenciales aplicaciones futuras en física, por ejemplo, para modelar la difusión fraccional en estructuras discretas.


Alejandro Pérez Riascos durante el Seminario de Estudiantes. Foto: Pedro Zaldívar Sánchez.

Enlaces Relacionados

Link a artículo:

http://arxiv.org/abs/1206.2898