Diseño e implementación de una herramienta para la comparación de algoritmos de detección de comunidades en grafos

Abstract

RESUMEN: En la última década, la aparición de servicios como Facebook o Twitter ha dado como resultado un renovado interés en el análisis de redes sociales, siendo la detección de comunidades uno de los principales problemas que se han abordado. La detección de comunidades consiste en organizar los vértices de un grafo en grupos densamente conectados entre sí.Apesar de que se han propuesto decenas de algoritmos y varios generadores de grafos para comprobar su eficacia, la prueba de los mismos no ha recibido gran atención en la literatura: ésta suele limitarse a la aplicación del algoritmo propuesto a un conjunto de grafos cuya estructura es conocida de antemano o a la selección de los parámetros de un generador de grafos que permitan obtener redes estructuralmente sencillas. Esto supone un gran problema ya que no se puede afirmar qué método es mejor, por lo que, en la práctica, la elección del algoritmo a usar vendrá determinada por factores que nada tienen que ver con su eficiencia (por ejemplo, su popularidad o la reputación de su autor). Por ello, este Proyecto Fin de Carrera ha diseñado e implementado una aplicación que permite comparar algoritmos de detección de comunidades de manera imparcial. Ésta se ha diseñado de tal manera que los usuarios pueden añadirle algoritmos, generadores de grafos y medidas de evaluación de resultados, para lo cual se ha hecho uso de un lenguaje multiplataforma de propósito general, como Java. La aplicación obtiene los grafos a partir de los generadores suministrados y se los envía a los algoritmos para que éstos le devuelvan la estructura de comunidades detectada. Así, con las medidas de evaluación oportunas, puede determinar qué algoritmo se comporta mejor. Asimismo, se ha implementado implementar un mecanismo para que la ejecución del código de los componentes suministrados sea segura, de manera que un usuario malintencionado no pueda ejecutar código que sea capaz de afectar a la seguridad de la máquina. El diseño e implementación de esta aplicación se han llevado a cabo siguiendo la metodología MÉTRICA en desarrollo orientado a objetos.

ABSTRACT: In the last decade, the appearance of services such as Facebook or Twitter has allowed for a renewed interest in social network analysis, being community detection one of the main problems tackled. Community detection consists in organizing the vertices of a graph in groups that permit them to be densely connected between each other. Despite the fact that many different algorithms and graph generators to test the efficiency of those algorithms have been proposed, that testing has not been duly treated in the literature: it usually is limited to the application of the proposed algorithm on a set of graphs whose structure is known in advance or the selection of the parameters of a graph generator that permit obtaining structurally simple networks. This becomes a great problem due to the fact that it cannot be ascertained what method is best, thus in practice choosing what algorithm to use will become conditioned by factors that have nothing to do with its efficiency (e.g., its popularity or the reputation of its author). For this reason, this Final Degree Project designed and implemented an application that permits comparing community detection algorithms in graphs in an impartial fashion. Itwas developed in such a manner that users can add algorithms, graph generators and measures for comparing results, for which a multipurpose and multiplatform programming language was used, in this case Java. The application obtains graphs from the generators included in it and sends them to the algorithms for these to return the community structure detected. Thus, with the appropriate measures, it is able to determine what algorithm does best. Also, a mechanism was implemented so as to ensure that the execution of these modules is safe, so that a malicious user cannot execute code that potentially puts the machine security at risk. The design and implementation of this application were done using the MÉTRICA methodology for object-oriented developments.