matriz laplaciana

Representación matricial de un gráfico.

En el campo matemático de la teoría de grafos , la matriz laplaciana , también llamada laplaciana gráfica , 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 gráfica de Fourier que extiende la transformada discreta tradicional de Fourier 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.

Definiciones para gráficos simples

matriz laplaciana

Dado un gráfico simple con vértices , su matriz laplaciana se define por elementos como ^[1] ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle v_{1},\ldots ,v_{n}}$ ${\textstyle L_{n\times n}}$

${\displaystyle L_{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{if}}\ i=j\\-1&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}},\end{cases}}}$

o equivalentemente por la matriz

${\displaystyle L=D-A,}$

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. ${\textstyle G}$ ${\textstyle A}$

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.

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 .

Laplaciano simétrico a través de la matriz de incidencia

La matriz de incidencia B con el elemento B _ve para el vértice v y la arista e (conectando vértices y , con i  <  j ) está definida por ${\textstyle |v|\times |e|}$ ${\textstyle v_{i}}$ ${\textstyle v_{j}}$

${\displaystyle B_{ve}=\left\{{\begin{array}{rl}1,&{\text{if }}v=v_{i}\\-1,&{\text{if }}v=v_{j}\\0,&{\text{otherwise}}.\end{array}}\right.}$

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 ${\textstyle |v|\times |v|}$

${\displaystyle L=BB^{\textsf {T}}}$

¿ Dónde está la matriz transpuesta de B ? ${\textstyle B^{\textsf {T}}}$

Un producto alternativo define el llamado laplaciano basado en bordes, a diferencia de la matriz laplaciana original basada en vértices L , comúnmente utilizada . ${\displaystyle B^{\textsf {T}}B}$ ${\textstyle |e|\times |e|}$

Laplaciano simétrico para un gráfico dirigido

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: ${\displaystyle A}$ ${\displaystyle A^{T}}$ ${\displaystyle A}$

Normalización de la matriz laplaciana

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.

Laplaciano simétricamente normalizado

La matriz laplaciana simétricamente normalizada se define como: ^[1]

${\displaystyle L^{\text{sym}}:=(D^{+})^{1/2}L(D^{+})^{1/2}=I-(D^{+})^{1/2}A(D^{+})^{1/2},}$

¿Dónde está la inversa de Moore-Penrose ? ${\displaystyle D^{+}}$

Los elementos de están dados por tanto por ${\textstyle L^{\text{sym}}}$

${\displaystyle L_{i,j}^{\text{sym}}:={\begin{cases}1&{\mbox{if }}i=j{\mbox{ and }}\deg(v_{i})\neq 0\\-{\frac {1}{\sqrt {\deg(v_{i})\deg(v_{j})}}}&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}}$

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:

Laplacianos normalizados izquierdo (camino aleatorio) y derecho

La matriz laplaciana normalizada por la izquierda (paseo aleatorio) se define como:

${\displaystyle L^{\text{rw}}:=D^{+}L=I-D^{+}A,}$

¿Dónde está la inversa de Moore-Penrose ? Los elementos de están dados por ${\displaystyle D^{+}}$ ${\textstyle L^{\text{rw}}}$

${\displaystyle L_{i,j}^{\text{rw}}:={\begin{cases}1&{\mbox{if }}i=j{\mbox{ and }}\deg(v_{i})\neq 0\\-{\frac {1}{\deg(v_{i})}}&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}}$

De manera similar, la matriz laplaciana normalizada a la derecha se define como

${\displaystyle LD^{+}=I-AD^{+}}$.

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 . ${\displaystyle G}$ ${\displaystyle D^{+}A}$ ${\displaystyle L^{\text{rw}}:=D^{+}L=I-D^{+}A}$ ${\displaystyle L^{\text{rw}}}$ ${\displaystyle LD^{+}=I-AD^{+}}$ ${\displaystyle AD^{+}}$

Para una matriz de adyacencia no simétrica de un gráfico dirigido, también es necesario elegir el grado de entrada o 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 . ${\displaystyle D_{\text{out}}^{+}A}$ ${\displaystyle AD_{\text{in}}^{+}}$

Definiciones para gráficos con aristas ponderadas

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.

matriz laplaciana

La matriz laplaciana está definida por

${\displaystyle L=D-A,}$

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.

Laplaciano simétrico a través de la matriz de incidencia

Un sistema de resorte bidimensional.

Para gráficos con bordes ponderados, 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. ${\displaystyle L=BB^{\textsf {T}}}$

Así reutilizamos la definición de la matriz de incidencia ingrávida B con el elemento B _ve para el vértice v y la arista e (conectando vértices y , con i  >  j ) definida por ${\textstyle |v|\times |e|}$ ${\textstyle v_{i}}$ ${\textstyle v_{j}}$

${\displaystyle B_{ve}=\left\{{\begin{array}{rl}1,&{\text{if }}v=v_{i}\\-1,&{\text{if }}v=v_{j}\\0,&{\text{otherwise}}.\end{array}}\right.}$

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 ${\textstyle |e|\times |e|}$ ${\textstyle |v|\times |v|}$

${\displaystyle L=BWB^{\textsf {T}}}$

¿ Dónde está la matriz transpuesta de B ? ${\textstyle B^{\textsf {T}}}$

La construcción se ilustra en el siguiente ejemplo, donde a cada borde se le asigna el valor de peso i , con ${\textstyle e_{i}}$ ${\textstyle i=1,2,3,4.}$

Laplaciano simétrico para un gráfico dirigido

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: ${\displaystyle A}$ ${\displaystyle A^{T}}$

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. ${\displaystyle A}$

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.

Normalización de la matriz laplaciana

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.

Laplaciano simétricamente normalizado

El laplaciano simétricamente normalizado se define como

${\displaystyle L^{\text{sym}}:=(D^{+})^{1/2}L(D^{+})^{1/2}=I-(D^{+})^{1/2}A(D^{+})^{1/2},}$

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: ${\displaystyle D^{+}}$ ${\textstyle (D^{+})^{1/2}}$

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

${\displaystyle L^{\text{sym}}:=(D^{+})^{1/2}L(D^{+})^{1/2}=(D^{+})^{1/2}BWB^{\textsf {T}}(D^{+})^{1/2}=SS^{T}}$

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. ${\textstyle |v|\times |e|}$ ${\textstyle |e|\times |e|}$ ${\textstyle |v|\times |e|}$ ${\textstyle S=(D^{+})^{1/2}BW^{{1}/{2}}}$ ${\textstyle {\frac {1}{\sqrt {d_{u}}}}}$ ${\textstyle -{\frac {1}{\sqrt {d_{v}}}}}$

Paseo aleatorio normalizado laplaciano

El paseo aleatorio laplaciano normalizado se define como

${\displaystyle L^{\text{rw}}:=D^{+}L=I-D^{+}A}$

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 ${\textstyle D^{+}}$ ${\textstyle L_{i,i}^{\text{rw}}}$ ${\textstyle L^{\text{rw}}}$

${\displaystyle L_{i,j}^{\text{rw}}:={\begin{cases}1&{\mbox{if}}\ i=j\ {\mbox{and}}\ \deg(v_{i})\neq 0\\-{\frac {1}{\deg(v_{i})}}&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}}$

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. ${\textstyle L^{\text{rw}}=I-P}$ ${\textstyle P=D^{+}A}$ ${\textstyle e_{i}}$ ${\textstyle x=e_{i}P}$ ${\textstyle i}$ ${\textstyle x_{j}=\mathbb {P} \left(v_{i}\to v_{j}\right)}$ ${\textstyle x}$ ${\textstyle x'=xP^{t}}$ ${\textstyle t}$

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. ${\displaystyle L^{\text{rw}}:=D^{+}L}$ ${\displaystyle D^{+}}$ ${\displaystyle P=D^{+}A}$

En el laplaciano normalizado a la derecha, menos utilizado, cada columna suma cero, ya que es estocástico por la izquierda . ${\displaystyle LD^{+}=I-AD^{+}}$ ${\displaystyle AD^{+}}$

Para una matriz de adyacencia no simétrica de un gráfico dirigido, también es necesario elegir el grado de entrada o 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 . ${\displaystyle D_{\text{out}}^{+}A}$ ${\displaystyle AD_{\text{in}}^{+}}$

Pesos negativos

Las ponderaciones negativas presentan varios desafíos para la normalización:

• La presencia de pesos negativos puede naturalmente dar como resultado sumas de filas y/o columnas nulas para los vértices no aislados. Un vértice con una gran suma de filas de pesos positivos y una suma de filas igualmente grande de pesos negativos, que en conjunto suman cero, podría considerarse un nodo pesado y ambos valores grandes escalados, mientras que la entrada diagonal permanece cero, como para un vértice aislado.
• Los pesos negativos también pueden dar sumas de filas y/o columnas negativas, de modo que la entrada diagonal correspondiente en la matriz laplaciana no normalizada sería negativa y no existiría una raíz cuadrada positiva necesaria para la normalización simétrica.
• Se pueden presentar argumentos para tomar el valor absoluto de las sumas de filas y/o columnas con fines de normalización, tratando así un posible valor -1 como una entrada unitaria legítima de la diagonal principal de la matriz laplaciana normalizada.

Propiedades

Para un gráfico (no dirigido) G y su matriz laplaciana L con valores propios : ${\textstyle \lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{n-1}}$

• L es simétrica .
• L es positivo-semidefinido (es decir, para todos ). Esto se puede ver en el hecho de que el laplaciano es simétrico y diagonalmente dominante . ${\textstyle \lambda _{i}\geq 0}$ ${\textstyle i}$
• 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).
• La suma de cada fila y columna 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. ${\textstyle \lambda _{0}=0}$ ${\textstyle \mathbf {v} _{0}=(1,1,\dots ,1)}$ ${\textstyle L\mathbf {v} _{0}=\mathbf {0} .}$
• El número de componentes conectados en el gráfico es la dimensión del espacio nulo del laplaciano y la multiplicidad algebraica del valor propio 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 un gráfico.
• El laplaciano es un operador en el espacio vectorial de funciones n-dimensional , donde es el conjunto de vértices de G, y . ${\textstyle f:V\to \mathbb {R} }$ ${\textstyle V}$ ${\textstyle n=|V|}$
• Cuando G es k-regular , el laplaciano normalizado es: , donde A es la matriz de adyacencia e I es una matriz identidad. ${\textstyle {\mathcal {L}}={\tfrac {1}{k}}L=I-{\tfrac {1}{k}}A}$
• 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 donde está el número de aristas del gráfico considerado. ${\textstyle 2m}$ ${\textstyle m}$
• Ahora considere una descomposición propia de , con vectores propios de norma unitaria y valores propios correspondientes : ${\textstyle L}$ ${\textstyle \mathbf {v} _{i}}$ ${\textstyle \lambda _{i}}$

${\displaystyle {\begin{aligned}\lambda _{i}&=\mathbf {v} _{i}^{\textsf {T}}L\mathbf {v} _{i}\\&=\mathbf {v} _{i}^{\textsf {T}}M^{\textsf {T}}M\mathbf {v} _{i}\\&=\left(M\mathbf {v} _{i}\right)^{\textsf {T}}\left(M\mathbf {v} _{i}\right).\\\end{aligned}}}$

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. ${\textstyle \lambda _{i}}$ ${\textstyle M\mathbf {v} _{i}}$ ${\textstyle \lambda _{i}\geq 0}$ ${\textstyle L}$

• Todos los valores propios del laplaciano simétrico normalizado satisfacen 0 = μ ₀ ≤… ≤ μ _n−1 ≤ 2. Estos valores propios (conocidos como el espectro del laplaciano normalizado) se relacionan bien con otros invariantes de gráficos para gráficos generales. ^[1]

• Se puede comprobar que:

${\displaystyle L^{\text{rw}}=I-D^{-{\frac {1}{2}}}\left(I-L^{\text{sym}}\right)D^{\frac {1}{2}}}$,

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 . ${\textstyle L^{\text{rw}}}$ ${\textstyle L^{\text{sym}}}$ ${\textstyle L^{\text{rw}}}$ ${\textstyle L^{\text{sym}}}$

Interpretación como operador discreto de Laplace que se aproxima al laplaciano continuo

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.

Generalizaciones y extensiones de la matriz laplaciana.

Laplaciano generalizado

El laplaciano generalizado se define como: ^[3] ${\displaystyle Q}$

${\displaystyle {\begin{cases}Q_{i,j}<0&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\Q_{i,j}=0&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is not adjacent to }}v_{j}\\{\mbox{any number}}&{\mbox{otherwise}}.\end{cases}}}$

