Estudio de la técnica Spectral clustering en un problema de particionamiento de grafo tipo k-way y la aplicaciónde la misma en la realineación de equipos ecuatorianos deportivos con restricción de cardinalidad.

Abstract

The main objective of this study focuses on the analysis of the clustering technique known as Spectral Clustering, which has great relevance in recent times due to its valuable results. It begins with a general review of basic concepts and fundamental theory to a specific study of spectral clustering and Markov chains. The algorithm presented by Marina Meila, which will be the primary focus of this work, is introduced, with a minor adjustment made for its execution, which will be explained later. Subsequently, computational tests are conducted on different random instances, presenting graphical results that reveal interesting findings about the method Spectral Clustering, and a comparison to the k-means method. Furthermore, a summary table is included detailing the execution times of Spectral Clustering and the traditional k-means technique, a statistic measuring clustering quality, and the objective function of finding the maximum cut, highlighting how the spectrum of a matrix significantly affects the k-means’ execution time. In addition to the tests on random instances, the algorithm is applied to a real instance composed of cities in Ecuador participating in interprovincial football championships. The results of this application are compared with those obtained in a study conducted by Recalde et al. in 2018, where the same case was addressed.