Optimización Multiobjetivo para la Detección de Comunidades en Redes Compleja

Abstract

A raíz de las bases de la teoría de grafos que surgieron en el siglo XVIII y sus desarrollos posteriores, es posible estudiar las relaciones o vínculos existentes en un conjunto de elementos y determinar las características y propiedades de dichas relaciones. En las últimas décadas, los importantes y continuos avances en el ámbito de las ciencias de la computación han permitido modelar y analizar grafos de cualquier escala y tipología correspondientes a sistemas reales de alta complejidad que proceden de multitud de áreas de conocimiento como ingeniería, física, ciencias sociales, etc. En la actualidad, gracias al modelado y análisis de grafos por computador, es posible obtener información valiosa sobre las relaciones funcionales o las características de un determinado sistema, por complejo que éste sea. Ello ha dado lugar a que investigadores de todo el mundo muestren un gran interés por resolver una amplia variedad de problemas relacionados con grafos, como pueden ser: partición de grafos, coloreado de grafos, problemas de enrutado, problemas de flujos en redes, etc. Todos estos problemas son altamente complejos, hasta el punto de estar incluidos en la categoría de problemas NP-completos, lo que implica que instancias lo suficientemente grandes de dichos problemas no pueden ser resueltos en un tiempo limitado En los últimos años, un problema relativamente nuevo que puede ser abordado mediante las técnicas de análisis basadas en grafos, ha despertado un gran interés dentro de la comunidad científica debido al potencial de analizar sistemas complejos que éste ofrece. Este problema, llamado detección de comunidades, nace a raíz de una característica común inherente a todos los sistemas complejos, la presencia de patrones de nodos más densamente conectados entre sí que con el resto de nodos de la red. De los nodos que muestran estos patrones de conexión, llamados comunidades, se espera que compartan ciertas propiedades que permitirán detectar nuevas características o relaciones funcionales de la red. La búsqueda de estos patrones o estructuras de comunidades es conocida como problema de la detección de comunidades, el cual ha sido clasificado en la literatura científica como problema NP-completo. Cómo encontrar la estructura de comunidades óptima que mejor representa las características de una red, se ha convertido en todo un hándicap, pues se han propuesto multitud de algoritmos y funciones objetivo para resolver el problema. Entre ellos, los algoritmos evolutivos y el índice de Modularidad han destacado como las principales soluciones aceptadas por la comunidad científica. Además de la importancia de la búsqueda de un algoritmo capaz de resolver el problema de la detección de comunidades eficientemente, el análisis de redes complejas a menudo se encuentra limitado a estudiar las características de una red desde una única perspectiva debido al enfoque propuesto por la mayoría de los algoritmos que encontramos en la literatura científica. Con el fin de lograr un análisis más completo y detallado de las redes objeto de estudio, esta tesis doctoral propone un enfoque novedoso, flexible y adaptativo para el análisis de comunidades de cualquier complejidad y tipología de red. En particular, se analizan redes de diferente topología y extensión comúnmente utilizadas en la literatura científica, y, además, se lleva a cabo un estudio pionero en el ámbito de ingeniería eléctrica sobre redes de transmisión de alta tensión. La importancia de este estudio radica en que estamos tratando con una de las mayores infraestructuras creadas por el hombre, con cientos de miles de kilómetros de líneas de alta tensión que interconectan no sólo regiones y países, sino también áreas continentales. Además, debido a la creciente demanda de electricidad y a la aparición de nuevos formatos de generación eléctrica, resulta imprescindible abordar el estudio sobre la ampliación y modificación de redes eléctricas mediante nuevos procedimientos complementarios a las técnicas tradicionales utilizadas en el estudio de sistemas eléctricos de potencia. La incorporación de estos nuevos formatos de generación de energía eléctrica renovables, está provocando que el diseño clásico de las redes eléctricas pase de un modelo centralizado, basado en disponer de un número relativamente acotado de centrales térmicas, nucleares e hidroeléctricas, a un modelo distribuido con unpeso creciente en energías renovables, originando así un aumento de laconectividad en las redes y, por consiguiente, un incremento de su complejidad. En este sentido, se hace indispensable la necesidad de aplicar estrategias de control más robustas, así como nuevas técnicas de optimización para gestionar sistemas a gran escala. Actualmente, aunque existen procedimientos de análisis y diseño de redes eléctricas, como es el caso de la resolución de flujos de potencia que permite analizar múltiples configuraciones del sistema eléctrico, el inmenso abanico de posibles configuraciones existentes provoca que sea necesario aplicar nuevos procedimientos complementarios de cara a hacer factible la búsqueda de soluciones. En este sentido, en la presente tesis doctoral se aplica la detección de comunidades en el estudio y análisis de redes eléctricas de gran tamaño a fin de ampliar las conclusiones obtenidas por los procedimientos tradicionales, además de analizar los resultados como posibles mejoras de control de la red, que supondrían de una mayor fiabilidad y capacidad de restauración ante graves perturbaciones como desastres naturales (tormentas, terremotos, etc.) mediante el desarrollo de nuevos planes de conmutación para proteger islas o desconexiones parciales de la red, evitando así una mayor degradación durante los incidentes. En resumen, el objetivo de esta tesis se centra en afrontar el problema de la detección de comunidades en ámbitos que precisan de la aparición de nuevas técnicas de diseño y control, a través del desarrollo de nuevos algoritmos evolutivos (mono-objetivo y multiobjetivo) que permitan analizar las características topológicas de una red desde distintas perspectivas, con mayor o menor nivel de detalle en función de las necesidades del analista. Para lograr este objetivo, en primer lugar, se han diseñado métodos de inicialización poblacional eficientes y operadores evolutivos avanzados basados en intercambios entre comunidades, que han sido incorporados al algoritmo genético mono-objetivo propuesto en esta tesis, el cual optimiza el popular Indice de Modularidad como función objetivo. Dicho algoritmo, denominado “Generational Genetic Algorithm” (GGA+), ha sido evaluado mediante un análisis de rendimiento sobre multitud de benchmarks populares basados en redes sociales, además de sobre grafos de gran escala con miles de nodos y aristas que representan redes reales de transmisión de alta tensión de escala nacional y continental. Tras el éxito de los resultados mostrados por la implementación del algoritmo mono-objetivo, con la finalidad de evaluar el rendimiento que los métodos de detección de comunidades evolutivos pueden ofrecer en el ámbito de ingeniería, distintos algoritmos como el mencionado GGA+ y otros algoritmos evolutivos referenciados en la literatura, como “Modularity and Improved Genetic Algorithm” (MIGA) o el bien conocido método de “Louvain”, se han aplicado sobre múltiples redes eléctricas, demostrando que los resultados obtenidos avalan su utilidad y buen rendimiento. Actualmente, la mayoría de métodos destinados a resolver el problema de la detección de comunidades, utilizan un enfoque mono-objetivo, siendo el índice Modularidad la función objetivo más extendida. Sin embargo, debido a la propia definición de comunidad en la que ésta puede ser vista desde un enfoque multiobjetivo, donde un objetivo puede ser maximizar el número de conexiones dentro de una comunidad y otro objetivo minimizar el número de conexiones con nodos externos a la comunidad, y, debido a que algunos estudios recientes han demostrado que al considerar Modularidad como único objetivo pueden surgir inconvenientes relacionados con el límite de resolución y desbalanceo de las soluciones, parece adecuado plantear el problema de la detección de comunidad desde un punto de vista multiobjetivo. Por estos motivos, en segundo lugar, basándonos en el buen rendimiento demostrado por GGA+, se ha diseñado una nueva versión multiobjetivo llamada MOGGA+, la cual incluye nuevos objetivos a optimizar en la detección de comunidades, abriendo de esta manera una nueva vía de investigación mediante la aplicación de algoritmos evolutivos multiobjetivo que optimizan simultáneamente diferentes objetivos. Más concretamente, MOGGA+ ha sido diseñado con nuevos métodos de inicialización avanzados y operadores evolutivos. Además, utiliza un conjunto de soluciones no dominadas basado en la dominancia de Pareto, y una estructura adicional para modificar dinámicamente la probabilidad de aplicar distintos operadores evolutivos en tiempo de ejecución. En cuanto a los diferentes objetivos optimizados, se ha analizado la combinación del índice de Modularidad con un novedoso objetivo propuesto en esta tesis, “Desbalanceo” de comunidades, propiedad a tener en cuenta a la hora de diseñar redes eléctricas resistentes a contingencias, donde es importante que la red pueda ser separada en islas (subredes) de escala aproximadamente similar, para evitar una mayor degradación de la red. También se ha analizado el objetivo Conductancia (como alternativa a Modularidad) junto con Desbalanceo. Conductancia es una medida de lafracción del volumen total de aristas en un subgrafo que están conectados a vértices o nodos de otros subgrafos de una red. Por último, cabe señalar que MOGGA+ incorpora técnicas de paralelismo para mejorar su rendimiento. Abstract: Following the foundations of graph theory that emerged in the eighteenth century, as well as its subsequent developments, it is possible to study the relationships or links existing in a set of elements and identify the characteristics and properties of those relationships. In the recent decades, the important and continuous advances in the field of computer science have made it possible to model and analyze graphs of any scale and typologycorresponding to highly complex real systems that come from many areas of knowledge, such as engineering, physics and social sciences. At present, thanks to computer graphics modeling and analysis, it is possible to obtain valuableinformation on the functional relationships or characteristics of a specificsystem, however complex it may be. This has led researchers around the world to show great interest in solving a wide variety of graph-related problems, among which can be found: graph partitioning, graph coloring, routing problems and network flow problems. All these problems are highly complex, to the extent that they are included in the category of NP-complete problems, which implies that sufficiently large instances of such problems cannot be solved in a limited time. In recent years, a relatively new problem that can be addressed through graphical analysis techniques has sparked great interest within the scientific community due to the potential to analyze the complex systems it offers. This problem, called community detection, arises from a common characteristic inherent in all complex systems, the presence of node patterns more densely connected to each other than to the rest of the nodes in the network. The nodes that show these connection patterns, called communities, are expected to share certain properties that will allow them to detect new features or functional relationships in the network. The search for these community structures is known as the community detection problem, which has also been classified in the scientific literature as an NP-complete problem. How to find the optimal community structure that best represents the characteristics of a network has become a real handicap, since many objective algorithms and functions have been proposed to solve the problem. Among them, evolutionary algorithms and the Modularity Index have stood out as the main solutions accepted by the scientific community. In addition to the importance of searching for an algorithm capable of solving the community detection problem efficiently, complex network analysis is often limited to studying the characteristics of a network from a single perspective due to the approach proposed by most of the algorithms found in the scientific literature. In order to achieve a more complete and detailed analysis of the networks under study, this doctoral thesis proposes a novel, flexible and adaptive approach for the analysis of communities of any complexity and network typology. More specifically, networks of different topology and extension commonly used in the scientific literature are analyzed, and, in addition, a pioneering study in the field of electrical engineering on high-voltage transmission networks is carried out. The importance of this study lies in the fact that we are dealing with one of the largest infrastructures created by humanity, with hundreds of thousands of kilometers of high-voltage lines that interconnect regions, countries and continental areas. What is more, due to the growing demand for electricity and the appearance of new formats of electricity generation, it is essential to undertake the study on the expansion and modification of electrical networks through new complementary procedures to the traditional techniques used in the study of electrical power systems. The incorporation of these new renewable electricity generation formats is causing the classic design of electrical networks to change from a centralized model, based on having a relatively limited number of thermal, nuclear and hydroelectric plants, to a distributed model with an increasing weight in renewable energy, thus causing an increase in network connectivity and, consequently, an increase in its complexity. In this sense, the need to apply more robust control strategies, as well as new optimization techniques to manage systems on a large scale, is essential. Currently, although there are analysis and design procedures for electrical networks, such as the resolution of power flows that allow multiple configurations of the electrical system to be analyzed, the immense range of possible existing configurations means that it is necessary to apply new complementary procedures in order to make the search for solutions feasible. In this sense, in this doctoral thesis, community detection is applied in the study and analysis of large electrical networks in order to expand the conclusions obtained by traditional procedures and analyze the results as possible improvements in network control, thus enhancing its reliability and allowing a faster and more efficient restoration in the face of serious disturbances such as natural disasters (storms, earthquakes, etc.), all through the development of new switching plans to protect islands or partial disconnections from the network, thus avoiding further degradation during incidents. In summary, the objective of this thesis is based on facing the problem of detecting communities in areas that require the appearance of new design and control techniques, through the development of new evolutionary algorithms that allow analyzing the topological characteristics of a network from different perspectives, with a greater or lesser level of detail depending on the analyst's needs. To achieve this objective, firstly, efficient population initialization methods and advanced genetic operators based on exchanges between communities have been designed, which have been incorporated into the single-objective genetic algorithm proposed in this thesis, which optimizes the popular Modularity Index as an objective function. This algorithm, called "Generational Genetic Algorithm" (GGA+), has been evaluated through a performance analysis on a multitude of popular benchmarks based on social networks, as well as on large-scale graphs with thousands of nodes and edges that represent real high-voltage transmission networks on a national and continental scale. After the success of the results shown by the implementation of the single-objective algorithm, in order to evaluate the performance that evolutionary community detection methods can offer in the engineering field, different algorithms such as the aforementioned GGA+, along with other evolutionary algorithms referenced in the literature, such as "Modularity and Improved Genetic Algorithm" (MIGA) or the well-known "Louvain" method, have been applied to multiple electrical networks, showing index being the most widely chosen objective function to optimize. However, due to the definition of community in which it can be viewed from a multiobjective approach, where one objective may be to maximize the number of connections within a community and another objective to minimize the number of connections with nodes external to the community, and since some recent studies have shown that when considering Modularity as the only objective, problems related to the resolution limit and imbalance of the solutions may arise, it seems appropriate to approach the problem of community detection from a multi-objective point of view. For these reasons, secondly, based on the good performance demonstrated by GGA+, the decision was made to design the multi-objective version called MOGGA+, which includes new objectives to be optimized in the detection of communities, thus opening a new avenue of research by applying multi-objective evolutionary algorithms that simultaneously optimize different objectives. More specifically, MOGGA+ has been designed with new advanced initialization methods and evolutionary operators. In addition, it uses a set of non-dominated solutions based on Pareto dominance, and an additional structure to dynamically modify the probability of applying different evolutionary operators at run time. Regarding the different optimized objectives, the combination of the Modularity index has been analyzed with a novel objective proposed in this thesis, Imbalance, a property to take into account when designing electrical networks resistant to contingencies, in which it is important that the network can be separated into islands (subnets) of approximately similar scale, to avoid further degradation of the network. nodes of other subgraphs in a network. Finally, it should be noted that MOGGA+ incorporates parallelism techniques to improve its performance. The objective Conductance (as an alternative to Modularity), along with Imbalance, has also been analyzed. Conductance is a measure of the fraction of the total volume of edges in a subgraph that are connected to vertices or that the results obtained support their usefulness and good performance. Currently, most of the methods aimed at solving the problem of community detection use a mono-objective approach, with the Modularity