UM ESTUDO COMPUTACIONAL COMPARATIVO ENTRE ALGORITMOS DE AGRUPAMENTO E DE DETECÇÃO DE COMUNIDADES

UM ESTUDO COMPUTACIONAL COMPARATIVO ENTRE ALGORITMOS DE AGRUPAMENTO E DE DETECÇÃO DE COMUNIDADES

Silva, Daiana Medeiros da; Brito, José André de Moura; Oliveira, Carla Silva

Artigo Completo:

O presente trabalho tem por objetivo comparar o desempenho de dois algoritmos de Agrupamento não-hierárquicos, quando aplicados a um conjunto de redes, frente a dois algoritmos de Detecção de Comunidades (Fast Greedy e Walktrap). A comparação entre os resultados foi feita a partir da aplicação do Índice de Silhueta. Esses algoritmos foram aplicados em 30 bases de dados artificiais, obtidas através do pacote clustergeneration do software R. Foi possível perceber que os algoritmos de agrupamento (k-means e PAM) apresentam melhores soluções quanto às silhuetas, frente aos algoritmos de Detecção de Comunidades em redes (Fast Greedy e Walktrap).

O presente trabalho tem por objetivo comparar o desempenho de dois algoritmos de Agrupamento não-hierárquicos, quando aplicados a um conjunto de redes, frente a dois algoritmos de Detecção de Comunidades (Fast Greedy e Walktrap). A comparação entre os resultados foi feita a partir da aplicação do Índice de Silhueta. Esses algoritmos foram aplicados em 30 bases de dados artificiais, obtidas através do pacote clustergeneration do software R. Foi possível perceber que os algoritmos de agrupamento (k-means e PAM) apresentam melhores soluções quanto às silhuetas, frente aos algoritmos de Detecção de Comunidades em redes (Fast Greedy e Walktrap).

Palavras-chave:

DOI: 10.5151/spolm2019-203

Referências bibliográficas

