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

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorKashiwabara, Andre Yoshiaki-
Autor(es): dc.contributor0000-0003-3280-2035-
Autor(es): dc.contributorhttp://lattes.cnpq.br/3194328548975437-
Autor(es): dc.contributorKashiwabara, Andre Yoshiaki-
Autor(es): dc.contributorhttp://lattes.cnpq.br/3194328548975437-
Autor(es): dc.contributorLopes, Fabricio Martins-
Autor(es): dc.contributorhttp://lattes.cnpq.br/1660070580824436-
Autor(es): dc.contributorBarbon Junior, Sylvio-
Autor(es): dc.contributorhttp://lattes.cnpq.br/8086324432194233-
Autor(es): dc.creatorOliveira, Gustavo Dias de-
Data de aceite: dc.date.accessioned2022-02-21T22:22:43Z-
Data de disponibilização: dc.date.available2022-02-21T22:22:43Z-
Data de envio: dc.date.issued2020-11-02-
Data de envio: dc.date.issued2020-11-02-
Data de envio: dc.date.issued2020-08-13-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/5424-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/673811-
Descrição: dc.descriptionA graph is a collection of vertexes and edges, each one connecting two vertexes. We can use the spectral moments to characterize the topology of the graph. The algorithms that calculate the spectral moments have a cubic-order complexity, a fact that makes it unfeasible for large graphs with millions of nodes because it demands a considerable computational processing time. This work presents an adaption of the algorithm, described by Cohein-Steiner, for undirected weighted graphs. The algorithm returns a result based on an approximation with difference on the forth demail place, that can still be used to characterize the graph. This one calculated the moments for a graph with more than 800 thousands of nodes in less than 2.5 seconds. This implementation consists in presenting a solution for calculating the spectral moments of large graphs in feasible computational processing time, that makes able to use this algorithm in pattern recognizing problems. On the implementation, some adaptions were made on the algorithm, improving for a runtime close to O(1).-
Descrição: dc.descriptionUm 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).-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Tecnológica Federal do Paraná-
Publicador: dc.publisherCornelio Procopio-
Publicador: dc.publisherBrasil-
Publicador: dc.publisherPrograma de Pós-Graduação em Informática-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Palavras-chave: dc.subjectTeoria dos grafos-
Palavras-chave: dc.subjectAnálise espectral-
Palavras-chave: dc.subjectRepresentações dos grafos-
Palavras-chave: dc.subjectGraph theory-
Palavras-chave: dc.subjectSpectrum analysis-
Palavras-chave: dc.subjectRepresentations of graphs-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO-
Palavras-chave: dc.subjectCiência da Computação-
Título: dc.titleUm algoritmo eficiente para estimar os momentos espectrais de grafos grandes não dirigidos com pesos-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.