Detalhes bibliográficos
| Ano de defesa: |
2009 |
| Autor(a) principal: |
Almeida, Leonardo Jesus |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Biblioteca Digitais de Teses e Dissertações da USP
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
http://www.teses.usp.br/teses/disponiveis/55/55134/tde-29032010-161550/
|
Resumo: |
O grande volume de dados armazenados em meio digital dificulta a anáalise 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íido 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 de uma 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^os 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 de três fases: (i) sucessivas compactações da rede inicial com base em contrações de arestas e fus~oes 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 particionamentos durante a fase de uncoasening. A fiim de avaliar a escalabilidade e eficiiê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 |
