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 un grafo . La matriz laplaciana gráfica, que recibe su nombre de Pierre-Simon Laplace , puede considerarse como una forma matricial del operador de Laplace discreto negativo en un grafo que se aproxima al laplaciano continuo negativo obtenido por 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 disperso 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 laplaciano del gráfico), como se establece mediante 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 del gráfico 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 por aristas , es decir, con pesos en sus aristas (las entradas de la matriz de adyacencia del gráfico) . La teoría de grafos espectrales relaciona las propiedades de un grafo con un espectro, es decir, valores propios y vectores propios de matrices asociadas con el grafo, como su matriz de adyacencia o matriz laplaciana. Los pesos desequilibrados pueden afectar de forma indeseable al espectro de la matriz, lo que lleva a la necesidad de normalización (un escalado de columnas/filas de las entradas de la matriz), lo que da como resultado matrices de adyacencia y laplacianas normalizadas.

Definiciones paragráficos simples

Matriz laplaciana

Dado un gráfico simple con vértices , su matriz laplaciana se define elemento por elemento 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 grafo. Como es un grafo simple, solo contiene 1 o 0 y sus elementos diagonales son todos 0. ${\textstyle G}$ ${\textstyle A}$

A continuación se muestra un ejemplo simple de un gráfico etiquetado, no dirigido y su matriz laplaciana.

Observamos para el grafo 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 el grado de salida , según la aplicación, como en el siguiente ejemplo:

En el grafo dirigido, tanto la matriz de adyacencia como la matriz laplaciana son asimétricas. En su matriz laplaciana, las sumas de las columnas o las sumas de las filas son cero, dependiendo de si se ha utilizado el grado de entrada o de salida .

Matriz laplaciana para un grafo no dirigido a través de la matriz de incidencia orientada

La matriz de incidencia orientada B con elemento B _ve para el vértice v y la arista e (que conecta los 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}}}$

donde es la matriz transpuesta de B . ${\textstyle B^{\textsf {T}}}$

Un producto alternativo define el llamado Laplaciano basado en aristas, a diferencia de la matriz Laplaciana L original basada en vértices, 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 grafo dirigido es, por definición, generalmente no simétrica, mientras que, por ejemplo, la agrupación espectral tradicional se desarrolló principalmente para grafos no dirigidos con adyacencia simétrica y matrices laplacianas. Un enfoque trivial para aplicar técnicas que requieren la simetría es convertir el grafo dirigido original en un grafo 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 matriz transpuesta , donde las entradas cero y uno de se tratan como valores lógicos, en lugar de 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 los demás 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 grados cero se excluyen del proceso de normalización.

Laplaciano normalizado simétricamente

La matriz laplaciana normalizada simétricamente 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 ${\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 normalizada simétricamente 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 (caminata aleatoria) y derecho

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

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

donde es 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 derecha se define como

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

La matriz laplaciana normalizada por la izquierda o por la 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 es estocástico por la derecha y, por lo tanto, es la matriz de un paseo aleatorio , de modo que el laplaciano normalizado por la izquierda tiene cada fila que suma cero. Por lo tanto, a veces llamamos alternativamente al paseo aleatorio laplaciano normalizado. En el laplaciano normalizado por la derecha, que se usa con menos frecuencia, 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 el grado de salida para la normalización:

El laplaciano normalizado de grado de salida izquierdo con sumas de filas todas 0 se relaciona con el estocástico derecho , mientras que el laplaciano normalizado de grado de entrada derecho con sumas de columnas todas 0 contiene el estocástico izquierdo . ${\displaystyle D_{\text{out}}^{+}A}$ ${\displaystyle AD_{\text{in}}^{+}}$

Definiciones para gráficos con aristas ponderadas

Los gráficos con aristas ponderadas, que son comunes en las aplicaciones, se definen convenientemente mediante sus matrices de adyacencia, donde los valores de las entradas son numéricos y ya no están limitados 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 las aristas 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 y los valores más grandes correspondan informalmente 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 pesos positivos y negativos. La mayoría de las definiciones de gráficos simples se extienden trivialmente al caso estándar de pesos no negativos, mientras que los pesos negativos requieren más atención, especialmente en la normalización.

Matriz laplaciana

La matriz laplaciana se define 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 el grado de salida , según la aplicación, como en el siguiente ejemplo:

Se permiten bucles propios del gráfico, que se manifiestan mediante entradas distintas de cero en la diagonal principal de la matriz de adyacencia, 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 los grafos 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 claro, descrito aquí, es separar los pesos de la conectividad: continuar usando la matriz de incidencia como para los grafos regulares e introducir una matriz que contenga solo 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 rigideces dadas y longitud unitaria, donde los valores de las rigideces juegan el papel de los pesos de las aristas del grafo. ${\displaystyle L=BB^{\textsf {T}}}$

De este modo, reutilizamos la definición de la matriz de incidencia sin peso B con elemento B _ve para el vértice v y la arista e (que conecta los 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 las aristas. 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}}}$

