Vinícius da Fonseca Vieira
Resumo
Uma das propriedades mais importantes em redes complexas é a sua estrutura de comunidades, ou seja, sua divisão em grupos de nós densamente conectados entre elementos do mesmo grupo e fracamente conectados com elementos fora do grupo. Dessa forma, há um grande interesse na investigação de métodos que sejam capazes de detectar a estrutura de comunidades em redes e um dos maiores desa os da área se coloca no estudo de redes reais, devido a suas grandes dimensões. O objetivo deste trabalho é apresentar o desenvolvimento de um código de alto desempenho para alguns dos métodos mais abordados na literatura para detecção de comunidades através da otimização da medida de modularidade: o método espectral de Newman utilizando uma etapa de ajuste no e o método de Clauset, Newman e Moore (CNM) com modi cações encontradas na literatura. Uma variação na etapa de ajuste no do método espectral de Newman proposta neste trabalho é capaz de acelerar sua execução sem comprometer a modularidade. Além disso, neste trabalho, utiliza-se a variação da modularidade para identi car a organização hierárquica das comunidades. Os resultados observados pela aplicação dos métodos a um vasto conjunto de redes reais permitem a análise das estruturas de comunidade das redes estudadas e possibilitam uma investigação comparativa dos métodos implementados. A metodologia adotada permite a geração de partições com valores de modularidade compatíveis com a literatura de detecção de comunidades em redes de larga escala, superando 1 milhão de nós com o método espectral de Newman.
Abstract
One of the most important properties in complex networks is their community structure, i.e. its division into groups of nodes densely connected between elements of the same group and weakly connected to elements outside the group. Thus, there is great interest in the investigation of methods that are able to detect the community structure in networks and one of the major challenges in the area arises in the study of real networks, due to their large sizes. The purpose of this work is to present the development of a high performance code for some of the most discussed methods in the literature for community detection by the optimiaztion of modularity measure: Newman's spectral method, using a ne tuning stage and the method of Clauset, Newman and Moore (CNM) with modi cations found in the literature. A variation in the ne tuning stage in Newman's spectral method proposed in this work is able to accelerate its execution without compromising the modularity. Moreover the modularity variation is used in order to identify the hierarchical organization of the communities. The results observed by the application of the methods to a wide range of real networks allow the structural analysis of the community structures of the studied networks and enable a comparative investigation of implemented methods. The adopted methodology allows the generation of partitions with modularity values consistent with the literature of community detection in large scale networks, and it overcomes 1 million nodes with Newman's spectral method.
