Análise da regularidade estrutural de redes complexas através de particionamento em estrelas

Andrade, Matheus Guedes de

Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/18161

Type:	Trabalho de conclusão de graduação
Title:	Análise da regularidade estrutural de redes complexas através de particionamento em estrelas
Other Titles:	Analysis of the structural regularity of complex networks through star partitioning
Author(s)/Inventor(s):	Andrade, Matheus Guedes de
Advisor:	Figueiredo, Daniel Ratton
Abstract:	A análise de Redes Complexas é fundamental para o entendimento de fenômenos observados por pesquisadores em diversas áreas da ciência. Nessa perspectiva, o relacionamento latente entre as características topológicas das redes com as propriedades dos fenômenos observados surge como fator chave. Dentre os diversos aspectos topológicos que aparecem como alicerce para o entendimento desses fenômenos, a regularidade topológica da rede é, por vezes, foco de observação. No âmbito citado, o uso de uma adaptação da entropia de von Neumann, inicialmente definida para misturas de estados quânticos, é comumente utilizada para descrever a regularidade de uma topologia, oferecendo uma base de comparação entre redes distintas. Não obstante, o cálculo dessa métrica é custoso em termos computacionais, dado que depende da obtenção de autovalores de matrizes. Em efeito, quando os objetos de estudo são redes de tamanho elevado, calcular diretamente essa entropia é, em geral, impraticável. Este trabalho propõe uma alternativa computacionalmente viável para obter uma aproximação da entropia de von Neumann através de particionamentos da rede. De forma direta, o método descrito consiste em decompor o grafo que representa a rede original em subgrafos estrela e utilizar o particionamento resultante para obter possíveis limitantes superiores e inferiores para a métrica em questão. A contribuição deste trabalho consiste na formalização matemática que embasa a obtenção destes limitantes, na descrição de algoritmos para o específico particionamento de grafos em estrelas e na análise experimental dos limitantes subsequentes, nos quesitos de efetividade de aproximação e de tratabilidade computacional para redes grandes.
Keywords:	Complexidade Estrutural Entropia de Redes
Subject CNPq:	CNPQ::ENGENHARIAS
Production unit:	Escola Politécnica
Publisher:	Universidade Federal do Rio de Janeiro
Issue Date:	Mar-2018
Publisher country:	Brasil
Language:	por
Right access:	Acesso Aberto
Appears in Collections:	Engenharia de Computação e Informação

Files in This Item:

File	Description	Size	Format
monopoli10024245.pdf		771.79 kB	Adobe PDF	View/Open

Show full item record Recommend this item View Statistics

Pantheon Institutional repository