Detecção de comunidades em redes por algori tmos ensemble

Abstract

Many elements in people’s everyday life can be represented by a graph or network. Such a system can possess thousands of elements, many of which can be related to one another. Finding communities or clusters within these systems to evaluate groups of related vertices, as opposed to the entire network, or each individual vertex, appears as a viable alternative for the analysis of these graphs. Due to its applications in various scientific fields, such as Biology, Medicine and Sociology, among others, clustering nodes becomes a viable alternative for these graphs, which may contain a large amount of nodes and edges. For data analysis, and more specifically, data clustering, a common strategy is consensus clustering, which combines two or more computational models to improve the quality of solutions, as compared to those found by only one model. Despite the good results obtained for data clustering, this strategy has not been frequently applied to finding communities in networks. For this reason, this dissertation proposes a genetic algorithm that applies consensus clustering techniques to identify communities in networks. Considering as the objective function a measure here called ”adjusted modularity”, our algorithm performed better than classic algorithms within the scientific literature in experiments performed with artificial and real-world graphs.

Diversos elementos presentes no cotidiano das pessoas podem ser representados por meio de um grafo ou rede. Um sistema que assume tal representação pode possuir milhares de elementos, alguns deles relacionados entre si. Encontrar comunidades ou clusters nesses sistemas para avaliação dos grupos de vértices relacionados ao invés da investigação do grafo como um todo ou dos vértices individualmente surge como uma alternativa viável para a análise desses grafos. Devido à existência de aplicações em diversas áreas do conhecimento, tais como biologia, medicina, sociologia, entre outras, agrupar vértices torna-se como uma alternativa atraente para esses grafos que podem possuir uma grande quantidade de vértices e arestas. Para a análise de dados, mais especificamente, em agrupamento de dados, uma estratégia bastante utilizada é a de agrupamento consensual, que consiste em combinar dois ou mais modelos computacionais para obter maior robustez nas soluções em comparação às encontradas por um único modelo. Apesar dos bons resultados encontrados para agrupamento de dados, essa estratégia não tem sido muito empregada para encontrar comunidades em redes. Por esse motivo, nesta Dissertação propomos um algoritmo genético que aplica técnicas de agrupamento consensual para encontrar comunidades em redes. Considerando como função objetivo uma medida chamada aqui de modularidade ajustada, nosso algoritmo superou o resultado de algoritmos clássicos da literatura em experimentos realizados usando grafos artificiais e reais.