Cruces Álvarez, Sergio Antonio2024-08-262024-08-262024Hidalgo Tapia, P. (2024). Algoritmos para el análisis de redes y grafos. (Trabajo Fin de Grado Inédito). Universidad de Sevilla, Sevilla.https://hdl.handle.net/11441/162048El análisis de redes y grafos es una disciplina fundamental en diversos campos como la informática, las ciencias sociales y el transporte. Esta disciplina ofrece la capacidad de modelar y analizar todo tipo de estructuras complejas, desde la red aérea de vuelos hasta las interacciones entre las proteínas en una célula, proporcionando información crucial para la optimización y gestión eficiente de estos sistemas. La teoría de redes permite representar de forma visual conjuntos de datos abstractos en formas de nodos o vértices y las conexiones o relaciones que estos pueden tener con otros nodos a través de aristas, generando un grafo sobre el cual aplicar algoritmos de centralidad, detección de comunidades u otras técnicas matemáticas que permiten el análisis de estos conjuntos de datos. El objetivo de este trabajo es presentar los conceptos necesarios para llevar a cabo un análisis de la red de transporte aéreo mediante vuelos por Europa y la red de metro de la ciudad de Sevilla. Una vez presentados los conceptos, se implementan algoritmos de centralidad como Betweenness Centrality y PageRank para el estudio de la centralidad de los nodos, y algoritmos de detección de comunidades como el algoritmo de Louvain y el de Spectral Clustering. Todo ello, unido a un estudio del comportamiento de la estructura de la red ante fallos o ataques intencionados a los nodos críticos, permite comprender la estructura y comportamiento de la red estudiada, así como su robustez. Para la implementación de estas técnicas se hace uso de Google Colab, una plataforma que permite la ejecución de código Python en la nube. Principalmente, con la librería Networkx se han podido implementar las técnicas de análisis descritas anteriormente, además de la implementación propia de algunas funciones como PageRank o las empleadas para el análisis de la robustez de la red. Además, se han empleado otras librerías adicionales como Folium, que permite superponer grafos a mapas reales, Pandas, para la extracción de los datos necesarios para la construcción de la red una vez convertidos a un formato adecuado, o Ipython.display, para la generación y visualización de animaciones que muestran la evolución de la red frente a fallos o ataques, entre otras. Estas herramientas combinadas permitieron una implementación robusta y flexible de los algoritmos, facilitando la exploración detallada y la representación gráfica de los datos y resultados. En ambos casos, se evaluaron características cruciales como la centralidad de los nodos, la detección de comunidades y la robustez de las redes frente a fallos y ataques. Los resultados obtenidos demuestran la vulnerabilidad de las redes ante ataques dirigidos a nodos con alta conectividad y su mayor resistencia frente a fallos aleatorios. En particular, se destacó la importancia de los nodos con alta centralidad en mantener la conectividad global de la red.Network and graph analysis is a fundamental discipline in various fields such as computer science, social sciences, and transportation. It offers the ability to model and analyze all types of complex structures, from airline flight networks to protein interactions within a cell, providing crucial information for the optimization and efficient management of these systems. This theory aims to visually represent abstract data sets in the form of nodes or vertices and the connections or relationships these may have with other nodes through edges, generating a graph on which to apply centrality algorithms, community detection methods, and other mathematical techniques for data set analysis. The objective of this work is to present the necessary concepts to carry out an analysis of the air transport network through flights in Europe and the metro network of the city of Seville. Once the concepts are introduced, centrality algorithms such as Betweenness Centrality and PageRank are implemented to study node centrality, along with community detection algorithms like the Louvain algorithm and Spectral Clustering. Combined with a study of the network's structural behavior under failures or intentional attacks on critical nodes, this approach enables an understanding of the structure and behavior of the studied network, as well as its robustness. Google Colab, a platform allowing the execution of Python code in the cloud, is utilized for implementing these techniques. Primarily using the Networkx library, the described analysis techniques were implemented, along with custom functions such as PageRank and those used for network robustness analysis. Additional libraries like Folium, for overlaying graphs on real maps, Pandas, for extracting the necessary data for network construction once converted to an appropriate format, and Ipython.display, for generating and visualizing animations showing the network's evolution under failures or attacks, were also employed. These combined tools enabled a robust and flexible implementation of the algorithms, facilitating detailed exploration and graphical representation of the data and results. In both cases, crucial characteristics such as node centrality, community detection, and network robustness against failures and attacks were evaluated. The results demonstrate the vulnerability of networks to attacks on highly connected nodes and their greater resistance to random failures. Particularly, the importance of highly central nodes in maintaining the network's global connectivity was highlighted.application/pdf102 p.spaAttribution-NonCommercial-NoDerivatives 4.0 Internacionalhttp://creativecommons.org/licenses/by-nc-nd/4.0/info:eu-repo/semantics/bachelorThesisinfo:eu-repo/semantics/openAccess