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.
Best 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.