matriz laplaciana

En el campo matemático de la teoría de grafos , la matriz laplaciana , también llamada laplaciana de grafos , matriz de admitancia , matriz de Kirchhoff o laplaciana discreta , es una representación matricial de un grafo . Nombrada en honor a Pierre-Simon Laplace , la matriz laplaciana de grafos puede considerarse como una forma matricial del operador laplaciano discreto negativo en un grafo que aproxima el laplaciano continuo negativo obtenido mediante el método de diferencias finitas .

La matriz laplaciana se relaciona con muchas propiedades funcionales de los grafos. El teorema de Kirchhoff se puede usar para calcular el número de árboles de expansión para un grafo dado. El corte más disperso de un grafo se puede aproximar mediante el vector de Fiedler —el vector propio correspondiente al segundo valor propio más pequeño del laplaciano del grafo— como lo establece la desigualdad de Cheeger . La descomposición espectral de la matriz laplaciana permite la construcción de incrustaciones de baja dimensión que aparecen en muchas aplicaciones de aprendizaje automático y determina una disposición espectral en el dibujo de grafos . El procesamiento de señales basado en grafos se basa en la transformada de Fourier de grafos que extiende la transformada discreta de Fourier tradicional al sustituir la base estándar de sinusoides complejos por los vectores propios de la matriz laplaciana de un grafo correspondiente a la señal.

La matriz laplaciana es la más fácil de definir para un grafo simple , pero es más común en aplicaciones para grafos con pesos en sus aristas , es decir, con pesos en sus aristas (las entradas de la matriz de adyacencia del grafo) . La teoría espectral de grafos relaciona las propiedades de un grafo con un espectro, es decir, los valores y vectores propios de matrices asociadas al grafo, como su matriz de adyacencia o la matriz laplaciana. Los pesos desequilibrados pueden afectar negativamente al espectro de la matriz, lo que requiere la normalización (un escalado de columnas y filas de las entradas de la matriz), dando como resultado matrices de adyacencia y laplacianas normalizadas.

Definiciones para gráficos simples

matriz laplaciana

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

L_{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{si}}\ i=j\\-1&{\mbox{si}}\ i\neq j\ {\mbox{y}}\ v_{i}{\mbox{ es adyacente a }}v_{j}\\0&{\mbox{en otro caso}},\end{cases}}

o equivalentemente por la matriz

L=DA,

donde D es la matriz de grados y A es la matriz de adyacencia del grafo . Dado que ${\textstyle G}$ es un gráfico simple, ${\textstyle A}$ Solo contiene 1s o 0s y todos los elementos de su diagonal son 0s.

Aquí tenemos un ejemplo sencillo de un grafo no dirigido etiquetado y su matriz laplaciana.

Observamos que, en el caso del grafo no dirigido, 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 cero (lo que implica directamente que la matriz laplaciana es singular).

Para grafos dirigidos , se puede utilizar el grado de entrada o el grado de salida , dependiendo de la aplicación, como en el siguiente ejemplo:

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

Matriz laplaciana para un grafo no dirigido mediante la matriz de incidencia orientada.

El ${\textstyle |v|\times |e|}$ matriz de incidencia orientada B con elemento B _ve para el vértice v y la arista e (que conecta vértices ) ${\textstyle v_{i}}$ y ${\textstyle v_{j}}$ , con i ≠ j ) se define por

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 en esta definición las aristas están técnicamente dirigidas, sus direcciones pueden ser arbitrarias, dando como resultado el mismo laplaciano simétrico. ${\textstyle |v|\times |v|}$ matriz L definida como

L=BB^{\textsf {T}}

dónde ${\textstyle B^{\textsf {T}}}$ es la transpuesta de la matriz B.

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

Laplaciano simétrico para un grafo dirigido

La matriz laplaciana de un grafo dirigido es, por definición, generalmente no simétrica, mientras que, por ejemplo, el agrupamiento espectral tradicional se desarrolla principalmente para grafos no dirigidos con adyacencia y matrices laplacianas simétricas. Un enfoque sencillo para aplicar técnicas que requieren simetría consiste en transformar 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 grafo no dirigido podría definirse, por ejemplo, como una suma booleana de la matriz de adyacencia. $A$ del grafo dirigido original y su transpuesta matricial $A^{T}$ , donde las entradas cero y uno de $A$ se tratan como valores lógicos, en lugar de numéricos, como en el siguiente ejemplo:

