# Small eigenvalues and spectral clustering

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.

-
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 at 20:09