Eigenvalue computation for large graph

Question

Consider a large graph, minimum 1 000 vertices but it can easily go up to 50 000 vertices depending the case. The graph is the result of social relationships (followers, following, friendship) so it can be oriented but for the ease of the solution let's say it's not, so the matrix is symmetric. Moreover the matrix of adjacency is highly sparse.

I need to calculate the eigenvalues, but the major problem as I see it is that computing eigenvalues for large adjacency matrices cost a lot on time complexity due to matrices operations. If I can't efficiently compute all the eigenvalues, even a method to find the largest eigenvalue would be nice.

I've searched through the literature in vain, is there an algorithm or other approach to solve this?

Answer 1

There are many methods for computing the eigenvalues of a matrix.

If you just want the largest eigenvalue, the power method is an efficient way to do that, as Yuval suggests. Typically the power method takes $O(n)$ time to find (an approximation to) the largest eigenvalue of a $n \times n$ matrix, if the matrix is sparse (it has $O(1)$ non-zero entries per row), with a constant of proportionality that depends on the matrix (and specifically on the value of $|\lambda_1/\lambda_2|$).

A generalization is the Lanczos algorithm, which lets you find the top $k$ eigenvalues in a sparse Hermitian matrix in $O(kn)$ time, with a constant of proportionality that depends on the matrix. Arnoldi iteration is a generalization to non-Hermitian matrices.

If you want to find all eigenvalues, there are multiple methods. The QR algorithm has $O(n^3)$ running time, though it doesn't take advantage of the sparsity of your matrix. Arnoldi iteration can apparently be used to find all eigenvalues, or the $k$ largest eigenvalues, but I don't know what its asymptotic running time is. There are apparently also software libraries that support eigenvalue computation on sparse matrices, e.g., Eigen, ARPACK, SuperLU, Spectra, OpenNL. I have no experience with them and cannot recommend one.

For more you might check Computational Science.SE, e.g., https://scicomp.stackexchange.com/questions/tagged/sparse+eigenvalues.