Here's a [reference about how the laplacian matrix relates to graph connectivity](http://www.math.pku.edu.cn/teachers/yaoy/Fall2011/lecture08.pdf). I'll try to write some more later, but one of the important things is that some characteristics of graphs are encoded in specific (eignvector, eigenvalue) positions in the ordered list of eigenvalues. So the second smallest eigenvalue is related to connectivity of the graph.
The use of random walks is, as I understand it, more for computiational purposes on graphs the size of billions or trillions of nodes that people like Google and Facebook work with.
I was in a bit of a rush and you're right matrix spectra are well-defined; what I was thinking was that diagonally dominant matrices are more well-behaved.
Try to right more later.