Análise estrutural de redes complexas modulares por meio de caminhadas auto-excludentes (2018)
- Authors:
- Autor USP: BAGNATO, GUILHERME DE GUZZI - IFSC
- Unidade: IFSC
- Sigla do Departamento: FCM
- Subjects: REDES COMPLEXAS; SIMULAÇÃO
- Keywords: Caminhada aleatória; Communities; Complex networks; Comunidades; Random walks
- Agências de fomento:
- Language: Português
- Abstract: O avanço das pesquisas em redes complexas proporcionou desenvolvimentos significativos para a compreensão de sistemas complexos. Uma rede complexa é modelada matematicamente por meio de um grafo, onde cada vértice representa uma unidade dinâmica e suas interações são simbolizadas por um conjunto de arestas. Para se determinar propriedades estruturais desse sistema, caminhadas aleatórias tem-se mostrado muito úteis pois dependem apenas de informações locais (vértices vizinhos). Entre elas, destaca-se o passeio auto-excludente (SAW) que possui a restrição de não visitar um vértice que já foi alcançado, ou seja, apresenta memória do caminho percorrido. Por este motivo o SAW tem apresentado melhores resultados do que caminhantes sem restrição, na exploração da rede. Entretanto, por não se tratar de um processo Markoviano ele apresenta grande complexidade analítica, tornando indispensável o uso de simulações computacionais para melhor compreensão de sua dinâmica em diferentes topologias. Mesmo com as dificuldades analíticas, o SAW se tornou uma ferramenta promissora na identificação de estruturas de comunidades. Apesar de sua importância, detecção de comunidades permanece um problema em aberto devido à alta complexidade computacional associada ao problema de optimização, além da falta de uma definição formal do significado de comunidade. Neste trabalho, propomos um método de detecção de comunidades baseado em SAW para extrair uma estrutura de comunidades da rede otimizando oparâmetro modularidade. Combinamos características extraídas desta dinâmica com a análise de componentes principais para posteriormente classificar os vértices em grupos por meio da clusterização hierárquica aglomerativa. Para avaliar a performance deste novo algoritmo, comparamos os resultados com outras quatro técnicas populares: Girvan-Newman, Fastgreedy, Walktrap e Infomap, aplicados em dois tipos de redes sintéticas e nove redes reais diversificadas e bem conhecidas. Para os benchmarks, esta nova técnica produziu resultados satisfatórios em diferentes combinações de parâmetros, como tamanho de rede, distribuição de grau e número de comunidades. Já para as redes reais, obtivemos valores de modularidade superior aos métodos tradicionais, indicando uma distribuição de grupos mais adequada à realidade. Feito isso, generalizamos o algoritmo para redes ponderadas e digrafos, além de incorporar metadados à estrutura topológica a fim de melhorar a classificação em grupos
- Imprenta:
- Publisher place: São Carlos
- Date published: 2018
- Data da defesa: 27.04.2018
-
ABNT
BAGNATO, Guilherme de Guzzi. Análise estrutural de redes complexas modulares por meio de caminhadas auto-excludentes. 2018. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2018. Disponível em: http://www.teses.usp.br/teses/disponiveis/76/76132/tde-21062018-152327/. Acesso em: 12 nov. 2024. -
APA
Bagnato, G. de G. (2018). Análise estrutural de redes complexas modulares por meio de caminhadas auto-excludentes (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/76/76132/tde-21062018-152327/ -
NLM
Bagnato G de G. Análise estrutural de redes complexas modulares por meio de caminhadas auto-excludentes [Internet]. 2018 ;[citado 2024 nov. 12 ] Available from: http://www.teses.usp.br/teses/disponiveis/76/76132/tde-21062018-152327/ -
Vancouver
Bagnato G de G. Análise estrutural de redes complexas modulares por meio de caminhadas auto-excludentes [Internet]. 2018 ;[citado 2024 nov. 12 ] Available from: http://www.teses.usp.br/teses/disponiveis/76/76132/tde-21062018-152327/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
