Detecção de comunidades em redes complexas utilizando estratégia multinível (2009)
- Authors:
- Autor USP: ALMEIDA, LEONARDO JESUS - ICMC
- Unidade: ICMC
- Subjects: INTELIGÊNCIA ARTIFICIAL; REDES COMPLEXAS
- Language: Português
- Abstract: O grande volume de dados armazenados em meio digital dificulta a análise e extração de informações por um ser humano sem que seja utilizada alguma ferramenta computacional inteligente. A área de Aprendizado de Máquina (AM) estuda e desenvolve algoritmos para o processamento e obtenção automática de conhecimento em dados digitais. Tradicionalmente, os algoritmos de AM modelam os dados analisados com base na abordagem proposicional; entretanto, recentemente com a disponibilidade de conjuntos de dados relacionais novas abordagens têm sido estudadas, como a modelagem utilizando redes complexas. Redes complexas é uma área de pesquisa recente e ativa que têm atraído a atenção de pesquisadores e tem sido aplicada em diversos domínios. Mais especificamente, o estudo de detecção de comunidades em redes complexas é o tema principal deste trabalho. Detectar comunidades consiste em buscar grupos de vértices densamente conectados entre si em uma rede. Detectar a melhor divisão em comunidades deuma rede é um problema NP-completo, o que requer que o desenvolvimento de soluções viáveis baseiem-se em heurísticas como, por exemplo, medidas de qualidade. Newman propôs a medida de modularidade Q que tem se mostrado eficiiente na análise de comunidades em redes. Este trabalho apresenta o Algoritmo Multinível de Otimização de Modularidade (AMOM) que é baseado a na otimização da medida de modularidade e integrado na estratégia multinível. A estratégia multinível é composta detrês fases: (i) sucessivas compactações da rede inicial com base em contrações de arestas e fusões de vértices, (ii) particionamento da rede reduzida utilizando Algoritmo de Otimização de Modularidade (AOM) modificado, e (iii) sucessivas descompactações das redes intermediárias até que se retorne a rede inicial. O principal atrativo da estratégia é viabilizar a utilização de algoritmos custosos no particionamento do grafo compactado, uma ) vez que neste grafo a quantidade de vértices e arestas é uma fração reduzida em relação ao grafo inicial. O trabalho também propõe dois novos métodos para refinamento dos particionamantos durante a fase de uncoasening. A fim de avaliar a escalabilidade e eficiência da metodologia proposta foram realizados experimentos empíricos em redes consideradas benchmark. Os resultados demonstram um significativo ganho de desempenho, mantendo bons resultados qualitativos
- Imprenta:
- Publisher place: São Carlos
- Date published: 2009
- Data da defesa: 05.10.2009
-
ABNT
ALMEIDA, Leonardo Jesus. Detecção de comunidades em redes complexas utilizando estratégia multinível. 2009. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2009. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-29032010-161550/. Acesso em: 31 out. 2024. -
APA
Almeida, L. J. (2009). Detecção de comunidades em redes complexas utilizando estratégia multinível (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-29032010-161550/ -
NLM
Almeida LJ. Detecção de comunidades em redes complexas utilizando estratégia multinível [Internet]. 2009 ;[citado 2024 out. 31 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-29032010-161550/ -
Vancouver
Almeida LJ. Detecção de comunidades em redes complexas utilizando estratégia multinível [Internet]. 2009 ;[citado 2024 out. 31 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-29032010-161550/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
