Randomized Algorithms For Evaluating Energy Of Large-Scale Graph

Graph energy is defined as the sum of the absolute values of all the eigenvalues of an adjacency matrix.It has strong background in many applications such as graph theory,quantum chemistry,complex network analysis and large-scale scientific computation.Now it has been a hot topic in many areas.However,to the best of our knowledge,almost all the researches focus on establishing lower or upper bounds for graph energy.And there are few efficient algorithms for computing graph energy,especially for extremely large-scale graphs.Our aim is to give an estimation which is as the same order of the ’real’ graph energy.The main contribution of this work is as follows.First,based on the assumption that most adjacency matrices are of low-rank,we propose a randomized algorithm relying on randomized singular value decomposition(RSVD).However,the number of the sampling(or the target rank)for a given adjacency matrix is difficult to determine in advance.Second,in order to improve the accuracy of our evaluation,we then propose a ’non-restarted’ algorithm which updates the columns of orthogonal matrix incrementally.The error analysis and the convergence of the algorithm is given.Unfortunately,this algorithm may suffer from the computational overhead and storage requirements as the iteration proceeds.Third,so as to cure the drawback of the non-restarted algorithm,we then propose a ’restarted’algorithm for evaluating energy of large-scale graph.The rationally of the proposed algorithm is given.All the algorithms presented in the paper can be utilized to estimating the energy of large-scale directed graphs and undirected graphs.Specifically,the restarted and non-restarted algorithms successfully apply to graphs with millions of nodes.Numerical experiment show the rationality of our strategies and illustrate the superiority of our proposed algorithms.