donde es 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 en el caso de los grafos simples, la matriz laplaciana de un grafo ponderado dirigido es, por definición, generalmente no simétrica. La simetría se puede reforzar convirtiendo el grafo dirigido original en un grafo no dirigido antes de construir el laplaciano. La matriz de adyacencia del grafo no dirigido se podría definir, por ejemplo, como una suma de la matriz de adyacencia del grafo 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 con su matriz de adyacencia simetrizada que solo tiene valores lógicos, 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 utilizando el grado de entrada y el grado de salida , como en el siguiente ejemplo:

La suma del laplaciano de grado de salida transpuesto y el laplaciano de grado de entrada es igual a la matriz laplaciana simétrica.

Normalización de la matriz laplaciana

El objetivo de la normalización es, como en el caso de los gráficos simples, hacer que las entradas diagonales de la matriz laplaciana sean todas unitarias, y escalar también las entradas fuera de la diagonal en consecuencia. En un gráfico ponderado , un vértice puede tener un grado alto debido a una pequeña cantidad de aristas conectadas pero con pesos grandes, así como también 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 puede ser necesario contarlos para el cálculo de los factores de normalización.

Laplaciano normalizado simétricamente

El laplaciano normalizado simétricamente 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 las aristas son no negativos, entonces todos los valores de grados son automáticamente también no negativos y, por lo tanto, cada valor de grado tiene una raíz cuadrada positiva única. Para evitar la división por cero, los vértices con grados cero se excluyen del proceso de normalización, como en el siguiente ejemplo: ${\displaystyle D^{+}}$ ${\textstyle (D^{+})^{1/2}}$

El laplaciano normalizado simétricamente es una matriz simétrica si y sólo si la matriz de adyacencia A es simétrica y las entradas diagonales de D son no negativas, en cuyo caso podemos utilizar el término laplaciano normalizado simétrico .

La matriz laplaciana normalizada simétrica 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 sin peso B y la matriz diagonal W que contiene los pesos de los bordes y definiendo la nueva matriz de incidencia ponderada 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 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}}}}}$

Laplaciano normalizado de paseo aleatorio

El laplaciano normalizado de paseo aleatorio se define como

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

donde D es la matriz de grado. Dado que la matriz de grado D es diagonal, su inversa se define simplemente como una matriz diagonal, que tiene entradas diagonales que son las 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 de laplaciano normalizado de caminata aleatoria 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, sea que denote 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 por paseo aleatorio también se puede llamar laplaciano normalizado por 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 por la derecha , asumiendo que todos los pesos son no negativos. ${\displaystyle L^{\text{rw}}:=D^{+}L}$ ${\displaystyle D^{+}}$ ${\displaystyle P=D^{+}A}$

En el laplaciano normalizado a la derecha, de uso menos frecuente, cada columna suma cero, ya que es estocástico a 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 el grado de salida para la normalización:

El laplaciano normalizado de grado de salida izquierdo con sumas de filas todas 0 se relaciona con el estocástico derecho , mientras que el laplaciano normalizado de grado de entrada derecho con sumas de columnas todas 0 contiene el estocástico izquierdo . ${\displaystyle D_{\text{out}}^{+}A}$ ${\displaystyle AD_{\text{in}}^{+}}$

Pesos negativos

Los pesos negativos presentan varios desafíos para la normalización:

• La presencia de pesos negativos puede dar como resultado, naturalmente, sumas de filas y/o columnas de cero para vértices no aislados. Un vértice con una suma de filas de pesos positivos grande y una suma de filas de pesos negativos igualmente grande y negativa, que en conjunto sumen cero, podría considerarse un nodo pesado y ambos valores grandes podrían escalarse, mientras que la entrada diagonal permanece en cero, como en el caso de 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 de unidad legítima de la diagonal principal de la matriz laplaciana normalizada.

Propiedades

Para un grafo (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étrico .
• L es semidefinida positiva (es decir, para todo ). Esto se puede ver a partir del 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 todas las filas y 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, , debido a que 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 distinto de cero más pequeño 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 disperso de un gráfico.
• El laplaciano es un operador en el espacio vectorial n-dimensional de funciones , 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 similar a una permutación de una matriz diagonal de bloques).
• La traza de la matriz laplaciana L es igual a donde es el número de aristas del grafo considerado. ${\textstyle 2m}$ ${\textstyle m}$
• Consideremos ahora 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 puede escribirse como el producto interno del vector consigo mismo, esto demuestra que y por lo tanto 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 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 el operador discreto de Laplace que aproxima al laplaciano continuo