Normalización de la matriz laplaciana

Un vértice con un grado elevado, también llamado nodo pesado , genera una entrada diagonal grande en la matriz laplaciana que domina sus propiedades. La normalización busca igualar la influencia de estos vértices a la de los demás, dividiendo las entradas de la matriz laplaciana entre sus grados. Para evitar la división por cero, los vértices aislados con grado cero se excluyen del proceso de normalización.

Laplaciano normalizado simétricamente

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

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

dónde $D^{+}$ es la inversa de Moore-Penrose de la matriz de grados.

Los elementos de ${\textstyle L^{\text{sym}}}$ quedan así dados por

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 solo si la matriz de adyacencia es simétrica.

Para una matriz de adyacencia no simétrica de un grafo dirigido, se puede utilizar tanto el grado de entrada como el grado de salida para la normalización:

Laplacianos normalizados izquierdo (paseo aleatorio) y derecho

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

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

dónde $D^{+}$ es la inversa de Moore-Penrose . Los elementos de ${\textstyle L^{\text{rw}}}$ son dados por

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

LD^{+}=I-AD^{+}

.

La matriz laplaciana normalizada izquierda o derecha es simétrica si la matriz de adyacencia es simétrica y el grafo es regular. De lo contrario, la matriz laplaciana normalizada izquierda o derecha es asimétrica. Por ejemplo,

El ejemplo también demuestra que si $G$ no tiene vértices aislados, entonces $D^{+}A$ estocástico derecho y, por lo tanto, es la matriz de un paseo aleatorio , de modo que el laplaciano normalizado izquierdo $L^{\text{rw}}:=D^{+}L=I-D^{+}A$ tiene cada fila sumando cero. Por lo tanto, a veces llamamos alternativamente $L^{\text{rw}}$ el laplaciano normalizado de paseo aleatorio . En el laplaciano normalizado derecho, menos utilizado $LD^{+}=I-AD^{+}$ cada columna suma cero ya que $AD^{+}$ es estocástico izquierdo .

Para una matriz de adyacencia no simétrica de un grafo 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 $D_{\text{out}}^{+}A$ , mientras que el laplaciano normalizado de grado de entrada derecho con sumas de columna todas 0 contiene estocástico izquierdo $AD_{\text{in}}^{+}$ .

Definiciones para grafos con aristas ponderadas

En aplicaciones comunes, los grafos con aristas ponderadas se definen convenientemente mediante sus matrices de adyacencia, donde los valores de las entradas son numéricos y ya no se limitan a ceros y unos. En el agrupamiento espectral y el procesamiento de señales basado en grafos , donde los vértices del grafo 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 da como resultado que todos los pesos sean no negativos, correspondiendo informalmente valores mayores a pares de puntos de datos más similares. El uso de la correlación y la anticorrelación entre los puntos de datos conduce naturalmente a pesos tanto positivos como negativos. La mayoría de las definiciones para grafos 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

L=D-A,

donde D es la matriz de grados y A es la matriz de adyacencia del grafo.

Para grafos dirigidos , se puede utilizar el grado de entrada o el grado de salida , dependiendo de la aplicación, como en el siguiente ejemplo:

Se permiten los bucles en el grafo, que se manifiestan mediante entradas distintas de cero en la diagonal principal de la matriz de adyacencia, pero no afectan a los valores laplacianos del grafo.

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

Para grafos con aristas ponderadas, se puede definir una matriz de incidencia ponderada B y usarla para construir el laplaciano simétrico correspondiente como $L=BB^{\textsf {T}}$ Un enfoque alternativo más limpio, que se describe aquí, consiste en separar los pesos de la conectividad: se continúa utilizando la matriz de incidencia como en los grafos regulares y se introduce una matriz que solo contiene 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 dada y longitud unitaria, donde los valores de rigidez desempeñan el papel de los pesos de las aristas del grafo.

Por lo tanto, reutilizamos la definición de lo ingrávido. ${\textstyle |v|\times |e|}$ matriz de incidencia B con elemento B _ve para el vértice v y la arista e (que conecta vértices ) ${\textstyle v_{i}}$ y ${\textstyle v_{j}}$ , con i > j ) definido por

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 diagonal. ${\textstyle |e|\times |e|}$ matriz 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, lo que sigue dando como resultado el mismo laplaciano simétrico. ${\textstyle |v|\times |v|}$ matriz L definida como

