¿Qué dice el valor propio mínimo de un gráfico sobre la conectividad del mismo?

Question

Estoy leyendo el libro de Fan Chung Teoría espectral de los gráficos y ahora estoy en el capítulo 2. Allí, Chung demuestra La desigualdad de Cheeger que es que $2h_G \geq \lambda_1 > h_G^2/2$ para cualquier gráfico $G$ . Para mí, esta desigualdad plantea la cuestión de una interpretación física de $\lambda_1$ y me pregunto si esa interpretación existe. A continuación, explicaré esta terminología y formularé mi pregunta con un poco más de precisión.

Dejemos que $G$ sea un gráfico con un conjunto de vértices $V$ con $\#V =n$ . El Laplaciano de $G$ es el $n\times n$ matriz $\mathcal{L}$ cuyo $(u,v)^{\text{th}}$ La entrada es $\text{deg}(v)$ si $u=v$ , $-(\text{deg}(u)\text{deg}(v))^{-1/2}$ si $u$ y $v$ son vértices adyacentes, y $0$ de lo contrario. Los valores propios de $\mathcal{L}$ se denominan valores propios de $G$ y se denotan por $\lambda_0 \leq \lambda_1 \leq \dots \leq \lambda_{n-1}$ . No es muy difícil demostrar que $\lambda_0$ es siempre $0$ por lo que normalmente nos referimos a $\lambda_1$ como el mínimo valor propio de $G$ .

Si $S\subset V$ (con $S\neq V$ ) entonces definimos $\overline{S} := V-S$ y $E(S,\overline{S})$ para ser el conjunto de aristas de $G$ con un vértice en $S$ y el otro en $\overline{S}$ . Además, deja que el volumen de $S$ definirse como $\text{vol}(S) := \sum_{v \in S} \text{deg}(v)$ . A continuación, definimos $$h_G(S) := \frac{\# E(S,\overline{S})}{\text{min}(\text{vol}(S),\text{vol}(\overline{S}))}.$$ El Constante de Cheeger de $G$ se define como $h_G := \min_{S \subset V} h_G(S)$ .

De la definición se desprende que la constante de Cheeger mide en qué medida el gráfico se "embotella" en algún lugar (tomando prestada la acertada descripción de Wikipedia). En términos generales, si la constante de Cheeger es pequeña, entonces hay un pequeño conjunto de aristas que se pueden eliminar del gráfico para desconectarlo en dos subgrafos relativamente grandes y relativamente conectados.

Ahora, no parece que $\lambda_1$ (que es igual al cociente mínimo de Rayleigh sobre el espacio de las eigenfunciones armónicas) tendría mucha interpretación física. Sin embargo, la desigualdad de Cheeger atrapa $\lambda_1$ bastante cerca de $h_G$ Así que se trata de una medida de cuello de botella. Además, hay otras pequeñas pistas en el texto que he leído hasta ahora que $\lambda_1$ puede estar relacionado con la conectividad del gráfico. Por ejemplo, demuestra que $\lambda_1 = 0$ si y sólo si $G$ está desconectado y que $\lambda_1 \geq 1/D\text{vol}(G)$ , donde $D$ es la longitud del camino de longitud máxima en $G$ .

Así que me pregunto si hay una interpretación física significativa de $\lambda_1$ que es más preciso que "está delimitado cerca de algo que es significativo".

Answer 1

El valor propio más pequeño (en valor absoluto) $\lambda_1$ del Laplaciano (no sé si esto coincide con su definición de $\lambda_1$ (recuerdo que no me gustan las definiciones de Chung) mide la rapidez el calor se disipa en el gráfico.

Más concretamente, para un grafo (finito, para simplificar) $G = (V, E)$ con Laplaciano $\Delta$ (considerado como un operador que actúa sobre funciones $V \to \mathbb{R}$ ), el ecuación del calor para una función $u(v, t) : V \times \mathbb{R} \to \mathbb{R}$ $$\Delta u = \frac{\partial u}{\partial t}$$

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

donde $f_i : V \to \mathbb{R}$ es el vector propio de $\Delta$ con valor propio $\lambda_i$ (y recuerda que $\lambda_0 = 0$ ). En función de $t$ el término dominante anterior es el término $e^{\lambda_1 t} f_1(v)$ que controla el decaimiento de la distribución del calor $u$ como $t \to \infty$ . Intuitivamente, hay que pensar que la ecuación del calor describe un "paseo aleatorio en tiempo continuo" sobre el gráfico. Si dicho paseo aleatorio se mezcla rápidamente (por lo que $\lambda_1$ es grande en valor absoluto), entonces el grafo está altamente conectado; si no es así, quizá el grafo tenga cuellos de botella de algún tipo. La desigualdad de Cheeger precisa esta intuición.