Observe que el laplaciano ordinario es un laplaciano generalizado.

Laplaciano magnético

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 . ${\displaystyle w_{ij}}$

${\displaystyle \gamma _{q}(i,j)=e^{i2\pi q(w_{ij}-w_{ji})}}$

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 : ${\displaystyle q}$ ${\displaystyle q=1/4}$

Laplaciano deformado

El laplaciano deformado se define comúnmente como

${\displaystyle \Delta (s)=I-sA+s^{2}(D-I)}$

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. ${\textstyle \Delta (1)}$ ${\textstyle \Delta (-1)=D+A}$

Laplaciano sin signos

El laplaciano sin signos se define como

${\displaystyle Q=D+A}$

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 ${\displaystyle D}$ ${\displaystyle A}$ ${\displaystyle L}$ ${\displaystyle Q}$

${\displaystyle Q=RR^{\textsf {T}}}$

donde está la matriz de incidencia. tiene un vector propio 0 si y solo si tiene un componente bipartito conectado distinto de los vértices aislados. Esto se puede mostrar como ${\textstyle R}$ ${\displaystyle Q}$

${\displaystyle \mathbf {x} ^{\textsf {T}}Q\mathbf {x} =\mathbf {x} ^{\textsf {T}}RR^{\textsf {T}}\mathbf {x} \implies R^{\textsf {T}}\mathbf {x} =\mathbf {0} .}$