L=BWB^{\textsf {T}}

dónde ${\textstyle B^{\textsf {T}}}$ es la transpuesta de la matriz B.

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

Laplaciano simétrico para un grafo dirigido

Al igual que en los grafos simples, la matriz laplaciana de un grafo dirigido ponderado es, por definición, generalmente no simétrica. La simetría se puede imponer convirtiendo primero el grafo dirigido original en un grafo no dirigido antes de construir la matriz laplaciana. La matriz de adyacencia del grafo no dirigido podría, por ejemplo, definirse como una suma de la matriz de adyacencia. $A$ del grafo dirigido original y su transpuesta matricial $A^{T}$ como en el siguiente ejemplo:

donde las entradas cero y uno de $A$ se tratan como numéricos, en lugar de lógicos como en los gráficos simples, valores, lo que explica la diferencia en los resultados: para gráficos simples, el gráfico simetrizado todavía necesita ser simple con su matriz de adyacencia simetrizada que tenga solo 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.

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 grafos simples, lograr que todos los elementos de la diagonal de la matriz laplaciana sean unitarios, escalando también los elementos fuera de la diagonal de forma correspondiente. En un grafo ponderado , un vértice puede tener un grado elevado debido a un número reducido de aristas conectadas pero con pesos elevados, al igual que debido a un gran número de aristas conectadas con pesos unitarios.

Los bucles internos del grafo, es decir, las entradas distintas de cero en la diagonal principal de la matriz de adyacencia, no afectan a los valores laplacianos del grafo, pero puede ser necesario tenerlos en cuenta para el cálculo de los factores de normalización.

Laplaciano normalizado simétricamente

El laplaciano normalizado simétricamente se define como

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 $D^{+}$ es la inversa de Moore-Penrose . Dado que la matriz de grados D es diagonal, su raíz cuadrada recíproca es ${\textstyle (D^{+})^{1/2}}$ es simplemente la matriz diagonal cuyos elementos diagonales son los recíprocos de las raíces cuadradas de los elementos diagonales de D. Si todos los pesos de las aristas son no negativos, entonces todos los valores de grado también son automáticamente no negativos y, por lo tanto, cada valor de grado tiene una única raíz cuadrada positiva. Para evitar la división por cero, los vértices con grado cero se excluyen del proceso de normalización, como en el siguiente ejemplo:

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

La matriz laplaciana normalizada simétrica también se puede escribir como

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

utilizando la ingravidez ${\textstyle |v|\times |e|}$ matriz de incidencia B y la diagonal ${\textstyle |e|\times |e|}$ matriz W que contiene los pesos de los bordes y define la nueva ${\textstyle |v|\times |e|}$ matriz de incidencia ponderada ${\textstyle S=(D^{+})^{1/2}BW^{{1}/{2}}}$ cuyas filas están indexadas por los vértices y cuyas columnas están indexadas por las aristas de G de tal manera que cada columna correspondiente a una arista e = {u, v} tiene una entrada ${\textstyle {\frac {1}{\sqrt {d_{u}}}}}$ en la fila correspondiente a u , una entrada ${\textstyle -{\frac {1}{\sqrt {d_{v}}}}}$ en la fila correspondiente a v , y tiene 0 entradas en cualquier otro lugar.

Laplaciano normalizado de paseo aleatorio

