Um algoritmo eficiente para estimar os momentos espectrais de grafos grandes não dirigidos com pesos

• Ano de defesa: 2020
• Autor(a) principal: Oliveira, Gustavo Dias de
• Orientador(a): Kashiwabara, Andre Yoshiaki
• Banca de defesa: Kashiwabara, Andre Yoshiaki , Lopes, Fabricio Martins , Barbon Junior, Sylvio
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Tecnológica Federal do Paraná; Cornelio Procopio
• Programa de Pós-Graduação: Programa de Pós-Graduação em Informática
• País: Brasil
• Palavras-chave em Português: Teoria dos grafos; Análise espectral; Representações dos grafos; Graph theory; Spectrum analysis; Representations of graphs
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.utfpr.edu.br/jspui/handle/1/5424

Um grafo se caracteriza por um conjunto de vértices e um conjunto arestas, cada uma dela conectando dois vértices. Os momentos espectrais de um grafo são utilizados para caracterizar a topologia do grafo. Os algoritmos para calcular os momentos espectrais, em geral, caracterizam-se por ter complexidade de ordem cubica, o que inviabiliza o cálculo para grafos grandes na escala de milhões de nós, por demandar um tempo de processamento computacional muito grande. Este trabalho apresenta uma adaptação do algoritmo, descrito por Cohein-Steiner, para grafos não dirigidos com pesos. O algoritmo devolve um resultado baseado em uma aproximação com diferença na quarta casa decimal, mas que ainda possa ser utilizado para caracterizar o grafo. O mesmo calculou os momentos para um grafo com mais de 800 mil nos em menos de 2,5 segundos. Esta implementação consiste em apresentar uma solução para calcular os momentos espectrais de grandes grafos em um tempo de processamento computacional viável. Dessa forma, a solução proposta e viável para aplicações em problemas que se possa utilizar este algoritmo em problemas de reconhecimento de padrões. Na implementação, foram feitas adaptações no algoritmo, melhorando para um consumo de tempo próximo à complexidade constante O(1).