Intuición detrás de valores propios de una matriz de adyacencia

10

Actualmente estoy trabajando para comprender el uso del límite de Cheeger y la desigualdad de Cheeger, y su uso para la partición espectral, la conductancia, la expansión, etc., pero todavía me cuesta comenzar una intuición con respecto al segundo valor propio de la matriz de adyacencia.
Por lo general, en la teoría de grafos, la mayoría de los conceptos con los que nos encontramos son bastante fáciles de intuir, pero en este caso, ni siquiera se me ocurre qué tipo de gráficos tendría un segundo valor propio muy bajo o muy alto.
He estado leyendo preguntas similares aquí y allá en la red SE, pero generalmente se refieren a valores propios en diferentes campos ( análisis multivariado , matrices de distancia euclidianas , matrices de correlación ...).
Pero nada sobre particiones espectrales y teoría de grafos.

¿Puede alguien intentar compartir su intuición / experiencia de este segundo valor propio en el caso de los gráficos y las matrices de adyacencia?

m.raynal
fuente
¿Está familiarizado con la conexión entre el espectro de la matriz de adyacencia y la convergencia de caminatas aleatorias en el gráfico?
Yuval Filmus
@YuvalFilmus En absoluto, a pesar de estar muy familiarizado con las caminatas aleatorias y de alguna manera familiarizado con el espectro de una matriz de adyacencia. Por lo tanto, estoy interesado en su opinión :)
m.raynal

Respuestas:

6

El segundo (en magnitud) valor propio controla la tasa de convergencia de la caminata aleatoria en el gráfico. Esto se explica en muchas notas de clase, por ejemplo, notas de clase de Luca Trevisan . En términos generales, la distancia L2 a la uniformidad después de pasos puede estar limitada por .tλ2t

Otro lugar donde aparece el segundo valor propio es el problema de la camarilla plantada . El punto de partida es la observación de que un gráfico aleatorio contiene una camarilla de tamañoG(n,1/2)2log2n , pero el algoritmo codicioso solo encuentra una camarilla de tamaño log2n , y no se conoce un algoritmo mejor eficiente. (El algoritmo codicioso solo elige un nodo aleatorio, tira todos los no vecinos y se repite).

Esto sugiere la plantación de una gran clique en la parte superior de G(n,1/2) . La pregunta es: qué tan grande debe ser la camarilla, para que podamos encontrarla de manera eficiente. Si plantamos una camarilla de tamaño Cnlogn , entonces podríamos identificar los vértices de la camarilla solo por su grado; pero este método solo funciona para camarillas de tamañoΩ(nlogn). Podemos mejorar esto usando técnicas espectrales: si plantamos una camarilla de tamañoCn , entonces elsegundo vector propiocodifica la camarilla, comoAlon, Krivelevich y Sudakovmostraron en un artículo clásico.

De manera más general, los primeros pocos vectores propios son útiles para dividir el gráfico en un pequeño número de grupos. Véase, por ejemplo, el Capítulo 3 de las notas de clase de Luca Trevisan , que describe las desigualdades de Cheeger de orden superior.

Yuval Filmus
fuente
5

(Descargo de responsabilidad: esta respuesta se trata de valores propios de los gráficos en general, no del segundo valor propio en particular. Sin embargo, espero que sea útil).

Una forma interesante de pensar acerca de los valores propios de un gráfico G=(V,E) es tomando el espacio vectorial Rn donde n=|V|e identificar cada vector con una función f:VR (es decir, un etiquetado de vértices). Un vector propio de la matriz de adyacencia, entonces, es un elemento de fRn tal que hay λR (es decir, un valor propio) con Af=λf , Asiendo la matriz de adyacencia de G . Tenga en cuenta que Af es el vector asociado con el mapa que envía cada vértice vV a uN(v)f(u) , siendo N(v) el conjunto de vecinos (es decir, vértices adyacentes a) u . Por lo tanto, en esta configuración, la propiedad de vector propio de f corresponde a la propiedad que suma sobre los valores de la función (bajo f )de los vecinos de un vértice produce el mismo resultado que multiplicar el valor de la función del vértice con la constante λ .

dkaeae
fuente
Muchas gracias, nunca había 'visto' que el vector propio multiplicado por \ lambda tenía el valor de la suma de los valores de función de los vecinos (incluso si proviene directamente de la definición).
m.raynal
1
Yo tampoco :) Lo encontré por casualidad en un programa de estudios sobre valores propios de gráficos.
dkaeae
5

G

GdGL=I1dAIn×nAf:VR,L

f,Lf=1d(u,v)E(f(u)f(v))2.

AdL0λ2AL1λ2d

1λ2d=min{f,Lff,f:vVf(v)=0,f0}.

f,Lfff:VRf0f0(u)=f(u)1nvVf(v)

1λ2d=min{f,Lff0,f0:f not constant}.

f0,f0=1n{u,v}(V2)(f(u)f(v))2n2

1λ2d=min{2nd(u,v)E(f(u)f(v))22n2{u,v}(V2)(f(u)f(v))2:f not constant}.

Lo que esto significa es que, si colocamos cada vértice de en la línea real en el punto , entonces la distancia promedio entre dos vértices aleatorios independientes en el gráfico (el denominador) es como máximo veces la distancia promedio entre los puntos finales de un borde aleatorio en el gráfico (el numerador). Entonces, en este sentido, una gran brecha espectral significa que lo que sucede a través de un borde aleatorio deuGf(u)ddλ2G (comportamiento local) es un buen predictor de lo que sucede a través de un par aleatorio de vértices no correlacionados (comportamiento global).

Sasho Nikolov
fuente