Detección de comunidades en redes mediante el uso de medidas borrosas

Resumen

La manipulación y análisis de grandes volúmenes de datos es un asunto cada vez más relevante en el mundo actual. En el área de la Ciencia y Análisis de Datos, existe una gran cantidad de herramientas desarrolladas para el modelado y resolución de problemas basados en situaciones reales, entre las que cabe destacar las redes complejas o grafos, modelos muy útiles para la representación de conjuntos de unidades o elementos conectados entre sí. Redes neuronales, especies animales que interactúan entre sí, sistemas biológicos y químicos, la World Wide Web y las diferentes redes sociales on line como Facebook, Twitter o LinkedIn, son algunos ejemplos de situaciones comúnmente modeladas mediante redes complejas o grafos. Este tipo de redes tiene ciertas propiedades topológicas y funcionales, y sus elementos suelen presentar patrones de interconexión que están lejos de ser regulares o aleatorios. Esta memoria se ha centrado en el estudio de la estructura de comunidades que suele caracterizar a las redes complejas. El problema relativo a la búsqueda de grupos de elementos altamente conectados en un grafo recibe el nombre de problema de detección de comunidades. Obtener una buena partición del conjunto de nodos, coherente, cohesiva, robusta y con buenas propiedades, simplifica enormemente el proceso de análisis de una red compleja. A lo largo de los años se han propuesto una gran cantidad de métodos con los que llevar a cabo esta búsqueda, así como varias métricas con las que evaluar la calidad de los resultados obtenidos. Por su alta velocidad de ejecución y por la gran calidad de los resultados proporcionados, entre los métodos existentes destaca el algoritmo de Louvain, que proporciona una partición del conjunto de nodos atendiendo a las características topológicas o estructurales del grafo, en concreto, a sus aristas. No obstante, parece justo aceptar que cualquier evento modelado por una red compleja tiene muchos más detalles de los abarcados por la representación de un grafo. Así surge la necesidad de disponer de otras herramientas con las que poder modelar todo el conocimiento disponible. En este ámbito, las medidas borrosas introducidas por Sugeno desarrollan una tarea esencial. Son la herramienta perfecta para el modelado de aspectos de la realidad difícilmente representables mediante técnicas clásicas y modelos nítidos. Fruto de la combinación de una medida borrosa con un grafo nítido, se define el grafo borroso extendido. Este modelo enriquece notablemente la representación de la realidad, dotando a los grafos de una fuente externa de conocimiento con la que considerar relaciones independientes al sistema modelado por una red compleja. Tomando el grafo borroso extendido como base, se ha trabajado en un nuevo problema: detección de comunidades en redes mediante el uso de medidas borrosas. Este problema incluye una variación en la noción de grupo, de manera que no sólo intervienen las conexiones directas entre elementos en el proceso de agrupación, sino que también el conocimiento externo representado por la medida borrosa en cuestión juega un papel esencial. Para su resolución se plantea una metodología innovadora basada en el algoritmo de Louvain. En esta memoria se especifica el método propuesto, así como su aplicación atendiendo a distintos escenarios en los que se pueden encontrar medidas borrosas de naturaleza diversa, analizando también su desarrollo en un contexto multi-dimensional y su aplicación en un caso real. El desarrollo de esta metodología de agrupamiento va secundada por la definición de nuevas herramientas que facilitan el proceso de manipulación y análisis de una medida borrosa. Pese a que esta tesis se enmarca en un contexto concreto, las herramientas y modelos presentados podrían aplicarse en otros ámbitos relacionados con el análisis de redes sociales (SNA).