Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11422/18161
Tipo: Trabalho de conclusão de graduação
Título: Análise da regularidade estrutural de redes complexas através de particionamento em estrelas
Título(s) alternativo(s): Analysis of the structural regularity of complex networks through star partitioning
Autor(es)/Inventor(es): Andrade, Matheus Guedes de
Orientador: Figueiredo, Daniel Ratton
Resumo: 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.
Palavras-chave: Complexidade Estrutural
Entropia de Redes
Assunto CNPq: CNPQ::ENGENHARIAS
Unidade produtora: Escola Politécnica
Editora: Universidade Federal do Rio de Janeiro
Data de publicação: Mar-2018
País de publicação: Brasil
Idioma da publicação: por
Tipo de acesso: Acesso Aberto
Aparece nas coleções:Engenharia de Computação e Informação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
monopoli10024245.pdf771.79 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.