Detección de estructuras latentes en redes complejas mediante técnicas de teoría de grafos y álgebra lineal

Abstract

El presente trabajo examina la integración de distintos tópicos matemáticos —como la teoría de grafos, el álgebra lineal y el análisis de datos— para el estudio estructural de redes complejas construidas partir de datos relacionales. Se muestran estrategias de detección de comunidades aplicadas tanto a redes simuladas como a redes reales, con el objetivo de mostrar cómo estos enfoques pueden vincularse en un mismo marco analítico. Estas estrategias dependen del objeto del investigador, por lo que los métodos propuestos se aplican según el interés de la determinación de comunidades. Utilizando una base de datos real del sistema de ciencia y tecnología argentino (SICYTAR, 2018) extraída del sitio datos.gob.ar, así como también una red simulada, se aplicaron tres enfoques complementarios: el coloreo de grafos, el agrupamiento espectral y el algoritmo de Girvan–Newman. En primer lugar, se utilizó la técnica del coloreo de grafos como estrategia organizativa para clasificar tareas, atributos y así generar una división preliminar de nodos. Luego, poniendo en práctica conceptos del álgebra lineal como la matriz Laplaciana y sus autovalores, se implementó el agrupamiento espectral para detectar patrones estructurales internos. Por último, se utilizó el algoritmo de Girvan–Newman para identificar comunidades basadas en la eliminación de aristas con un alto valor de intermediación. Todo este proceso siendo hecho con el paquete igraph del software R. Los resultados muestran que la integración de estos métodos permite modelar y optimizar la organización de redes complejas, revelando estructuras internas poco evidentes y ofreciendo una lectura m´as profunda de las redes y datos relacionales mediante el uso conjunto de herramientas matemáticas. De este modo, este trabajo no solo aporta resultados, sino también una propuesta que puede extenderse a distintos contextos que manejen grandes cantidades de datos, tales como sistemas educativos o instituciones científicas.

This paper examines the integration of different mathematical topics—such as graph theory, linear algebra, and data analysis—for the structural study of complex networks built from relational data. Community detection strategies are presented, applied to both simulated and real networks, with the goal of demonstrating how these approaches can be linked within a single analytical framework, which is the objective of this thesis. These strategies depend on the researcher’s objective, so the proposed methods are applied according to the interest in determining communities. Using a real database of the Argentine Science and Technology System (SICYTAR, 2018) extracted from datos.gob.ar, as well as a simulated network, three complementary approaches were applied: graph coloring, spectral clustering, and the Girvan-Newman algorithm. First, graph coloring was used as an organizational strategy to classify tasks and attributes, thus generating a preliminary node division. Then, applying concepts from linear algebra such as the Laplacian matrix and its eigenvalues, spectral clustering was implemented to detect internal structural patterns. Finally, the Girvan-Newman algorithm was used to identify communities based on the elimination of edges with a high betweenness value. This entire process was performed using the igraph package of the R software. The results show that the integration of these methods allows to model and optimize the organization of complex networks, revealing internal structures that are not obvious and offering a deeper reading of networks and relational data through the joint use of mathematical tools. In this way, this work not only provides results but also a proposal that can be extended to different contexts that handle large amounts of data, such as educational systems or scientific institutions.