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

Abstract

A 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).