La matriz laplaciana del grafo puede verse además como una forma matricial del operador discreto negativo de Laplace en un grafo que se aproxima al operador continuo negativo de Laplace obtenido por el método de diferencias finitas . (Véase ecuación de Poisson discreta ) ^[2] En esta interpretación, cada vértice del grafo se trata como un punto de la cuadrícula; la conectividad local del vértice determina la plantilla de aproximación de 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 contorno homogénea de Neumann , es decir, contorno libre. Tal interpretación permite, por ejemplo, generalizar la matriz laplaciana al caso de grafos con un número infinito de vértices y bordes, lo que conduce 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.

Matriz de admitancia de un circuito de corriente alterna

El laplaciano de un grafo se introdujo por primera vez para modelar redes eléctricas. En una red eléctrica de corriente alterna (CA), las resistencias de valor real se reemplazan por impedancias de valor complejo. El peso de la arista ( i , j ) es, por convención, menos el recíproco de la impedancia directamente entre i y j . En los modelos de tales redes, las entradas de la matriz de adyacencia son complejas, pero la matriz de Kirchhoff sigue siendo simétrica, en lugar de ser hermítica . A una matriz de este tipo se la suele llamar " matriz de admitancia ", denotada como , en lugar de "laplaciano". Esta es una de las raras aplicaciones que dan lugar a matrices simétricas complejas . ${\displaystyle Y}$

Laplaciano magnético

Existen otras situaciones en las que las entradas de la matriz de adyacencia tienen valores complejos y el laplaciano se convierte en una matriz hermítica . El laplaciano magnético para un grafo 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 hermítica 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 la fenomenología de una partícula cargada libre en un grafo, que está sujeta a la acción de un campo magnético y el parámetro se llama 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 grado y s es un número (de valor complejo). ^[5]
El laplaciano estándar es simplemente y es el laplaciano sin signo. ${\textstyle \Delta (1)}$ ${\textstyle \Delta (-1)=D+A}$

Laplaciano sin signos

El laplaciano sin signo 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 se puede factorizar como ${\displaystyle D}$ ${\displaystyle A}$ ${\displaystyle L}$ ${\displaystyle Q}$

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

donde es 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 ${\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 donde si y solo si el gráfico tiene un componente conectado bipartito. ${\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 de salida 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 y tecnología ^[8]
• Red X ^[9]
• Julia ^[10]

Software de aplicación

• Agrupamiento 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 de puntos de cambio laplacianos para gráficos dinámicos (KDD 2020) ^[15]
• LaplacianOpt (un paquete de Julia para maximizar el segundo valor propio de Laplaciano en gráficos ponderados) ^[16]
• LigMG (Gráfico irregular grande multicuadrícula) ^[17]
• Laplacianos.jl ^[18]

Véase también

• Matriz de rigidez
• Distancia de resistencia
• Matriz de tasa de transición
• Cálculo sobre grafos finitos ponderados
• Gráfica de la transformada de Fourier

Referencias

1. Chung, Fan (1997) [1992]. Teoría de grafos espectrales. Sociedad Matemática Americana. ISBN 978-0821803158.
2. Smola, Alexander J.; Kondor, Risi (2003), "Núcleos y regularización en grafos", Teoría del aprendizaje y máquinas de núcleo: 16.ª conferencia anual sobre teoría del aprendizaje y 7.º taller de núcleos, COLT/Kernel 2003, Washington, DC, EE. UU., 24-27 de agosto de 2003, Actas , Lecture Notes in Computer Science, 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 Aida (2020). Procesamiento de señales gráficas para gráficos dirigidos basado en el laplaciano hermítico (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 grafos 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.
7. Chaiken, S.; Kleitman, D. (1978). "Teoremas del árbol matricial". Revista de teoría combinatoria, serie A. 24 ( 3): 377–381. doi : 10.1016/0097-3165(78)90067-5 . ISSN  0097-3165.
8. "SciPy". GitHub . 4 de octubre de 2023.
9. "NetworkX". GitHub . 4 de octubre de 2023.
10. "Julia". GitHub . 4 de octubre de 2023.
11. "2.3. Agrupamiento".
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. "SmoothG". 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 gráficos irregulares grandes". GitHub . 5 de enero de 2022.
18. "Laplacians.jl". GitHub . 11 de marzo de 2022.