En el campo matemático de la teoría de grafos , la matriz laplaciana , también llamada grafo laplaciano , matriz de admitancia , matriz de Kirchhoff o laplaciana discreta , es una representación matricial de un grafo . La matriz laplaciana se puede utilizar para encontrar muchas propiedades útiles de un gráfico. Junto con el teorema de Kirchhoff , se puede utilizar para calcular el número de árboles de expansión para un gráfico dado. El corte más escaso de una gráfica se puede aproximar a través del segundo valor propio más pequeño de su laplaciano por la desigualdad de Cheeger. También se puede utilizar para construir incrustaciones de baja dimensión , que pueden ser útiles para una variedad de aplicaciones de aprendizaje automático .
Definición
Matriz laplaciana para gráficos simples
Dado un gráfico simple con vértices, su matriz laplaciana se define como: [1]
donde D es la matriz de grados y A es la matriz de adyacencia del gráfico. Desde es un gráfico simple, solo contiene unos o ceros y sus elementos diagonales son todos ceros.
En el caso de gráficos dirigidos , se puede utilizar tanto el grado inferior como el superior , según la aplicación.
Los elementos de son dadas por
dónde es el grado del vértice .
Laplaciano normalizado simétrico
La matriz laplaciana normalizada simétrica se define como: [1]
- ,
Los elementos de son dadas por
Paseo aleatorio normalizado Laplaciano
La matriz laplaciana normalizada de caminata aleatoria se define como:
Los elementos de son dadas por
Laplaciano generalizado
El laplaciano generalizado se define como: [2]
Observe que el laplaciano ordinario es un laplaciano generalizado.
Ejemplo
A continuación se muestra un ejemplo simple de un gráfico etiquetado no dirigido y su matriz laplaciana.
Gráfico etiquetado | Matriz de grados | Matriz de adyacencia | Matriz laplaciana |
---|---|---|---|
Propiedades
Para un gráfico (no dirigido) G y su matriz laplaciana L con valores propios :
- L es simétrico .
- L es positivo-semidefinito (es decir para todos ). Esto se verifica en la sección de la matriz de incidencia (a continuación). Esto también se puede ver por el hecho de que el laplaciano es simétrico y diagonalmente dominante .
- L es una matriz M (sus entradas fuera de la diagonal no son positivas, pero las partes reales de sus valores propios no son negativas).
- Cada suma de filas y suma de columnas de L es cero. De hecho, en la suma, el grado del vértice se suma con un "-1" para cada vecino.
- En consecuencia, , porque el vector satisface Esto también implica que la matriz laplaciana es singular.
- El número de componentes conectados en el gráfico es la dimensión del espacio nulo del Laplaciano y la multiplicidad algebraica del autovalor 0.
- El valor propio más pequeño distinto de cero de L se llama brecha espectral .
- El segundo valor propio más pequeño de L (podría ser cero) es la conectividad algebraica (o valor de Fiedler ) de G y se aproxima al corte más escaso de una gráfica.
- El laplaciano es un operador en el espacio vectorial de funciones n-dimensional, dónde es el conjunto de vértices de G, y .
- Cuando G es k-regular , el Laplaciano normalizado es:, donde A es la matriz de adyacencia e I es una matriz de identidad.
- Para un gráfico con múltiples componentes conectados , L es una matriz diagonal de bloques , donde cada bloque es la matriz laplaciana respectiva para cada componente, posiblemente después de reordenar los vértices (es decir, L es una permutación similar a una matriz diagonal de bloques).
- La traza de la matriz laplaciana L es igual a dónde es el número de aristas del gráfico considerado.
Matriz de incidencia
Definir un matriz de incidencia orientada M con el elemento M ev para la arista e (que conecta el vértice i y j , con i > j ) y el vértice v dado por
Entonces la matriz laplaciana L satisface
dónde es la transpuesta de la matriz de M .
Ahora considere una descomposición propia de , con vectores propios de norma unitaria y valores propios correspondientes :
Porque se puede escribir como el producto interno del vector consigo mismo, esto muestra que y así los valores propios de son todos no negativos.
Laplaciano deformado
El laplaciano deformado se define comúnmente como
donde I es la matriz de identidad, A es la matriz de adyacencia, D es la matriz de grados y s es un número (de valor complejo). [3]
El laplaciano estándar es solo y es el laplaciano sin signo.
Laplaciano sin signo
El laplaciano sin signo se define como
dónde es la matriz de grados, y es la matriz de adyacencia. [4] Como el laplaciano firmado, el laplaciano sin signo también es positivo semidefinido, ya que se puede factorizar como
dónde es la matriz de incidencia. tiene un vector propio 0 si y solo si tiene un componente conectado bipartito distinto de los vértices aislados. Esto se puede mostrar como
Esto tiene una solución donde si y solo si el gráfico tiene un componente conectado bipartito.
Laplaciano normalizado simétrico
El laplaciano (simétrico) normalizado se define como
donde L es el Laplaciano (no normalizado), A es la matriz de adyacencia y D es la matriz de grados. Dado que la matriz de grados D es diagonal y positiva, su raíz cuadrada recíprocaes sólo la matriz diagonal cuyos elementos diagonales son los recíprocos de las raíces cuadradas positivas de los elementos de la diagonal de D . El laplaciano simétrico normalizado es una matriz simétrica.
Uno tiene: , donde S es la matriz cuyas filas están indexadas por los vértices y cuyas columnas están indexadas por los bordes de G de manera que cada columna correspondiente a un borde e = {u, v} tiene una entrada en la fila correspondiente a u, una entrada en la fila correspondiente av, y tiene 0 entradas en otros lugares. ( denota la transposición de S).
Todos los valores propios del Laplaciano normalizado son reales y no negativos. Podemos ver esto de la siguiente manera. Desdees simétrico, sus valores propios son reales. También son no negativos: considere un vector propio de con valor propio λ y supongamos . (Podemos considerar g y f como funciones reales en los vértices v.) Entonces:
donde usamos el producto interno , una suma de todos los vértices v, y denota la suma de todos los pares desordenados de vértices adyacentes {u, v}. La cantidadse llama la suma de Dirichlet de f, mientras que la expresiónse llama el cociente de Rayleigh de g.
Sea 1 la función que asume el valor 1 en cada vértice. Luego es una función propia de con valor propio 0. [5]
De hecho, los autovalores del Laplaciano simétrico normalizado satisfacen 0 = μ 0 ≤… ≤ μ n − 1 ≤ 2. Estos autovalores (conocidos como el espectro del Laplaciano normalizado) se relacionan bien con otras invariantes gráficas para gráficas generales. [6]
Paseo aleatorio normalizado Laplaciano
El Laplaciano normalizado de caminata aleatoria se define como
donde D es la matriz de grados. Dado que la matriz de grados D es diagonal, su inversase define simplemente como una matriz diagonal, que tiene entradas diagonales que son los recíprocos de las correspondientes entradas diagonales positivos de D .
Para los vértices aislados (aquellos con grado 0), una opción común es establecer el elemento correspondiente a 0.
Esta convención da como resultado una buena propiedad de que la multiplicidad del valor propio 0 es igual al número de componentes conectados en el gráfico.
Los elementos de la matriz de son dadas por
El nombre del laplaciano normalizado de caminata aleatoria proviene del hecho de que esta matriz es , dónde es simplemente la matriz de transición de un caminante aleatorio en el gráfico. Por ejemplo, dejadenotar el i-ésimo vector base estándar . Luegoes un vector de probabilidad que representa la distribución de las ubicaciones de un caminante aleatorio después de dar un solo paso desde el vértice; es decir,. De manera más general, si el vector es una distribución de probabilidad de la ubicación de un caminante aleatorio en los vértices del gráfico, entonces es la distribución de probabilidad del caminante después pasos.
Uno puede comprobar que
- ,
es decir, es similar al laplaciano normalizado. Por esta razón, incluso sien general no es hermitiano, tiene valores propios reales. De hecho, sus valores propios concuerdan con los de (que es ermitaño).
Gráficos
Como comentario adicional sobre los paseos aleatorios en los gráficos , considere un gráfico simple no dirigido . Considere la probabilidad de que el caminante esté en el vértice i en el momento t , dada la distribución de probabilidad de que estuvo en el vértice j en el momento t - 1 (asumiendo una probabilidad uniforme de dar un paso a lo largo de cualquiera de los bordes unidos a un vértice dado) :
o en notación matricial-vectorial:
(Equilibrio, que se establece como , es definido por .)
Podemos reescribir esta relación como
es una matriz simétrica llamada matriz de adyacencia reducida . Entonces, dar pasos en esta caminata aleatoria requiere tomar poderes de, que es una operación simple porque es simétrico.
Interpretación como el operador discreto de Laplace
La matriz laplaciana se puede interpretar como una representación matricial de un caso particular del operador discreto de Laplace . Tal interpretación permite, por ejemplo, generalizar la matriz laplaciana al caso de gráficos con un número infinito de vértices y aristas, lo que conduce a una matriz laplaciana de tamaño infinito.
Suponer describe una distribución de calor a través de un gráfico , donde es el calor en el vértice . De acuerdo con la ley de enfriamiento de Newton , el calor transferido desde el nodo al nodo es proporcional a si nodos y están conectados (si no están conectados, no se transfiere calor). Entonces, para la capacidad calorífica,
En notación matricial-vectorial,
lo que da
Observe que esta ecuación toma la misma forma que la ecuación de calor , donde la matriz - L reemplaza al operador laplaciano; de ahí el "grafo laplaciano".
Para encontrar una solución a esta ecuación diferencial, aplique técnicas estándar para resolver una ecuación diferencial matricial de primer orden . Es decir, escribe como una combinación lineal de vectores propios de L (para que) con coeficientes dependientes del tiempo,
Conectando a la expresión original (debido a que L es una matriz simétrica, sus vectores propios de norma unitaria son ortogonales):
cuya solución es
Como se mostró antes, los valores propios de L no son negativos, lo que demuestra que la solución de la ecuación de difusión se acerca a un equilibrio, porque solo decae exponencialmente o permanece constante. Esto también muestra que dado y la condición inicial , se puede encontrar la solución en cualquier momento t . [7]
Encontrar para cada en términos de la condición inicial general , simplemente proyecta en los vectores propios de norma unitaria ;
- .
Este enfoque se ha aplicado al modelado cuantitativo de transferencia de calor en redes no estructuradas. [8]
En el caso de gráficos no dirigidos, esto funciona porque es simétrico y, según el teorema espectral , sus vectores propios son todos ortogonales. Así que la proyección sobre los vectores propios de es simplemente una transformación de coordenadas ortogonales de la condición inicial en un conjunto de coordenadas que decaen exponencial e independientemente entre sí.
Comportamiento de equilibrio
Comprender , los únicos términos que quedan son aquellos donde , desde
En otras palabras, el estado de equilibrio del sistema está determinado completamente por el núcleo de.
Dado que por definición, , el vector de todos ellos está en el kernel. Si haycomponentes conectados disjuntos en el gráfico, entonces este vector de todos se puede dividir en la suma de independiente vectores propios de unos y ceros, donde cada componente conectado corresponde a un vector propio con unos en los elementos del componente conectado y ceros en el resto.
La consecuencia de esto es que para una condición inicial dada para un gráfico con vértices
dónde
Para cada elemento de , es decir, para cada vértice en el gráfico, se puede reescribir como
- .
En otras palabras, en estado estacionario, el valor de converge al mismo valor en cada uno de los vértices del gráfico, que es el promedio de los valores iniciales en todos los vértices. Dado que esta es la solución a la ecuación de difusión de calor, tiene perfecto sentido intuitivamente. Esperamos que los elementos vecinos en el gráfico intercambien energía hasta que esa energía se distribuya uniformemente por todos los elementos que están conectados entre sí.
Ejemplo del operador en una cuadrícula
Esta sección muestra un ejemplo de una función difundir en el tiempo a través de un gráfico. El gráfico de este ejemplo se construye en una cuadrícula discreta 2D, con puntos en la cuadrícula conectados a sus ocho vecinos. Se especifican tres puntos iniciales para tener un valor positivo, mientras que el resto de los valores de la cuadrícula son cero. Con el tiempo, la disminución exponencial actúa para distribuir los valores en estos puntos de manera uniforme en toda la cuadrícula.
El código fuente completo de Matlab que se utilizó para generar esta animación se proporciona a continuación. Muestra el proceso de especificar las condiciones iniciales, proyectando estas condiciones iniciales en los valores propios de la Matriz Laplaciana y simulando el decaimiento exponencial de estas condiciones iniciales proyectadas.
N = 20 ; % El número de píxeles a lo largo de una dimensión de la imagen. A = ceros ( N , N ); % La imagen Adj = ceros ( N * N , N * N ); % La matriz de adyacencia % Use 8 vecinos y complete la matriz de adyacenciadx = [ - 1 , 0 , 1 , - 1 , 1 , - 1 , 0 , 1 ]; dy = [ - 1 , - 1 , - 1 , 0 , 0 , 1 , 1 , 1 ]; para x = 1 : N para y = 1 : N índice = ( x - 1 ) * N + y ; para ne = 1 : longitud ( dx ) nuevox = x + dx ( ne ); newy = y + dy ( ne ); si nuevox > 0 && nuevox <= N && nuevo > 0 && nuevo <= N índice2 = ( nuevox - 1 ) * N + nuevo ; Adj ( índice , índice2 ) = 1 ; final final finalfinal% ABAJO ES EL CÓDIGO CLAVE QUE COMPUTA LA SOLUCIÓN A LA ECUACIÓN DIFERENCIALDeg = diag ( suma ( Adj , 2 )); % Calcular la matriz de grados L = Deg - Adj ; % Calcular la matriz laplaciana en términos de matrices de grado y adyacencia [ V , D ] = eig ( L ); % Calcular los autovalores / vectores de la matriz laplaciana D = diag ( D ); % Condición inicial (coloque algunos valores positivos grandes alrededor y% hacer que todo lo demás sea cero)C0 = ceros ( N , N ); C0 ( 2 : 5 , 2 : 5 ) = 5 ; C0 ( 10 : 15 , 10 : 15 ) = 10 ; C0 ( 2 : 5 , 8 : 13 ) = 7 ; C0 = C0 (:); C0V = V '* C0 ; % Transforma la condición inicial en el sistema de coordenadas % de los autovectorespara t = 0 : 0.05 : 5 % Tiempos de bucle y decadencia de cada componente inicial Phi = C0V *. Exp ( - D * t ); % Decaimiento exponencial para cada componente Phi = V * Phi ; % Transformación del sistema de coordenadas de vector propio al sistema de coordenadas original Phi = remodelar ( Phi , N , N ); % Muestra los resultados y escribe en un archivo GIF imagesc ( Phi ); caxis ([ 0 , 10 ]); title ( sprintf ( 'Difusión t =% 3f' , t )); marco = obtener marco ( 1 ); im = frame2im ( marco ); [ imind , cm ] = rgb2ind ( im , 256 ); si t == 0 imwrite ( imind , cm , 'out.gif' , 'gif' , 'Loopcount' , inf , 'DelayTime' , 0.1 ); demás imwrite ( imind , cm , 'out.gif' , 'gif' , 'WriteMode' , 'agregar' , 'DelayTime' , 0.1 ); finalfinal
Aproximación al laplaciano continuo negativo
La gráfica matriz laplaciana puede verse además como una forma matricial de una aproximación al operador laplaciano (semidefinido positivo) obtenido por el método de diferencias finitas . (Consulte la ecuación de Poisson discreta ) [9] En esta interpretación, cada vértice del gráfico se trata como un punto de la cuadrícula; la conectividad local del vértice determina la plantilla de aproximación en diferencias finitas en este punto de la cuadrícula, el tamaño de la cuadrícula es siempre uno para cada borde y no hay restricciones en ningún punto de la cuadrícula, lo que corresponde al caso de la condición de límite de Neumann homogénea , es decir , límite libre.
Multigrafos dirigidos
Se puede definir un análogo de la matriz laplaciana para multigrafos dirigidos. [10] En este caso, la matriz laplaciana L se define como
donde D es una matriz diagonal con D i , i igual al grado exterior del vértice i y A es una matriz con A i , j igual al número de aristas de i a j (incluidos los bucles).
Ver también
- Matriz de rigidez
- Distancia de resistencia
- Matriz de tasas de transición
- Cálculo en gráficos ponderados finitos
- Transformada de Fourier del gráfico
Referencias
- ^ a b Weisstein, Eric W. "Matriz laplaciana" . MathWorld .
- ^ Godsil, C .; Royle, G. (2001). Teoría de Grafos Algebraicos, Textos de Posgrado en Matemáticas . Springer-Verlag.
- ^ Morbidi, F. (2013). "El Protocolo de Consenso Deformado" (PDF) . Automatica . 49 (10): 3049-3055. doi : 10.1016 / j.automatica.2013.07.006 .
- ^ Cvetković, Dragoš; Simić, Slobodan K. (2010). "Hacia una teoría espectral de gráficos basada en el laplaciano sin signo, III". Análisis aplicable y matemáticas discretas . 4 (1): 156–166. doi : 10.2298 / AADM1000001C . ISSN 1452-8630 . JSTOR 43671298 .
- ^ Chung, Fan RK (1997). Teoría de grafos espectrales (Repr. Con corr., 2. [pr.] Ed.). Providence, RI: American Math. Soc. ISBN 978-0-8218-0315-8.
- ^ Chung, Fan (1997) [1992]. Teoría del gráfico espectral . Sociedad Matemática Estadounidense. ISBN 978-0821803158.
- ^ Newman, Mark (2010). Redes: una introducción . Prensa de la Universidad de Oxford. ISBN 978-0199206650.
- ^ Yavari, R .; Cole, KD; Rao, PK (2020). "Transferencia de calor computacional con teoría de gráfico espectral: verificación cuantitativa" . J. Internacional de Ciencias Térmicas . 153 : 106383. doi : 10.1016 / j.ijthermalsci.2020.106383 .
- ^ Smola, Alexander J .; Kondor, Risi (2003), "Kernels and regularization on graphs", Learning Theory and Kernel Machines: 16a Conferencia Anual sobre Teoría del Aprendizaje y Séptimo Taller de Kernel, COLT / Kernel 2003, Washington, DC, EE. UU., 24 al 27 de agosto de 2003, Actas , Lecture Notes in Computer Science, 2777 , Springer, págs. 144-158, CiteSeerX 10.1.1.3.7020 , doi : 10.1007 / 978-3-540-45167-9_12 , ISBN 978-3-540-40720-1.
- ^ Chaiken, S .; Kleitman, D. (1978). "Teoremas del árbol de matrices" . Revista de Teoría Combinatoria, serie A . 24 (3): 377–381. doi : 10.1016 / 0097-3165 (78) 90067-5 . ISSN 0097-3165 .
- T. Sunada, "Análisis geométrico discreto", Proceedings of Symposia in Pure Mathematics, (ed. Por P. Exner, JP Keating, P. Kuchment, T. Sunada, A. Teplyaev), 77 (2008), 51-86.
- B. Bollobás , Modern Graph Theory , Springer-Verlag (1998, edición corregida 2013), ISBN 0-387-98488-7 , Capítulos II.3 (Espacios vectoriales y matrices asociadas con gráficos), VIII.2 (La matriz de adyacencia y el laplaciano), IX.2 (Redes eléctricas y caminatas aleatorias).