Análise estrutural de redes complexas modulares por meio de caminhadas auto-excludentes

• Ano de defesa: 2018
• Autor(a) principal: Bagnato, Guilherme de Guzzi
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Caminhada aleatória; Communities; Complex networks; Comunidades; Random walks; Redes complexas
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/76/76132/tde-21062018-152327/

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 o parâ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.