El laplaciano normalizado de caminata aleatoria se define como

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 ${\textstyle D^{+}}$ se define simplemente como una matriz diagonal, cuyas entradas diagonales son los recíprocos 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. ${\textstyle L_{i,i}^{\text{rw}}}$ a 0. Los elementos de la matriz de ${\textstyle L^{\text{rw}}}$ son dados por

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 ${\textstyle L^{\text{rw}}=I-P}$ , dónde ${\textstyle P=D^{+}A}$ es simplemente la matriz de transición de un caminante aleatorio en el grafo, suponiendo pesos no negativos. Por ejemplo, sea ${\textstyle e_{i}}$ denotemos el i-ésimo vector base estándar . Entonces ${\textstyle x=e_{i}P}$ 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. ${\textstyle i}$ ; es decir, ${\textstyle x_{j}=\mathbb {P} \left(v_{i}\to v_{j}\right)}$ . De forma más general, si el vector ${\textstyle x}$ es una distribución de probabilidad de la ubicación de un caminante aleatorio en los vértices del grafo, entonces ${\textstyle x'=xP^{t}}$ es la distribución de probabilidad del caminante después ${\textstyle t}$ pasos.

El laplaciano normalizado de paseo aleatorio también puede llamarse laplaciano normalizado izquierdo. $L^{\text{rw}}:=D^{+}L$ ya que la normalización se realiza multiplicando el laplaciano por la matriz de normalización $D^{+}$ a la izquierda. Tiene cada fila sumando cero ya que $P=D^{+}A$ es estocástico por la derecha , suponiendo que todos los pesos son no negativos.

En el laplaciano normalizado derecho, menos utilizado $LD^{+}=I-AD^{+}$ cada columna suma cero ya que $AD^{+}$ es estocástico izquierdo .

Para una matriz de adyacencia no simétrica de un grafo 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 $D_{\text{out}}^{+}A$ , mientras que el laplaciano normalizado de grado de entrada derecho con sumas de columna todas 0 contiene estocástico izquierdo $AD_{\text{in}}^{+}$ .

Pesos negativos

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

La presencia de pesos negativos puede resultar naturalmente en sumas de filas y/o columnas iguales a cero para vértices no aislados. Un vértice con una gran suma de filas de pesos positivos y una suma de filas de pesos negativos igualmente grande, que en conjunto suman cero, podría considerarse un nodo pesado y ambos valores grandes se escalarían, mientras que la entrada diagonal permanece en cero, como en el caso de un vértice aislado.
Los pesos negativos también pueden dar como resultado sumas negativas de filas y/o columnas, 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 esgrimir argumentos para tomar el valor absoluto de las sumas de filas y/o columnas con el fin de normalizar, tratando así un posible valor -1 como una entrada unitaria 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étrica .
L es semidefinida positiva (es decir, ${\textstyle \lambda _{i}\geq 0}$ a pesar de ${\textstyle i}$ ). Esto se puede ver en el hecho de que el laplaciano es simétrico y diagonalmente dominante .
L es una matriz M (sus entradas fuera de la diagonal son no positivas, pero las partes reales de sus valores propios son no negativas).
La suma de cada fila y columna de L es cero. De hecho, en la suma, el grado del vértice se incrementa en "-1" por cada vecino.
En consecuencia, ${\textstyle \lambda _{0}=0}$ , porque el vector ${\textstyle \mathbf {v} _{0}=(1,1,\dots ,1)}$ Satisface ${\textstyle L\mathbf {v} _{0}=\mathbf {0} .}$ Esto también implica que la matriz laplaciana es singular.
El número de componentes conexas en el grafo es la dimensión del espacio nulo del laplaciano y la multiplicidad algebraica del valor propio 0.
El valor propio no nulo más pequeño de L se denomina brecha espectral .
El segundo valor propio más pequeño de L (que podría ser cero) es la conectividad algebraica (o valor de Fiedler ) de G y se aproxima al corte más disperso de un grafo.
El laplaciano es un operador en el espacio vectorial n-dimensional de funciones ${\textstyle f:V\to \mathbb {R} }$ , dónde ${\textstyle V}$ es el conjunto de vértices de G, y ${\textstyle n=|V|}$ .
Cuando G es k-regular , el laplaciano normalizado es: ${\textstyle {\mathcal {L}}={\tfrac {1}{k}}L=I-{\tfrac {1}{k}}A}$ donde A es la matriz de adyacencia e I es una matriz identidad.
Para un grafo con múltiples componentes conexas , L es una matriz diagonal por 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 por permutación a una matriz diagonal por bloques).
La traza de la matriz laplaciana L es igual a ${\textstyle 2m}$ dónde ${\textstyle m}$ es el número de aristas del grafo considerado.
Ahora consideremos una descomposición en valores propios de ${\textstyle L}$ , con autovectores de norma unitaria ${\textstyle \mathbf {v} _{i}}$ y los autovalores correspondientes ${\textstyle \lambda _{i}}$ :

{\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}}

