Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Most of what I've seen about the spectral theory of the graph Laplacian concentrates on $\lambda_2$, the second-smallest eigenvalue. This eigenvalue contains information regarding the connectivity of the graph.

What can one learn from the rest of the eigenvalues and their associated eigenvectors? I'm not interested in special graphs -- e.g. regular graphs -- but large, messy graphs created from data.

share|improve this question
4  
John, are you familiar with, say, U. von Luxburg (2007), A tutorial on spectral clustering, Statistics and Computing, vol. 17, no. 4? If I recall (though I don't have it handy), there is at least one chapter of D. Skillicorn, Understanding Complex Datasets: Data Mining with Matrix Decompositions, Chapman and Hall/CRC, 2007 that discusses some high-level aspects, as well. –  cardinal Jul 15 '13 at 18:50
    
Thanks! I am not familiar with those references. –  John D. Cook Jul 15 '13 at 18:57
1  
For the more mathematical point of view, see the recent survey arxiv.org/abs/1111.2897 by X.-D. Zhang. A classical way to infer something from the whole ensemble of eigenvalues is to take the product $\frac{\lambda_{2} \ldots \lambda_{n}}{n}$ which counts the spanning trees... –  Felix Goldberg Jul 15 '13 at 19:02
1  
"The third largest eigenvalue roughly measures how hard it is to cut the graph into distinct pieces." --Leanne R. Silvia & Gary E. Davis –  Joseph O'Rourke Jul 15 '13 at 19:07
3  
I recently asked a related question: mathoverflow.net/questions/136434/… –  Paul Siegel Jul 15 '13 at 21:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.