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

Let $L$ be the discrete Laplacian associated to an undirected graph. It is well-known that the spectral gap of $L$, i.e. the smallest nonzero eigenvalue, is a measure of how well connected the graph is; the smaller the spectral gap, the fewer cuts are needed to disconnect the graph.

I have observed experimentally that the number of "small" eigenvalues corresponds to the number of "loosely connected clusters" in the graph. For example, take four graphs A, B, C, D, each with four vertices, such that every vertex is connected to every other vertex within each of the four graphs. Then form a single connected graph G by connecting a vertex in A to a vertex in B, a vertex in B to a vertex in C, and a vertex in C to a vertex in D. The first few eigenvalues of the Laplacian of G are:

0, .1126, .3542, .5688, 4, 4,...

I suspect that if this observation were formulated correctly then it would not be hard to turn into a theorem, but if anyone happens to know a reference I would appreciate it. My main question is: can one formulate a quantitative version of my observation? In other words if I give you the spectrum of the Laplacian of a graph, can you tell me how many "loosely connected clusters" there are in the graph? I don't want to commit to any precise meaning of the phrase "loosely connected clusters"; I'm hoping for answers that include an appropriate definition.

share|improve this question
    
I'll quote from section IV.D of arxiv.org/abs/0906.0612: "If the graph is connected, but consists of $k$ subgraphs which are weakly linked to each other...the lowest $k-1$ non-vanishing eigenvalues are still close to zero..." –  Steve Huntsman Jul 11 '13 at 20:09
add comment

1 Answer

The magic words are "Cheeger's inequality" (for which a good reference is Sarnak's "Some applications of modular forms", or Fan Chung's book on spectral graph theory).

EDIT

You can also google for "Graph spectral partition and clustering", which beats this problem halfway into the ground.

share|improve this answer
    
Cheeger's inequality as I know it is formulated just for the second eigenvalue; I guess my question can be summarized as: is there a counterpart of Cheeger's inequality for larger eigenvalues? –  Paul Siegel Jul 11 '13 at 20:24
1  
Cheeger's inequality comes from the variational characterization of eigenvalues, which works for ALL eigenvalues, not just the smallest ones (you just have to go to orthogonal complements), so you can do this iteratively. –  Igor Rivin Jul 11 '13 at 20:51
    
Also, see the edit.. –  Igor Rivin Jul 11 '13 at 20:54
    
but beware: a tightly related notion is that of faber-krahn inequality (roughly stating that among all domains in a certain class the ball is the one with the lowest second eigenvalue). similar assertions exist also for higher eigenvalues, but are much less reliable as one would expect - in the sense that there seems to be no direct relation between k-th minimization problems and k-connectivity: see e.g. arxiv.org/abs/0910.3966 –  Delio Mugnolo Jul 12 '13 at 9:46
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.