Pantheon Repositório Institucional da UFRJ
Coleta, preserva e divulga a produção acadêmica digital em todas as áreas do conhecimento.
São os ativos do repositório, além de teses e dissertações da UFRJ, artigos científicos, livros eletrônicos, capítulos de livros e trabalhos apresentados em eventos por professores, pesquisadores, funcionários administrativos e alunos de mestrado e doutorado.
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 | Tamanho | Formato | |
|---|---|---|---|---|
| monopoli10024245.pdf | 771.79 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.