Eigenvalue computation for large graph
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.