¿Qué nos dicen los vectores propios de una matriz de adyacencia?

Question

El vector propio principal de la matriz de adyacencia de un grafo nos da una noción de centralidad de los vértices.

¿Qué nos dicen los vectores propios segundo, tercero, etc.?

Motivación: Una técnica estándar de recuperación de información (LSI) utiliza una SVD truncada como aproximación de bajo rango de una matriz. Si truncamos a rango 1, entonces tenemos esencialmente un algoritmo de PageRank. Me preguntaba si hay formas de interpretar las correcciones introducidas por los vectores propios superiores.

Algo parecido a lo que nos dicen los momentos de una distribución (por ejemplo, el primer momento nos da la media, el segundo nos dice la varianza, el tercero nos da la asimetría, etc).

Answer 1

El segundo valor propio de una cadena de Markov tiene un significado, y afecta (por ejemplo) a la convergencia y estabilidad de los algoritmos que encuentran la distribución de equilibrio. Véase El segundo valor propio de la matriz Google de Haveliwala y Kamvar para saber cómo calcular su valor.

El segundo vector propio, sin embargo, tiene que ser algo más complejo. Dado que la matriz PageRank es una cadena de Markov reversible (por construcción), tiene una distribución de equilibrio única. Así que el único vector v para el que P v = v es el primer vector propio. Por lo tanto, el segundo vector propio no representa necesariamente una distribución de probabilidad. Según Conjuntos casi invariantes inducidos por las fluctuaciones Según la teoría de Schwartz y Billings, si una cadena de Markov reversible representa un sistema dinámico lineal, el segundo vector propio es una buena forma de encontrar conjuntos casi invariantes, que son subconjuntos de las páginas en las que el usuario estocástico perfecto pasaría un largo tiempo "atrapado" antes de irse a otras partes de la web. Los signos de las entradas del segundo eigenvector (y del tercero, y quizá de otros) pueden utilizarse para encontrar estos conjuntos casi invariantes.