Porque ${\textstyle \lambda _{i}}$ se puede escribir como el producto interno del vector ${\textstyle M\mathbf {v} _{i}}$ con ello, esto demuestra que ${\textstyle \lambda _{i}\geq 0}$ y por lo tanto los valores propios de ${\textstyle L}$ son todos no negativos.

Todos los autovalores del laplaciano simétrico normalizado satisfacen 0 = μ ₀ ≤ … ≤ μ _n−1 ≤ 2. Estos autovalores (conocidos como el espectro del laplaciano normalizado) se relacionan bien con otros invariantes de grafos para grafos generales. ^{[ 1 ]}

Se puede comprobar que:

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

,

es decir, ${\textstyle L^{\text{rw}}}$ es similar al laplaciano normalizado ${\textstyle L^{\text{sym}}}$ . Por esta razón, incluso si ${\textstyle L^{\text{rw}}}$ En general, no es simétrico, tiene autovalores reales, exactamente los mismos que los autovalores del laplaciano simétrico normalizado. ${\textstyle L^{\text{sym}}}$ .

Interpretación como el operador de Laplace discreto que aproxima el laplaciano continuo.

La matriz laplaciana del grafo puede verse además como una forma matricial del operador laplaciano discreto negativo en un grafo que aproxima el operador laplaciano continuo negativo obtenido por el método de diferencias finitas . (Véase la 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 arista, y no hay restricciones en ningún punto de la cuadrícula, lo que corresponde al caso de la condición de contorno de Neumann homogénea , 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 aristas, lo que lleva a una matriz laplaciana de tamaño infinito.

Generalizaciones y extensiones de la matriz laplaciana

Laplaciano generalizado

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

{\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}}

Nótese que el laplaciano ordinario es un laplaciano generalizado.

Matriz de admitancia de un circuito de CA

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 permanece simétrica, en lugar de ser hermitiana . Dicha matriz se denomina habitualmente " matriz de admitancia ", denotada $Y$ , en lugar de un "Laplaciano". Esta es una de las raras aplicaciones que dan lugar a matrices simétricas complejas .

Laplaciano magnético

Existen otras situaciones en las que las entradas de la matriz de adyacencia son de valor complejo, y el laplaciano se convierte en una matriz hermitiana . El laplaciano magnético para un grafo dirigido con pesos reales $w_{ij}$ se construye como el producto de Hadamard de la matriz simétrica real del laplaciano simetrizado y la matriz de fase hermitiana con entradas complejas

\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 $q$ se denomina carga eléctrica. ^{[ 4 ]} En el siguiente ejemplo $q=1/4$ :

Laplaciano deformado

El laplaciano deformado se define comúnmente como

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

dónde ${\textstyle I}$ es la matriz identidad, ${\textstyle A}$ es la matriz de adyacencia, ${\textstyle D}$ es la matriz de grados y ${\textstyle s}$ es un número (de valor complejo). ^{[ 5 ]} El laplaciano estándar es simplemente ${\textstyle \Delta (1)}$ y ${\textstyle \Delta (-1)=D+A}$ es el laplaciano sin signo.

Laplaciano sin signo

El laplaciano sin signo se define como

Q=D+A

dónde $D$ es la matriz de grados y $A$ es la matriz de adyacencia. ^{[ 6 ]} Al igual que el laplaciano con signo $L$ , el laplaciano sin signo $Q$ también es semidefinido positivo ya que puede ser factorizado como

Q=RR^{\textsf {T}}

dónde ${\textstyle R}$ es la matriz de incidencia. $Q$ tiene un vector propio de 0 si y solo si tiene una componente bipartita conexa (los vértices aislados son componentes bipartitas conexas). Esto se puede demostrar como

\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 $\mathbf {x} \neq \mathbf {0}$ si y solo si el grafo tiene un componente bipartito conexo.

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

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

Software de aplicación

Agrupamiento espectral de scikit-learn ^{[ 11 ]}
PyGSP: Procesamiento de señales gráficas en Python ^{[ 12 ]}
megaman: Aprendizaje de variedades para millones de puntos ^{[ 13 ]}
smoothG ^{[ 14 ]}
Detección de puntos de cambio laplacianos para grafos dinámicos (KDD 2020) ^{[ 15 ]}
LaplacianOpt (un paquete de Julia para maximizar el segundo valor propio del laplaciano de grafos ponderados) ^{[ 16 ]}
LigMG (Multicuadrícula de grafos irregulares grandes) ^{[ 17 ]}
Laplacianos.jl ^{[ 18 ]}

