@misc{10902/699,
year = {2012},
month = {7},
url = {http://hdl.handle.net/10902/699},
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 = {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.},
title = {Diseño e implementación de una herramienta para la comparación de algoritmos de detección de comunidades en grafos},
author = {Palazuelos Calderón, Camilo},
}