Detección de comunidades en redes complejas basada en la sincronización

Abstract

El estudio de las redes complejas atrae cada vez más el interés de muchos investigadores por muchas razones obvias. Muchos sistemas tanto reales como tecnológicos pueden representarse como redes complejas, es decir, un conjunto de entidades en interacción de acuerdo a propiedades topológicas no triviales. La interacción entre los elementos de la red puede describir comportamientos globales tales como el tráfico en Internet, el servicio de suministro de electricidad o la evolución de los mercados. Una de las propiedades topológicas de los grafos que caracterizan estos sistemas complejos es la estructura de comunidad. La detección de comunidades tiene como objetivo la identificación de los módulos o grupos con alguna o varias propiedades en común basándose únicamente en la información codificada en la topología del grafo. La detección de comunidades es importante no sólo para caracterizar el grafo, sino que además ofrece información sobre la formación de la red así como sobre su funcionalidad. El estudio de las leyes subyacentes que gobiernan la dinámica y evolución de los sistemas complejos y la caracterización de sus grafos revela que las redes a gran escala, generalmente, se caracterizan por topologías complejas y estructuras heterogéneas. La estructura de conectividad de estas redes se manifiesta por la presencia de comunidades (clusters o grupos), es decir, conjuntos de nodos que comparten propiedades comunes o juegan roles similares en la red. Las comunidades pueden representar relaciones de amistad en las redes sociales, páginas web con una temática similar, o rutas bioquímicas en las redes metabólicas. Formalmente, una red es un grafo compuesto por un gran número de nodos altamente interconectados donde una comunidad se resalta por la presencia de un gran número de aristas conectando nodos dentro de grupos individuales, pero con baja concentración de aristas entre estos grupos. El mejor modo para establecer la estructura de comunidad de una red compleja es un problema todavía sin resolver. Durante los últimos años, se han propuesto muchos algoritmos que persiguen extraer la partición óptima de una red en comunidades. El clustering espectral, los algoritmos de particionamiento de grafos, los métodos basados en la modularidad o los algoritmos basados en la sincronización son sólo algunos de estos algoritmos de extracción de comunidades. Los algoritmos dinámicos basados en la sincronización han sido estudiados por varios autores, y han demostrado que la monitorización del proceso dinámico de la sincronización permite revelar las diferentes escalas topologicas presentes en una red compleja. Muchos de estos algoritmos se basan en el modelo Kuramoto o en algunas de sus variantes como el modelo de opinión, donde cada oscilador aislado es modelado en un espacio unidimensional. El objetivo principal del presente proyecto es la implementación de un algoritmo de detección de comunidades basado en la sincronización de osciladores acoplados. Cada oscilador ha sido modelado mediante el sistema dinámico de Rossler, un sistema de ecuaciones diferenciales definido en un espacio tridimensional.