En el campo matemático de la teoría de grafos , la matriz laplaciana , también llamada gráfica laplaciana , matriz de admitancia , matriz de Kirchhoff o laplaciana discreta , es una representación matricial de una gráfica . La matriz laplaciana gráfica, que lleva el nombre de Pierre-Simon Laplace , puede verse como una forma matricial del operador de Laplace discreto negativo en una gráfica que se aproxima al laplaciano continuo negativo obtenido mediante el método de diferencias finitas .
La matriz laplaciana se relaciona con 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 determinado. El corte más escaso de un gráfico se puede aproximar a través del vector de Fiedler , el vector propio correspondiente al segundo valor propio más pequeño del gráfico laplaciano, según lo establecido por la desigualdad de Cheeger . La descomposición espectral de la matriz laplaciana permite construir incrustaciones de baja dimensión que aparecen en muchas aplicaciones de aprendizaje automático y determina un diseño espectral en el dibujo de gráficos . El procesamiento de señales basado en gráficos se basa en la transformada de Fourier gráfica que extiende la transformada de Fourier discreta tradicional al sustituir la base estándar de sinusoides complejas por vectores propios de la matriz laplaciana de un gráfico correspondiente a la señal.
La matriz laplaciana es la más fácil de definir para un gráfico simple , pero es más común en aplicaciones para un gráfico ponderado en los bordes , es decir, con pesos en sus bordes: las entradas de la matriz de adyacencia del gráfico . La teoría de grafos espectrales relaciona las propiedades de un gráfico con un espectro, es decir, valores propios y vectores propios de matrices asociadas con el gráfico, como su matriz de adyacencia o matriz laplaciana. Los pesos desequilibrados pueden afectar de manera no deseada el espectro de la matriz, lo que lleva a la necesidad de normalización (una escala de columna/fila de las entradas de la matriz) lo que resulta en adyacencia normalizada y matrices laplacianas.
Dado un gráfico simple con vértices , su matriz laplaciana se define por elementos como [1]
o equivalentemente por la matriz
donde D es la matriz de grados y A es la matriz de adyacencia del gráfico. Dado que es un gráfico simple, solo contiene 1 o 0 y sus elementos diagonales son todos 0.
A continuación se muestra un ejemplo sencillo de un gráfico no dirigido etiquetado y su matriz laplaciana.
Observamos para el gráfico no dirigido que tanto la matriz de adyacencia como la matriz laplaciana son simétricas, y que las sumas de filas y columnas de la matriz laplaciana son todas ceros (lo que implica directamente que la matriz laplaciana es singular).
Para gráficos dirigidos , se puede utilizar el grado de entrada o de salida , según la aplicación, como en el siguiente ejemplo:
En el gráfico dirigido, tanto la matriz de adyacencia como la matriz laplaciana son asimétricas. En su matriz laplaciana, las sumas de columnas o las sumas de filas son cero, dependiendo de si se ha utilizado el grado de entrada o de salida .
La matriz de incidencia orientada B con elemento B ve para el vértice v y la arista e (conectando vértices y , con i ≠ j ) está definida por
Aunque los bordes en esta definición están técnicamente dirigidos, sus direcciones pueden ser arbitrarias, dando como resultado la misma matriz laplaciana simétrica L definida como
¿Dónde está la matriz transpuesta de B ?
Un producto alternativo define el llamado laplaciano basado en bordes, a diferencia de la matriz laplaciana L original basada en vértices, comúnmente utilizada .
La matriz laplaciana de un gráfico dirigido es, por definición, generalmente no simétrica, mientras que, por ejemplo, la agrupación espectral tradicional se desarrolla principalmente para gráficos no dirigidos con adyacencia simétrica y matrices laplacianas. Un enfoque trivial para aplicar técnicas que requieren simetría es convertir el gráfico dirigido original en un gráfico no dirigido y construir la matriz laplaciana para este último.
En la notación matricial, la matriz de adyacencia del gráfico no dirigido podría, por ejemplo, definirse como una suma booleana de la matriz de adyacencia del gráfico dirigido original y su transposición matricial , donde las entradas cero y uno de se tratan como lógicas, en lugar de valores numéricos, como en el siguiente ejemplo:
Un vértice con un grado grande, también llamado nodo pesado, da como resultado una entrada diagonal grande en la matriz laplaciana que domina las propiedades de la matriz. La normalización tiene como objetivo hacer que la influencia de dichos vértices sea más igual a la de otros vértices, dividiendo las entradas de la matriz laplaciana por los grados de los vértices. Para evitar la división por cero, los vértices aislados con cero grados se excluyen del proceso de normalización.
La matriz laplaciana simétricamente normalizada se define como: [1]
¿Dónde está la inversa de Moore-Penrose ?
Los elementos de están dados por tanto por
La matriz laplaciana simétricamente normalizada es simétrica si y sólo si la matriz de adyacencia es simétrica.
Para una matriz de adyacencia no simétrica de un gráfico dirigido, se puede utilizar tanto el grado de entrada como el de salida para la normalización:
La matriz laplaciana normalizada por la izquierda (paseo aleatorio) se define como:
¿Dónde está la inversa de Moore-Penrose ? Los elementos de están dados por
De manera similar, la matriz laplaciana normalizada a la derecha se define como
La matriz laplaciana normalizada izquierda o derecha no es simétrica si la matriz de adyacencia es simétrica, excepto en el caso trivial de todos los vértices aislados. Por ejemplo,
El ejemplo también demuestra que si no tiene vértices aislados, entonces estocástico derecho y, por lo tanto, es la matriz de un paseo aleatorio , de modo que el laplaciano normalizado por la izquierda hace que cada fila sume cero. Por lo tanto, a veces alternativamente llamamos laplaciano normalizado al paseo aleatorio . En el laplaciano normalizado a la derecha, menos utilizado, cada columna suma cero, ya que es estocástico por la izquierda .
Para una matriz de adyacencia no simétrica de un gráfico dirigido, también es necesario elegir el grado de entrada o de salida para la normalización:
El laplaciano normalizado de grado exterior izquierdo con sumas de filas todos 0 se relaciona con el estocástico derecho , mientras que el laplaciano normalizado de grado interno derecho con sumas de columnas todo 0 contiene estocástico izquierdo .
Los gráficos comunes en aplicaciones con bordes ponderados se definen convenientemente por sus matrices de adyacencia donde los valores de las entradas son numéricos y ya no se limitan a ceros y unos. En la agrupación espectral y el procesamiento de señales basado en gráficos , donde los vértices del gráfico representan puntos de datos, los pesos de los bordes se pueden calcular, por ejemplo, como inversamente proporcionales a las distancias entre pares de puntos de datos, lo que lleva a que todos los pesos sean no negativos con valores más grandes de manera informal. correspondientes a pares de puntos de datos más similares. El uso de correlación y anticorrelación entre los puntos de datos conduce naturalmente a ponderaciones tanto positivas como negativas. La mayoría de las definiciones de gráficos simples se extienden trivialmente al caso estándar de ponderaciones no negativas, mientras que las ponderaciones negativas requieren más atención, especialmente en la normalización.
La matriz laplaciana está definida por
donde D es la matriz de grados y A es la matriz de adyacencia del gráfico.
Para gráficos dirigidos , se puede utilizar el grado de entrada o de salida , según la aplicación, como en el siguiente ejemplo:
Los bucles propios del gráfico, que se manifiestan mediante entradas distintas de cero en la diagonal principal de la matriz de adyacencia, están permitidos, pero no afectan los valores laplacianos del gráfico.
Para gráficos con aristas ponderadas, se puede definir una matriz de incidencia ponderada B y usarla para construir el laplaciano simétrico correspondiente como . Un enfoque alternativo más limpio, que se describe aquí, es separar los pesos de la conectividad: continuar usando la matriz de incidencia como para los gráficos regulares e introducir una matriz que solo contenga los valores de los pesos. Un sistema de resortes es un ejemplo de este modelo utilizado en mecánica para describir un sistema de resortes de rigidez y longitud unitaria determinadas, donde los valores de las rigideces desempeñan el papel de los pesos de los bordes del gráfico.
Por lo tanto, reutilizamos la definición de la matriz de incidencia ingrávida B con el elemento B ve para el vértice v y el borde e (que conecta los vértices y , con i > j ) definido por
Ahora también definimos una matriz diagonal W que contiene los pesos de los bordes. Aunque las aristas en la definición de B están técnicamente dirigidas, sus direcciones pueden ser arbitrarias, dando como resultado la misma matriz laplaciana simétrica L definida como
¿Dónde está la matriz transpuesta de B ?
La construcción se ilustra en el siguiente ejemplo, donde a cada borde se le asigna el valor de peso i , con
Al igual que para los gráficos simples, la matriz laplaciana de un gráfico ponderado dirigido es, por definición, generalmente no simétrica. La simetría se puede imponer convirtiendo primero el gráfico dirigido original en un gráfico no dirigido antes de construir el laplaciano. La matriz de adyacencia del gráfico no dirigido podría, por ejemplo, definirse como una suma de la matriz de adyacencia del gráfico dirigido original y su matriz transpuesta como en el siguiente ejemplo:
donde las entradas cero y uno se tratan como valores numéricos, en lugar de lógicos como para gráficos simples, lo que explica la diferencia en los resultados; para gráficos simples, el gráfico simetrizado aún debe ser simple y su matriz de adyacencia simetrizada solo tiene valores lógicos, valores no numéricos, por ejemplo, la suma lógica es 1 v 1 = 1, mientras que la suma numérica es 1 + 1 = 2.
Alternativamente, la matriz laplaciana simétrica se puede calcular a partir de los dos laplacianos usando el grado de entrada y el grado de salida , como en el siguiente ejemplo:
La suma del laplaciano de grado externo transpuesto y el laplaciano de grado interno es igual a la matriz laplaciana simétrica.
El objetivo de la normalización es, al igual que para los gráficos simples, hacer que las entradas diagonales de la matriz laplaciana sean todas unitarias, y también escalar las entradas fuera de la diagonal en consecuencia. En un gráfico ponderado , un vértice puede tener un grado grande debido a una pequeña cantidad de aristas conectadas pero con pesos grandes, así como debido a una gran cantidad de aristas conectadas con pesos unitarios.
Los bucles propios del gráfico, es decir, entradas distintas de cero en la diagonal principal de la matriz de adyacencia, no afectan los valores laplacianos del gráfico, pero es posible que sea necesario contarlos para el cálculo de los factores de normalización.
El laplaciano simétricamente normalizado se define como
donde L es el laplaciano no normalizado, A es la matriz de adyacencia, D es la matriz de grados y es la inversa de Moore-Penrose . Dado que la matriz de grados D es diagonal, su raíz cuadrada recíproca es simplemente la matriz diagonal cuyas entradas diagonales son las recíprocas de las raíces cuadradas de las entradas diagonales de D. Si todos los pesos de los bordes no son negativos, entonces todos los valores de grados también son automáticamente no negativos y, por lo tanto, cada valor de grados tiene una raíz cuadrada positiva única. Para evitar la división por cero, los vértices con cero grados se excluyen del proceso de normalización, como en el siguiente ejemplo:
El laplaciano simétricamente normalizado es una matriz simétrica si y sólo si la matriz de adyacencia A es simétrica y las entradas diagonales de D no son negativas, en cuyo caso podemos usar el término laplaciano simétrico normalizado .
La matriz laplaciana simétrica normalizada también se puede escribir como
utilizando la matriz de incidencia ingrávida B y la matriz diagonal W que contiene los pesos de las aristas y definiendo la nueva matriz de incidencia ponderada cuyas filas están indexadas por los vértices y cuyas columnas están indexadas por las aristas de G de modo que cada columna corresponde a una arista e = { u, v} tiene una entrada en la fila correspondiente a u , una entrada en la fila correspondiente a v y tiene 0 entradas en otros lugares.
El paseo aleatorio laplaciano normalizado se define como
donde D es la matriz de grados. Dado que la matriz de grados D es diagonal, su inversa se define simplemente como una matriz diagonal, que tiene entradas diagonales que son recíprocas de las entradas diagonales correspondientes de D. Para los vértices aislados (aquellos con grado 0), una opción común es establecer el elemento correspondiente en 0. Los elementos de la matriz de están dados por
El nombre del laplaciano normalizado de paseo aleatorio proviene del hecho de que esta matriz es , donde es simplemente la matriz de transición de un caminante aleatorio en el gráfico, asumiendo pesos no negativos. Por ejemplo, denotemos el i-ésimo vector de base estándar . Entonces es 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 de los pasos.
El laplaciano normalizado de paseo aleatorio también se puede llamar laplaciano normalizado a la izquierda, ya que la normalización se realiza multiplicando el laplaciano por la matriz de normalización de la izquierda. Cada fila suma cero ya que es estocástico derecho , suponiendo que todos los pesos no sean negativos.
En el laplaciano normalizado a la derecha, menos utilizado, cada columna suma cero, ya que es estocástico por la izquierda .
Para una matriz de adyacencia no simétrica de un gráfico dirigido, también es necesario elegir el grado de entrada o de salida para la normalización:
El laplaciano normalizado de grado exterior izquierdo con sumas de filas todos 0 se relaciona con el estocástico derecho , mientras que el laplaciano normalizado de grado interno derecho con sumas de columnas todo 0 contiene estocástico izquierdo .
Las ponderaciones negativas presentan varios desafíos para la normalización:
Para un gráfico (no dirigido) G y su matriz laplaciana L con valores propios :
Debido a que se puede escribir como el producto interno del vector consigo mismo, esto muestra que los valores propios de son todos no negativos.
es decir, es similar al laplaciano normalizado . Por esta razón, incluso si en general no es simétrico, tiene valores propios reales, exactamente los mismos que los valores propios del laplaciano simétrico normalizado .
La matriz laplaciana gráfica se puede ver además como una forma matricial del operador de Laplace discreto negativo en un gráfico que se aproxima al operador laplaciano continuo negativo obtenido mediante el método de diferencias finitas . (Ver ecuación discreta de Poisson ) [2] En esta interpretación, cada vértice del gráfico se trata como un punto de 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 frontera homogénea de Neumann , es decir , límite libre. 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 lleva a una matriz laplaciana de tamaño infinito.
El laplaciano generalizado se define como: [3]
Observe que el laplaciano ordinario es un laplaciano generalizado.
Las entradas de la matriz de adyacencia pueden tener valores complejos, en cuyo caso la noción de simetría matricial debe reemplazarse con una matriz hermitiana . El laplaciano magnético para un gráfico dirigido con pesos reales se construye como el producto de Hadamard de la matriz simétrica real del laplaciano simetrizado y la matriz de fase hermitiana con las entradas complejas .
que codifican la dirección del borde en la fase en el plano complejo. En el contexto de la física cuántica, el laplaciano magnético puede interpretarse como el operador que describe en una gráfica la fenomenología de una partícula libre cargada, la cual está sujeta a la acción de un campo magnético y el parámetro se denomina carga eléctrica. [4] En el siguiente ejemplo :
El laplaciano deformado se define comúnmente como
donde I es la matriz identidad, A es la matriz de adyacencia, D es la matriz de grados y s es un número (de valores complejos). [5]
El laplaciano estándar es justo y es el laplaciano sin signos.
El laplaciano sin signos se define como
donde es la matriz de grados y es la matriz de adyacencia. [6] Al igual que el laplaciano con signo , el laplaciano sin signo también es semidefinido positivo ya que puede factorizarse como
donde está la matriz de incidencia. tiene un vector propio 0 si y solo si tiene un componente bipartito conectado (los vértices aislados son componentes bipartitos conectados). Esto se puede mostrar como
Esto tiene una solución si y solo si el gráfico tiene un componente bipartito conectado.
Se puede definir un análogo de la matriz laplaciana para multigrafos dirigidos. [7] 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).