A Restarted and Randomized Algorithm for Evaluating Energy of Extremely Large-Scale Graph

Abstract

Graph energy is a spectrum-based graph invariant that has been studied extensively in network sciences. However, as far as we are aware, most of the existing works try to establish theoretical bounds, and there are few efficient algorithms for computing energy of extremely large-scale graph. To fill-in this gap, we first propose a randomized algorithm for evaluating energy of large-scale graphs, under the assumption that the adjacency matrix is approximately low (numerical) rank. However, the number of sampling used in this algorithm is difficult to determine in advance, and the graph energy is often underestimated. In order to improve the quality of the evaluation, we then propose a non-restarted randomized algorithm that updates the columns of the search basis incrementally. The error analysis and the convergence of the algorithm are established. However, the non-restarted algorithm may suffer from heavy overhead as the iteration proceeds. So as to release the overhead of the non-restarted algorithm, we finally propose a restarted randomized algorithm for evaluating energy of extremely large-scale graphs. The rationality of the restarted algorithm is given. Extensive numerical experiments are performed on extremely large-scale real-world and synthetic graphs, to show the effectiveness of our strategies and efficiency of the proposed algorithms.