Is there an easy way to compute the second smallest eigenvalue in question if the graph is large?

There is a well-known theorem that quickly computes the smallest eigenvalue if the graph is bipartite, but I'm not aware of any generalization (which may be quite useful for some results in econometrics).

I recently found this paper: "Hearing the clusters in a graph: A distributed algorithm" http://arxiv.org/abs/0911.4729

Wish I had some data to apply it too :-)

It's been a while since I've done work in this area but you might want to lookup Lanzcos Algorithm [1].

[1]:http://en.m.wikipedia.org/wiki/Lanczos_algorithm

I love graph theory. Neat writeup!