Teoría espectral de los grafos: interpretabilidad de los valores propios y los vectores

Question

Pensé "¡Guau!" cuando aprendí que el vector propio de la matriz de adyacencia de un gráfico de ciclo $C_n$ correspondiente al segundo mayor valor propio da las coordenadas de los vértices cuando se distribuyen por igual en el ciclo unitario: el $n$ -Las raíces de la unidad (del análisis complejo) aparecen en un contexto completamente discreto. Es más: Las coordenadas del vector propio pueden ser "interpretadas" directamente cuando se asignan correctamente a los vértices.

Hay otra interpretación directa de un vector propio de adyacencia: el vector propio correspondiente al mayor valor propio da la importancia relativa de los vértices siendo proporcional a la suma de las importancias relativas de sus vecinos.

Pregunta: ¿Se pueden "interpretar" más vectores propios de adyacencia, o todos ellos, de forma razonable? "interpretados"?

¿O, en general, depende del tipo de gráfico, de si se pueden interpretar los vectores propios y de cómo se pueden interpretar, y el primer ejemplo anterior es sólo una curiosidad?

¿Qué pasa con la interpretación de los eigen- valores ? ¿Al menos algunos de ellos "significan" algo concebible?

Answer 1

Una referencia definitiva es la de Lovasz Valores propios de los gráficos un documento que desconocía al hacer esta pregunta.

Answer 2

Las características estructurales interesantes de los grafos suelen reflejarse en los vectores propios (¿qué tal una generalidad?) A menudo es cuestión de habilidad qué vector propio tomar. Por ejemplo, un grfo cíclico tiene multiplicidad 2 para el siguiente valor propio más grande. Tome un 6-ciclo (ya que es fácil). El 2º valor propio es 1 y un vector propio genérico (en orden cíclico) es (1,t,t-1,-1,-t,1-t) SO (buscando relativamente pocos valores distintos) (1,1/2,-1/2,-1,-1/2,1/2) y (1,1,0,-1,-1,0) (y sus desplazamientos cíclicos) parecen buenos. Girando este último a (0,1,1,0,-1,-1) multiplicando por $\frac{\sqrt{-3}}{2}$ y añadiendo esto a (1,1/2,-1/2,-1,-1/2,1/2) se obtiene un bonito vector propio con valores en el círculo unitario, pero no es el vector propio.

Esta es otra forma de verlo $-\lambda$ es un valor propio de un grafo bipartito cuando $\lambda $ es: Tomar un vector propio para $\lambda$ y sustituir todos los valores de una parte por sus negativos. Esto muestra que (dado que el mayor valor propio es único en el sentido de que tiene un vector propio totalmente positivo) el más pequeño (en el caso bipartito) es único en el sentido de que es positivo en una mitad del gráfico y negativo en la otra, por lo que revela la bipartición. Se podría suponer que en un grafo general el valor propio más pequeño podría tener algunos vectores propios que partieran los vértices en dos clases (positivos y negativos) de forma que se minimizara el número de aristas que conectan vértices del mismo signo. Varios teoremas de Miroslav Fiedler son relevantes para estas consideraciones.

También mencionaré que me ha resultado útil considerar el subespacio abarcado por (los vectores propios de) varios valores propios. Consideremos el esqueleto de un cubo. La suma de los espacios propios primero y segundo se extiende por los vectores característicos de las 6 caras. La suma de los primeros valores propios, segundo y tercero, se extiende por los vectores característicos de las 12 aristas. La suma de los cuatro primeros valores propios (¡es decir, todo!) está abarcada por los vectores característicos de los 8 vértices. Esto es cierto (mutatis mutandis) de forma mucho más general (grafos de Hamming, redes finitas, grafos de Johnson y otros grafos que surgen de geometrías muy regulares).