Ir para o menu de navegação principal Ir para o conteúdo principal Ir pro rodapé

Artigos

v. 9 n. 4 (2014): Dezembro/2014

Um Estudo do Problema de Detecção de Comunidades em Redes

DOI
https://doi.org/10.7177/sg.2014.V9.N4.A14
Enviado
dezembro 3, 2014
Publicado
dezembro 3, 2014

Resumo

O presente trabalho traz um estudo do problema de detecção de comunidades associadas às redes complexas, ou seja, redes formadas por elementos do mundo real. De forma a realizar esse estudo, as redes foram representadas por uma estrutura matemática denominada grafo. E de forma a detectar as comunidades nessas redes, aplicou-se um algoritmo de detecção de comunidades no grafo associado. Em particular, neste trabalho, optou-se pela utilização de um algoritmo de detecção de comunidades, denominado FastGreedy. Uma vez definida a comunidade, em uma segunda fase do estudo, foi aplicado um algoritmo de agrupamento (K-means) em cada um dos grafos, considerando o número de grupos igual ao número de comunidades. A comunidade definida e os agrupamentos construídos foram avaliados a posteriori mediante o cálculo da modularidade e do coeficiente de silhueta. Ao final desse trabalho, são apresentados alguns resultados computacionais concernentes à aplicação desses algoritmos, disponíveis no software livre R, considerando três bases reais. 

This paper presents a study of the problem of detecting communities associated with complex networks, this is, networks comprising elements of the real world. In order to perform this study, networks were represented by a mathematical structure called graph. And, in order to detect the communities these networks was applied to an algorithm for detecting communities in associated graph. In particular, in this work, we opted for the use of a community detection algorithm, called FastGreedy. Once defined the community, in a second phase of the study, we applied a clustering algorithm (K-means) in each of the graphs, groups considering the number equal to the number of communities. The community defined and constructed clusters were evaluated retrospectively by calculating the coefficient of modularity and silhouette. At the end of this work are presented some results concerning the application of these computational algorithms available in the free software R, considering three real bases.

Keywords: Graphs; Communities; Algorithms.

Downloads

Não há dados estatísticos.