Véase también

Referencias

1 2 3 Chung, Fan (1997) [1992]. Teoría espectral de grafos . Sociedad Matemática Americana. ISBN 978-0821803158.
↑ 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, pp. 144-158 , CiteSeerX 10.1.1.3.7020 , doi : 10.1007/978-3-540-45167-9_12 , ISBN 978-3-540-40720-1.
↑ Godsil, C.; Royle, G. (2001). Teoría algebraica de grafos, Textos de posgrado en matemáticas . Springer-Verlag.
↑ Satoshi Furutani; Toshiki Shibahara; Mitsuaki Akiyama; Kunio Hato; Masaki Aida (2020). Procesamiento de señales gráficas para grafos dirigidos basado en el laplaciano hermitiano (PDF) . ECML PKDD 2019: Aprendizaje automático y descubrimiento de conocimiento en bases de datos. pp. 447–463 . doi : 10.1007/978-3-030-46150-8_27 .
^ 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 .
↑ Cvetković, Dragoš; Simić, Slobodan K. (2010). "Hacia una teoría espectral de grafos basada en el laplaciano sin signo, III" . Applicable Analysis and Discrete Mathematics . 4 (1): 156– 166. doi : 10.2298/AADM1000001C . ISSN 1452-8630 . JSTOR 43671298 .
↑ Chaiken, S.; Kleitman, D. (1978). "Teoremas de árboles matriciales" . Journal of Combinatorial Theory, Series A. 24 ( 3): 377– 381. doi : 10.1016/0097-3165(78)90067-5 . ISSN 0097-3165 .
↑ "SciPy" . GitHub . 4 de octubre de 2023.
↑ "NetworkX" . GitHub . 4 de octubre de 2023.
↑ "Julia" . GitHub . 4 de octubre de 2023.
↑ "2.3. Agrupación" .
↑ "PyGSP: Procesamiento de señales gráficas en Python" . GitHub . 23 de marzo de 2022.
↑ "Megaman: Aprendizaje de variedades para millones de puntos" . GitHub . 14 de marzo de 2022.
↑ "SmoothG" . GitHub . 17 de septiembre de 2020.
↑ "Presentación de nuestro artículo en KDD 2020" . 2 de julio de 2020.
↑ "Harshangrjn/LaplacianOpt.jl" . GitHub . 2 de febrero de 2022.
↑ "LigMG (Large Irregular Graph MultiGrid): un solucionador laplaciano de grafos de memoria distribuida para grafos irregulares grandes" . GitHub . 5 de enero de 2022.
↑ "Laplacians.jl" . GitHub . 11 de marzo de 2022.

[Fan_Chung-1] 1 2 3 Chung, Fan (1997) [1992]. Teoría espectral de grafos . 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, pp. 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 algebraica de grafos, 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 grafos dirigidos basado en el laplaciano hermitiano (PDF) . ECML PKDD 2019: Aprendizaje automático y descubrimiento de conocimiento en bases de datos. pp. 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" . Applicable Analysis and Discrete Mathematics . 4 (1): 156– 166. doi : 10.2298/AADM1000001C . ISSN 1452-8630 . JSTOR 43671298 .

[Chaiken1978-7] Chaiken, S.; Kleitman, D. (1978). "Teoremas de árboles matriciales" . Journal of Combinatorial Theory, Series 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. Agrupación" .

[12] "PyGSP: Procesamiento de señales gráficas en Python" . GitHub . 23 de marzo de 2022.

[13] "Megaman: Aprendizaje de variedades para millones de puntos" . GitHub . 14 de marzo de 2022.

[14] "SmoothG" . GitHub . 17 de septiembre de 2020.

[15] "Presentación de nuestro artículo en KDD 2020" . 2 de julio de 2020.

[16] "Harshangrjn/LaplacianOpt.jl" . GitHub . 2 de febrero de 2022.

[17] "LigMG (Large Irregular Graph MultiGrid): un solucionador laplaciano de grafos de memoria distribuida para grafos irregulares grandes" . GitHub . 5 de enero de 2022.

[18] "Laplacians.jl" . GitHub . 11 de marzo de 2022.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]