Use este identificador para citar ou linkar para este item: http://repositorio.roca.utfpr.edu.br/jspui/handle/1/11692
Título: Exploração do comportamento de um algoritmo combinatório para o particionamento de grafos núcleo-periferia
Título(s) alternativo(s): An exploration on the behaviour of a combinatorial algorithm for core-periphery graph partitioning
Autor(es): Rodriguez, Henrique Antunes
Orientador(es): Giménez-Lugo, Gustavo Alberto
Palavras-chave: Teoria dos grafos
Algoritmos
Análise combinatória
Graph theory
Algorithms
Combinatorial analysis
Data do documento: 15-Jun-2018
Editor: Universidade Tecnológica Federal do Paraná
Câmpus: Curitiba
Referência: RODRIGUEZ, Henrique Antunes.“An exploration on the behaviour of a combinatorial algorithm for core-periphery graph partitioning". 2018. 37 f. Trabalho de Conclusão de Curso (Bacharelado em Sistemas de Informação) - Universidade Tecnológica Federal do Paraná, Curitiba, 2018.
Resumo: A maioria das redes reais de larga escala apresenta uma estrutura topológica que pode ser particionada em duas subestruturas, o Núcleo e a Periferia. Quando tal particionamento é realizado, uma análise do comportamento do núcleo pode ser extrapolada para se obter uma compreensão do comportamento de toda a rede. Devido à sua confiabilidade, os algoritmos espectrais até o momento dominam o campo de estudo quando se trata de identificar o núcleo de uma rede; entretanto, os algoritmos espectrais executam cálculos muito complexos, que são computacionalmente caros e educacionalmente complicados. Este estudo é uma exploração da maneira como um algoritmo, baseado em uma abordagem não-spectral, se comporta quando testado em um conjunto de grafos com estruturas variadas, tentando determinar se ele poderia ser uma alternativa viável, simples e rápida aos complexos e caros algoritmos atualmente dominando este assunto.
Abstract: Most real life large-scale networks present a topological structure that can be partitioned into two substructures, the Core and the Periphery. When such a partitioning is achieved, an analysis of the behaviour of the core can be extrapolated to obtain an understanding of the behaviour of the entire network. Due to their reliability, spectral algorithms have so far dominated the field of study when it comes to identifying the core of a network; however, spectral algorithms perform very complex computations, which are computationally expensive, and educationally complicated. This study is an exploration into the way an algorithm, based on a non-spectral approach, would perform when tested on a set of graphs with varied structures, attempting to determine whether it could be a viable, simple, and fast alternative to the complex and costly algorithms currently dominating this subject.
URI: http://repositorio.roca.utfpr.edu.br/jspui/handle/1/11692
Aparece nas coleções:CT - Sistemas de Informação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
CT_COSIS_2018_1_04.pdf1,04 MBAdobe PDFVisualizar/Abrir


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