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

Isabelle Soares, Carla Silva Oliveira, José André de Moura Brito

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.


Palavras-chave


Grafos; Comunidades; Algoritmos.

Texto completo:

PDF


DOI: https://doi.org/10.7177/sg.2014.V9.N4.A14

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

 

ISSN: 1980-5160

Rua Passo da Pátria 156, bloco E, sala Sistemas & Gestão, Escola de Engenharia, São Domingos, Niterói, RJ, CEP: 24210-240

Tel.: (21) 2629-5616

Correspondência: Caixa Postal LATEC: 100175, CEP 24.020-971, Niterói, RJ