Algoritmos de detección de comunidades en grafos y aplicación en conjuntos de datos de tránsito en aeropuertos y trasvase de alumnos entre titulaciones de la UPV

Abstract

[CA] Els avanços en teoria de grafs i anàlisi de xarxes complexes han estat fonamentals per a una millor comprensió dels sistemes complexos que poden aparèixer a la vida real. L’estructura comunitària és una de les característiques més importants dels grafs que modelen aquests sistemes; no obstant això, l’obtenció de comunitats és un problema extraordinàriament complex i encara no s’ha obtingut una solució que funcione satisfactòriament en qualsevol tipus de graf que es puga presentar en situacions reals. Durant les dues darreres dècades s’han desenvolupat multitud de mètodes per detectar comunitats en grafs, usant conceptes i tècniques de diferents àmbits científics com la física, la biologia, o les ciències socials. En aquest treball s’exposen alguns dels mètodes més emprats actualment a detecció de comunitats, i es presenten certs algorismes l’objectiu dels quals és la millora dels resultats obtinguts fins ara en grafs dirigits dèbilment connectats. A més, es presenta un nou algorisme basat en tècniques usades en tractament d’imatges per a la detecció de fronteres. Aquest nou mètode fa ús del producte de convolució per a la detecció i poda d’arestes de soroll. L’eficàcia d’aquest algorisme es comprova mitjançant la seva aplicació en dos casos reals: el trànsit de vols comercials entre aeroports dels Estats Units, i el flux d’estudiants entre graus al sistema d’accés a la universitat pública a Espanya

[ES] Los avances en teoría de grafos y análisis de redes complejas han sido fundamentales para una mejor comprensión de los sistemas complejos que pueden aparecer en la vida real. La estructura comunitaria es una de las características más importantes de los grafos que modelan estos sistemas; sin embargo, la obtención de comunidades es un problema extraordinariamente complejo y aún no se ha obtenido una solución que funcione satisfactoriamente en cualquier tipo de grafo que pueda presentarse en situaciones reales. Durante las dos últimas décadas se han desarrollado multitud de métodos para detectar comunidades en grafos, usando conceptos y técnicas de distintos ámbitos científicos como la física, la biología, o las ciencias sociales.

En este trabajo se exponen algunos de los métodos más empleados actualmente en detección de comunidades, y se presentan ciertos algoritmos cuyo objetivo es la mejora de los resultados obtenidos hasta el momento en grafos dirigidos débilmente conectados. Además, se presenta un nuevo algoritmo basado en técnicas usadas en tratamiento de imágenes para la detección de bordes. Este nuevo método hace uso del producto de convolución para la detección y poda de aristas de ruido. La eficacia de este algoritmo se comprueba mediante su aplicación en dos casos reales: el tráfico de vuelos comerciales entre aeropuertos de Estados Unidos, y el flujo de estudiantes entre grados en el sistema de acceso a la universidad pública en España.

[EN] The advances in graph theory and complex network analysis have been fundamental in a better understanding of real complex systems. Community structure is one of the most important characteristics in graphs modelling these systems; nevertheless, obtaining graph's communities is an extraordinarely complicated problem and has not yet been found a solution that can obtain satisfying results in any kind of graph that may appear in real scenarios. During the last two decades, a huge number of community detection methods have been developed, employing concepts and techniques from various scientific areas such as physics, biology or social sciences.

In this work, some of the most popular community detection methods are described, and are also presented new algorithms developed to improve the results in weakly connected directed graphs. A new algorithm based on image processing techniques for edge detection is described. This new method makes uso of the convolution product for detecting and pruning noise edges that may be present in the graph. The performance of this algorithm is proved in two real cases: commercial flights transit between US airports, and studient transit between univeristy degrees in the access system to the Spanish public universities.