Esto tiene una solución si y solo si el gráfico tiene un componente bipartito conectado. ${\displaystyle \mathbf {x} \neq \mathbf {0} }$

multigrafos dirigidos

Se puede definir un análogo de la matriz laplaciana para multigrafos dirigidos. ^[7] En este caso la matriz laplaciana L se define como

${\displaystyle L=D-A}$

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).

Implementaciones de software de código abierto

• Ciencia ficción ^[8]
• RedX ^[9]
• Julia ^[10]

Software de la aplicacion

• Agrupación espectral de scikit-learn ^[11]
• PyGSP: procesamiento de señales gráficas en Python ^[12]
• megaman: aprendizaje múltiple para millones de puntos ^[13]
• suaveG ^[14]
• Detección del punto de cambio laplaciano para gráficos dinámicos (KDD 2020) ^[15]
• LaplacianOpt (un paquete de Julia para maximizar el segundo valor propio de gráficos ponderados de Laplacian) ^[16]
• LigMG (MultiGrid de gráfico irregular grande) ^[17]
• Laplacianos.jl ^[18]

Ver también

• Matriz de rigidez
• Distancia de resistencia
• Matriz de tasas de transición
• Cálculo sobre gráficos ponderados finitos
• Transformada gráfica de Fourier

Referencias

