16
$\begingroup$

I'm reading Fan Chung's Spectral Graph Theory, and I'm now in chapter 2. There, Chung proves Cheeger's inequality, which is that $2h_G \geq \lambda_1 > h_G^2/2$ for any graph $G$. To me, this inequality raises the question of a physical interpretation of $\lambda_1$ and I'm wondering if such an interpretation exists. Below, I'll explain this terminology and ask my question a little more precisely.

Let $G$ be a graph with vertex set $V$, with $\#V =n$. The Laplacian of $G$ is the $n\times n$ matrix $\mathcal{L}$ whose $(u,v)^{\text{th}}$ entry is $\text{deg}(v)$ if $u=v$, $-(\text{deg}(u)\text{deg}(v))^{-1/2}$ if $u$ and $v$ are adjacent vertices, and $0$ otherwise. The eigenvalues of $\mathcal{L}$ are called the eigenvalues of $G$ and are denoted by $\lambda_0 \leq \lambda_1 \leq \dots \leq \lambda_{n-1}$. It's not too hard to show that $\lambda_0$ is always $0$, so we normally refer to $\lambda_1$ as the minimal eigenvalue of $G$.

If $S\subset V$ (with $S\neq V$) then we define $\overline{S} := V-S$ and $E(S,\overline{S})$ to be the set of edges of $G$ with one vertex in $S$ and the other in $\overline{S}$. Also, let the volume of $S$ be defined as $\text{vol}(S) := \sum_{v \in S} \text{deg}(v)$. We then define $ h_G(S) := \frac{\# E(S,\overline{S})}{\text{min}(\text{vol}(S),\text{vol}(\overline{S}))}.$ The Cheeger constant of $G$ is defined to be $h_G := \min_{S \subset V} h_G(S)$.

It's clear from the definition that the Cheeger constant measures how much the graph "bottlenecks" somewhere (to borrow Wikipedia's apt description). Loosely speaking, if Cheeger's constant is small then there's a small set of edges that you can remove from the graph to disconnect it into two relatively large and relatively connected subgraphs.

Now, it doesn't seem like $\lambda_1$ (which equals the minimal Rayleigh quotient over the space of harmonic eigenfunctions) would have much of a physical interpretation. However, Cheeger's inequality traps $\lambda_1$ fairly close to $h_G$, so it is some loose measure of bottlenecking. Also, there are other little hints in the text I've read so far that $\lambda_1$ might be related to the graph's connectedness. For instance, she proves $\lambda_1 = 0$ if and only if $G$ is disconnected and that $\lambda_1 \geq 1/D\text{vol}(G)$, where $D$ is the length of the maximal-length path in $G$.

So I'm wondering if there is a meaningful physical interpretation of $\lambda_1$ that is more precise than "it's bounded near something that is meaningful."

  • 0
    @Srivatsan: My notation is consistent with Chung's book. However, to make the post self-contained, I've just edited it. Hopefully it's clearer now.2011-11-29

1 Answers 1

9

The smallest (in absolute value) eigenvalue $\lambda_1$ of the Laplacian (I don't know if this agrees with your definition of $\lambda_1$; I recall not liking Chung's definitions) measures how fast heat dissipates on the graph.

More precisely, for a (finite, for simplicity) graph $G = (V, E)$ with Laplacian $\Delta$ (regarded as an operator acting on functions $V \to \mathbb{R}$), the heat equation for a function $u(v, t) : V \times \mathbb{R} \to \mathbb{R}$ $\Delta u = \frac{\partial u}{\partial t}$

has general solution $u(v, t) = \sum_{k=0}^{n-1} e^{\lambda_i t} f_i(v)$

where $f_i : V \to \mathbb{R}$ is the eigenvector of $\Delta$ with eigenvalue $\lambda_i$ (and recall that $\lambda_0 = 0$). As a function of $t$, the dominant term above is the term $e^{\lambda_1 t} f_1(v)$, which controls the decay of the heat distribution $u$ as $t \to \infty$. Intuitively you should think of the heat equation as describing a "continuous-time random walk" on the graph. If such a random walk mixes quickly (so $\lambda_1$ is large in absolute value), then the graph is highly connected; if not, then perhaps the graph has bottlenecks of some kind. Cheeger's inequality makes this intuition precise.

  • 1
    Yes, Chung's Laplacian is a positive semide$f$inite matrix. I think that explains things. Thanks again for $y$our help! :-)2011-11-29