• [1] JAIN, A.; DUBES, R. Algorithms for Clustering Data. Prentice Hall. 1988. [2] KUMAR, V.; STEINBACH, M.; TAN, P. N. Introdução ao Data Mining – Mineração de Dados. Ciência Moderna. 2009. [3] HAN, J.; KAMBER, M.; PEI, J. Data Mining: Concepts and Techniques: Concepts and Techniques. The Morgan Kaufmann Series in Data Management Systems. Elsevier Science, 2012. [4] TEIXEIRA, L. S.; LIMA, L. S.; ABREU, N. M. M. Grafos que modelam redes confiáveis. In: XL SBPO: A Pesquisa Operacional e o uso racional de recursos hídricos. João Pessoa, PB, Brasil, 2008. [5] COSTA, J. M. S.; TEIXEIRA, P. M.; BARBASTEFANO, R. G.; SOUZA, C. G.; LIMA, L. S. Aplicação da análise de redes sociais em uma rede de publicações sobre gestão da cadeia de suprimentos. In: XXXIII Encontro Nacional de Engenharia de Produção, Bahia, 2013. [6] MENTZ, J.; CALVO, R.; SENO, E. R. M.; ROMERO, R. A. F.; LIANG, Z. Redes Complexas: Conceitos e aplicações. Instituto de Ciências Matemáticas e de Computação. Relatório Técnico, n. 290, 2007. [7] MOORI, R. G.; MARCONDES, R. C.; AVILA, R. T. A análise de agrupamentos como instrumento de apoio à melhoria da qualidade dos serviços aos clientes. Rev. adm. contemp. [online]. vol.6, n.1, pp. 63-84, ISSN 1982-7849, 2002. [8] SANTOS, M.; GUIZZO, C. S. P.; SAMPAIO, R. R.; CORDEIRO, A. J. A. Aplicação da análise de agrupamento na avaliação da formação técnica profissionalizante para o setor industrial. XVLI Simpósio brasileiro de pesquisa operacional, Bahia, 2014. [9] HAMMOUDA, K. M. “Web Mining: Identifying Document Structure for Web Document Clustering”, Tese de Mestrado, Department of Systems Design Engineering, University of Waterloo, Canada, 2002. [10] HANSEN, P.; JAUMARD B. Cluster Analysis and Mathematical Programming, Mathematical Programming, 1997. [11] NALDI, M. C. Técnicas de combinação para agrupamento centralizado e distribuído de dados. Tese de doutorado, USP, 2011. [12] LIU, C. L. Introduction to Combinatirial Mathematics (Computer Science Sereies). Mcgraw-Hill College. 1968. [13] BRITO, J.A.M.; SEMAAN, G.S.; BRITO, L. R. Resolução do Problema dos kmedoids Via Algoritmo Genético de Chaves Aleatórias Viciadas. In: XVIII Simpósio de Pesquisa Operacional e Logística da Marinha (SPOLM), Rio de Janeiro, 2015. [14] KAUFMAN, L.; ROUSSEEUW, P. J. An introduction to cluster analysis. John Wiley and Sons. 1990. [15] ALVES, I.; OLIVEIRA, C. S.; BRITO, J. A. M. Um estudo do problema de detecção de comunidades em redes. Revista Eletrônica Sistemas & Gestão, v. 9 n. 4, pp. 566- 576, 2014. [16] CRUZ, M. D. O problema de Clusterização Automática. Tese de Doutorado, COPPE/ UFRJ, Rio de Janeiro, RJ, Brasil, 2010. [17] OLIVEIRA, T. B. S. Cluserização de dados utilizando técnicas de redes complexas e computação bioinspirada Dissertação de mestrado -Instituo de Ciências Matemática e de Computação - USP, São Carlos -SP, 2008. [18] ROUSSEUW, P. J. Silhouetts: A grafical aid to the interpretation and validation of cluster analysis. Journal of Computatuinal and Applied Mathematics, 20(1):53-65. 1987. [19] SILVA, L. F. Uma Análise Híbrida Para Detecção De Anomalias Da Mama Usando Séries Temporais De Temperatura. Tese de Doutorado em Computação. Universidade Federal Fluminense, Niterói, 2015. [20] FILHO, J. A. A. Definição Automática da Quantidade de Atributos Selecionados em Tarefas de Agrupamento de Dados. Tese de Doutorado em Ciências. Instituto de Ciências Matemáticas e de Computação-ICMC-USP, São Carlos, 2013. [21] NEWMAN, M. E. J.; GIRVAN, M. Finding and evaluating community structure in networks. Physical Review E, 69(026113), 2004. [22] KARGER, D. Minimum cuts in near-linear time. Journal of the ACM (JACM), v. 47, n. 1, p. 46-76, 2000. [23] KERNIGHAN, B.; LIN, S. An efficient heuristic procedure for partitiong graphs. Bell System Technical Journal, v. 49, n. 2, p.291-307, 1970. [24] FIDUCCIA, C.; MATTHEYSES, R. M. “A linear-time heuristic for improving network partitions”,In: 19th IEE Conference on Design Automation, 1982. [25] LINARES, O. A. C. Segmentação de Imagens de altadimensão por meio de algortimos de detecção de comunidades e super pixels. Dissertação de Mestrado, Instituto de Ciência Matemáticas e de Computação – ICMC - USP, São Carlos, 2013. [26] CLAUSET, A.; NEWMAN, M. E., MOORE, C. “Finding community structure in very large networks”, Physical Review E., Vol 70, N º 6, 2004. [27] BOTELHO, G. M.; SOUSA, F. B. Comparação de Algoritmos de Detecção de Comunidades em Redes Complexas. Instituto de Ciências Matemáticas e de Computação São Carlos - SP – Brasil. Universidade de São Paulo (USP). Disponível em:< http://wiki.icmc.usp.br/images/8/81/Trabalho2GlendaFabiano.pdf > . Acessado em: 25 ago. 2015. [28] PONS, P.; LATAPY, M. Computing communities in large networks using random walks. J. Graph Algorithms Appl., v. 10, n. 2, p. 191–218, 2006. [29] PORTO, S. M. Metodologia para a Evolução de Comunidades em Redes Complexas Dinâmicas. Dissertação de M.Sc., Instituto Nacional de Pesquisas Espaciais, São José dos Campos, 2014. [30] QIU, W.; JOE, H. Generation of random groups with specified degree of separation. Journal of Classification, v. 23, n. 2, p. 315-334, 2006.

Como citar:

Silva, Daiana Medeiros da; Brito, José André de Moura; Oliveira, Carla Silva; "UM ESTUDO COMPUTACIONAL COMPARATIVO ENTRE ALGORITMOS DE AGRUPAMENTO E DE DETECÇÃO DE COMUNIDADES", p-2808-2822. In: Anais do XIX Simpósio de Pesquisa Operacional & Logística da Marinha. São Paulo: Blucher, 2020.
ISSN 21756295, DOI 10.5151/spolm2019-203