8
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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..." $\endgroup$
    – Steve Huntsman
    Commented Jul 11, 2013 at 20:09

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Paul Siegel
    Commented Jul 11, 2013 at 20:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – Igor Rivin
    Commented Jul 11, 2013 at 20:51
  • $\begingroup$ Also, see the edit.. $\endgroup$
    – Igor Rivin
    Commented Jul 11, 2013 at 20:54
  • $\begingroup$ 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 $\endgroup$
    – Delio Mugnolo
    Commented Jul 12, 2013 at 9:46
  • $\begingroup$ This question and answer are a bit old, but I just want to remark that it is not really accurate to say that one can produce higher Cheeger inequalities by iterating the proof of the usual Cheeger inequality. For one, it is not easy to give a good combinatorial description of the $k$th eigenvector and thus it is not easy to describe the set over which one hopes to minimize the Rayleigh quotients for the Laplacian. Additionally, it is not obvious (and I think not completely resolved) what the lower bound for $\lambda_k$ should be. $\endgroup$
    – Paul Siegel
    Commented Jul 9, 2014 at 19:32
3
$\begingroup$

It seems that this is a rather difficult problem, some aspects of which are still open. Upon further research I think the best answer currently available is in this paper: http://arxiv.org/abs/1111.1055

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .