What does the minimal eigenvalue of a graph say about the graph's connectivity?

1.1k Views Asked by At

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

1

There are 1 best solutions below

3
On BEST ANSWER

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.