1. Chung, Fan (1997) [1992]. Teoría de grafos espectrales. Sociedad Matemática Estadounidense. ISBN 978-0821803158.
2. Smola, Alejandro J.; Kondor, Risi (2003), "Núcleos y regularización en gráficos", Teoría del aprendizaje y máquinas del núcleo: 16ª Conferencia anual sobre teoría del aprendizaje y 7º Taller del núcleo, COLT/Kernel 2003, Washington, DC, EE. UU., 24 al 27 de agosto de 2003, Actas , Apuntes de conferencias sobre informática, vol. 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.
3. Godsil, C.; Royle, G. (2001). Teoría de Grafos Algebraicos, Textos de Posgrado en Matemáticas . Springer-Verlag.
4. Satoshi Furutani; Toshiki Shibahara; Mitsuaki Akiyama; Kunio Hato; Masaki Aída (2020). Procesamiento de señales gráficas para gráficos dirigidos basado en el laplaciano hermitiano (PDF) . ECML PKDD 2019: Aprendizaje automático y descubrimiento de conocimiento en bases de datos. págs. 447–463. doi :10.1007/978-3-030-46150-8_27.
5. Morbidi, F. (2013). "El Protocolo de Consenso Deformado" (PDF) . Automática . 49 (10): 3049–3055. doi :10.1016/j.automatica.2013.07.006. S2CID  205767404.
6. Cvetković, Dragoš; Simić, Slobodan K. (2010). "Hacia una teoría espectral de gráficos basada en el laplaciano sin signos, III". Análisis Aplicable y Matemática Discreta . 4 (1): 156–166. doi : 10.2298/AADM1000001C . ISSN  1452-8630. JSTOR  43671298.
7. 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.
8. "CienciaPy". GitHub . 4 de octubre de 2023.
9. "RedX". GitHub . 4 de octubre de 2023.
10. "Julia". GitHub . 4 de octubre de 2023.
11. "2.3. Agrupación".
12. "PyGSP: procesamiento de señales gráficas en Python". GitHub . 23 de marzo de 2022.
13. "Megaman: aprendizaje múltiple para millones de puntos". GitHub . 14 de marzo de 2022.
14. "SuaveG". GitHub . 17 de septiembre de 2020.
15. "Anuncio de nuestro artículo en KDD 2020".
16. "Harshangrjn/LaplacianOpt.jl". GitHub . 2 de febrero de 2022.
17. "LigMG (Large Irregular Graph MultiGrid): un solucionador laplaciano de gráficos de memoria distribuida para grandes gráficos irregulares". GitHub . 5 de enero de 2022.
18. "Laplacianos.jl". GitHub . 11 de marzo de 2022.