Say I have a graph with 10 million nodes and 100 million edges. I would like to compute the largest Eigen value on the adjacency matrix of this graph. Which Eigen value solvers should work for the graph this big. Note that the matrix is sparse.
You can use Arpack [1], it requires just a function that computes a matrix-vector product (thus it works well for sparse matrices).
Arpack has different operating modes, for computing either the high frequencies (small eigenvalues) or the low frequencies (large eigenvalues). Unfortunately, it works in general much faster for the high frequencies, but what you can do is pre-factoring your matrix using a sparse LU factorization algorithm, e.g., SuperLU [2], then compute the high frequencies of M^-1, by solving a linear system instead of computing the sparse matrix vector product, then the eigenvalue is just the inverse of the one computed by Arpack.
I tryed that with meshes with tenths of million nodes, and it works quite well. Details are in my article [3] and companion source-code [4]
References:
[1] http://www.caam.rice.edu/software/ARPACK/
[2] http://crd-legacy.lbl.gov/~xiaoye/SuperLU/
[3] http://alice.loria.fr/index.php/publications.html?redirect=0&Paper=ManifoldHarmonics@2007
[4] http://alice.loria.fr/WIKI/index.php/Graphite/ManifoldHarmonics