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 grafo laplaciano , matriz de admitancia , matriz de Kirchhoff o laplaciana discreta , es una representación matricial de un grafo . La matriz laplaciana se puede utilizar para encontrar muchas propiedades útiles de un gráfico. Junto con el teorema de Kirchhoff , se puede utilizar para calcular el número de árboles de expansión para un gráfico dado. El corte más escaso de una gráfica se puede aproximar a través del segundo valor propio más pequeño de su laplaciano por la desigualdad de Cheeger. También se puede utilizar para construir incrustaciones de baja dimensión , que pueden ser útiles para una variedad de aplicaciones de aprendizaje automático .

Definición

Matriz laplaciana para gráficos simples

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

${\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 unos o ceros y sus elementos diagonales son todos ceros.${\textstyle G}$${\textstyle A}$

En el caso de gráficos dirigidos , se puede utilizar tanto el grado inferior como el superior , según la aplicación.

Los elementos de están dados por${\textstyle L}$

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

donde es el grado del vértice .${\displaystyle \operatorname {deg} (v_{i})}$${\displaystyle i}$

Laplaciano normalizado simétrico

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

${\displaystyle L^{\text{sym}}:=D^{-{\frac {1}{2}}}LD^{-{\frac {1}{2}}}=I-D^{-{\frac {1}{2}}}AD^{-{\frac {1}{2}}}}$,

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}}}$

Caminata aleatoria normalizada laplaciana

La matriz laplaciana normalizada de caminata aleatoria se define como:

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

Los elementos de están dados por${\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}}}$

Laplaciano generalizado

El laplaciano generalizado se define como: ^[2]${\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.

Ejemplo

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

Gráfico etiquetado	Matriz de grados	Matriz de adyacencia	Matriz laplaciana
	${\textstyle \left({\begin{array}{rrrrrr}2&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrrrr}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrrrr}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\-1&-1&0&-1&3&0\\0&0&0&-1&0&1\\\end{array}}\right)}$

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étrico .
• L es positivo-semidefinito (es decir, para todos ). Esto se verifica en la sección de la matriz de incidencia (a continuación). Esto también se puede ver por el hecho de que el laplaciano es simétrico y diagonalmente dominante .${\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).
• Cada suma de filas y suma de columnas de L es cero. De hecho, en la suma, el grado del vértice se suma con un "-1" para cada vecino.
• En consecuencia, porque el vector satisface Esto también implica que la matriz laplaciana es singular.${\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 autovalor 0.
• El valor propio más pequeño distinto de cero de L se llama brecha espectral .
• El segundo valor propio más pequeño de L (podría ser cero) es la conectividad algebraica (o valor de Fiedler ) de G y se aproxima al corte más escaso de una gráfica.
• El laplaciano es un operador en el espacio vectorial de funciones n-dimensional , 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 de 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 es el número de aristas del gráfico considerado.${\textstyle 2m}$${\textstyle m}$

Matriz de incidencia

Defina una matriz de incidencia orientada M con el elemento M _ev para la arista e (que conecta el vértice i y j , con i  >  j ) y el vértice v dado por${\textstyle |e|\times |v|}$

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

Entonces la matriz laplaciana L satisface

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

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

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 y, por lo tanto, los valores propios de no son negativos.${\textstyle \lambda _{i}}$${\textstyle M\mathbf {v} _{i}}$${\textstyle \lambda _{i}\geq 0}$${\textstyle L}$

Laplaciano deformado

El laplaciano deformado se define comúnmente como

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

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

Laplaciano sin signo

El laplaciano sin signo se define como

${\displaystyle Q=D+A}$

donde es la matriz de grados y es la matriz de adyacencia. ^[4] 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 conectado bipartito 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 donde si y solo si el gráfico tiene un componente conectado bipartito.${\displaystyle \mathbf {x} \neq \mathbf {0} }$

Laplaciano normalizado simétrico

El laplaciano (simétrico) normalizado se define como

${\displaystyle L^{\text{sym}}:=D^{-{\frac {1}{2}}}LD^{-{\frac {1}{2}}}=I-D^{-{\frac {1}{2}}}AD^{-{\frac {1}{2}}}}$

donde L es el Laplaciano (no normalizado), A es la matriz de adyacencia y D es la matriz de grados. Dado que la matriz grado D es diagonal y positiva, su raíz cuadrada recíproca es la matriz diagonal cuyos elementos diagonales son los recíprocos de las raíces cuadradas positivas de los elementos de la diagonal de D . El laplaciano simétrico normalizado es una matriz simétrica.${\textstyle D^{-{\frac {1}{2}}}}$

Uno tiene:, donde S es la matriz cuyas filas están indexadas por los vértices y cuyas columnas están indexadas por los bordes de G, de modo que cada columna correspondiente a un borde e = {u, v} tiene una entrada en la fila correspondiente a u , una entrada en la fila correspondiente av, y tiene 0 entradas en otros lugares. ( denota la transposición de S).${\textstyle L^{\text{sym}}=SS^{*}}$${\textstyle {\frac {1}{\sqrt {d_{u}}}}}$${\textstyle -{\frac {1}{\sqrt {d_{v}}}}}$${\textstyle S^{*}}$

Todos los valores propios del Laplaciano normalizado son reales y no negativos. Podemos ver esto de la siguiente manera. Dado que es simétrico, sus valores propios son reales. También son no negativos: considere un autovector de con autovalor λ y suponga . (Podemos considerar g y f como funciones reales en los vértices v.) Entonces:${\textstyle L^{\text{sym}}}$${\textstyle g}$${\textstyle L^{\text{sym}}}$${\textstyle g=D^{\frac {1}{2}}f}$

${\displaystyle \lambda \ =\ {\frac {\langle g,L^{\text{sym}}g\rangle }{\langle g,g\rangle }}\ =\ {\frac {\left\langle g,D^{-{\frac {1}{2}}}LD^{-{\frac {1}{2}}}g\right\rangle }{\langle g,g\rangle }}\ =\ {\frac {\langle f,Lf\rangle }{\left\langle D^{\frac {1}{2}}f,D^{\frac {1}{2}}f\right\rangle }}\ =\ {\frac {\sum _{u\sim v}(f(u)-f(v))^{2}}{\sum _{v}f(v)^{2}d_{v}}}\ \geq \ 0,}$

donde usamos el producto interno , una suma de todos los vértices v, y denota la suma de todos los pares desordenados de vértices adyacentes {u, v}. La cantidad se llama suma de Dirichlet de f, mientras que la expresión se llama cociente de Rayleigh de g.${\textstyle \langle f,g\rangle =\sum _{v}f(v)g(v)}$${\textstyle \sum _{u\sim v}}$${\textstyle \sum _{u,v}(f(u)-f(v))^{2}}$${\textstyle {\frac {\left\langle g,L^{\text{sym}}g\right\rangle }{\langle g,g\rangle }}}$

Sea 1 la función que asume el valor 1 en cada vértice. Entonces es una función propia de con valor propio 0. ^[5]${\textstyle D^{\frac {1}{2}}1}$${\textstyle L^{\text{sym}}}$

De hecho, 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 otras invariantes gráficas para gráficas generales. ^[6]

Caminata aleatoria normalizada laplaciana

El Laplaciano normalizado de caminata aleatoria se define como

${\displaystyle L^{\text{rw}}:=D^{-1}L}$

donde D es la matriz de grados. Dado que la matriz grado D es diagonal, su inversa se define simplemente como una matriz diagonal, que tiene entradas diagonales que son los recíprocos de las correspondientes entradas diagonales positivos de D .${\textstyle D^{-1}}$

Para los vértices aislados (aquellos con grado 0), una opción común es establecer el elemento correspondiente en 0.${\textstyle L_{i,i}^{\text{rw}}}$

Esta convención da como resultado una buena propiedad de que la multiplicidad del valor propio 0 es igual al número de componentes conectados en el gráfico.

Los elementos de la matriz de están dados por${\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 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. Por ejemplo, denotemos el i-ésimo vector base estándar . Entonces es un vector de probabilidad que representa la distribución de las ubicaciones de un caminante al azar 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^{-1}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}$

Uno 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, aunque en general no sea hermitaño, tiene valores propios reales. De hecho, sus valores propios concuerdan con los de (que es hermitiano). ${\textstyle L^{\text{rw}}}$${\textstyle L^{\text{sym}}}$${\textstyle L^{\text{rw}}}$${\textstyle L^{\text{sym}}}$

Gráficos

Como comentario adicional sobre los paseos aleatorios en los gráficos , considere un gráfico simple no dirigido . Considere la probabilidad de que el caminante esté en el vértice i en el momento t , dada la distribución de probabilidad de que estuvo en el vértice j en el momento t - 1 (asumiendo una probabilidad uniforme de dar un paso a lo largo de cualquiera de los bordes unidos a un vértice dado) :

${\displaystyle p_{i}(t)=\sum _{j}{\frac {A_{ij}}{\deg \left(v_{j}\right)}}p_{j}(t-1),}$

o en notación matricial-vectorial:

${\displaystyle p(t)=AD^{-1}p(t-1).}$

(El equilibrio, que se establece como , se define por .)${\textstyle t\rightarrow \infty }$${\textstyle p=AD^{-1}p}$

Podemos reescribir esta relación como

${\displaystyle D^{-{\frac {1}{2}}}p(t)=\left[D^{-{\frac {1}{2}}}AD^{-{\frac {1}{2}}}\right]D^{-{\frac {1}{2}}}p(t-1).}$

${\textstyle A_{\text{reduced}}\equiv D^{-{\frac {1}{2}}}AD^{-{\frac {1}{2}}}}$es una matriz simétrica llamada matriz de adyacencia reducida . Entonces, dar pasos en esta caminata aleatoria requiere tomar poderes de , que es una operación simple porque es simétrica.${\textstyle A_{\text{reduced}}}$${\textstyle A_{\text{reduced}}}$

Interpretación como el operador discreto de Laplace

La matriz laplaciana se puede interpretar como una representación matricial de un caso particular del operador discreto de Laplace . Tal interpretación permite, por ejemplo, generalizar la matriz laplaciana al caso de gráficos con un número infinito de vértices y aristas, lo que conduce a una matriz laplaciana de tamaño infinito.

Suponga que describe una distribución de calor a través de un gráfico , donde está el calor en el vértice . De acuerdo con la ley de enfriamiento de Newton , el calor transferido de un nodo a otro es proporcional a si los nodos y están conectados (si no están conectados, no se transfiere calor). Luego, para la capacidad calorífica ,${\textstyle \phi }$${\textstyle \phi _{i}}$${\textstyle i}$${\textstyle i}$${\textstyle j}$${\textstyle \phi _{i}-\phi _{j}}$${\textstyle i}$${\textstyle j}$${\textstyle k}$

${\displaystyle {\begin{aligned}{\frac {d\phi _{i}}{dt}}&=-k\sum _{j}A_{ij}\left(\phi _{i}-\phi _{j}\right)\\&=-k\left(\phi _{i}\sum _{j}A_{ij}-\sum _{j}A_{ij}\phi _{j}\right)\\&=-k\left(\phi _{i}\ \deg(v_{i})-\sum _{j}A_{ij}\phi _{j}\right)\\&=-k\sum _{j}\left(\delta _{ij}\ \deg(v_{i})-A_{ij}\right)\phi _{j}\\&=-k\sum _{j}\left(\ell _{ij}\right)\phi _{j}.\end{aligned}}}$

En notación matricial-vectorial,

${\displaystyle {\begin{aligned}{\frac {d\phi }{dt}}&=-k(D-A)\phi \\&=-kL\phi ,\end{aligned}}}$

lo que da

${\displaystyle {\frac {d\phi }{dt}}+kL\phi =0.}$

Observe que esta ecuación toma la misma forma que la ecuación de calor , donde la matriz - L reemplaza al operador laplaciano ; de ahí el "grafo laplaciano".${\textstyle \nabla ^{2}}$

Para encontrar una solución a esta ecuación diferencial, aplique técnicas estándar para resolver una ecuación diferencial matricial de primer orden . Es decir, escriba como una combinación lineal de vectores propios de L (de modo que ) con coeficientes dependientes del tiempo,${\textstyle \phi }$${\textstyle \mathbf {v} _{i}}$${\textstyle L\mathbf {v} _{i}=\lambda _{i}\mathbf {v} _{i}}$${\textstyle \phi (t)=\sum _{i}c_{i}(t)\mathbf {v} _{i}.}$

Reemplazando la expresión original (debido a que L es una matriz simétrica, sus vectores propios de norma unitaria son ortogonales):${\textstyle \mathbf {v} _{i}}$

${\displaystyle {\begin{aligned}0={}&{\frac {d\left(\sum _{i}c_{i}(t)\mathbf {v} _{i}\right)}{dt}}+kL\left(\sum _{i}c_{i}(t)\mathbf {v} _{i}\right)\\{}={}&\sum _{i}\left[{\frac {dc_{i}(t)}{dt}}\mathbf {v} _{i}+kc_{i}(t)L\mathbf {v} _{i}\right]\\{}={}&\sum _{i}\left[{\frac {dc_{i}(t)}{dt}}\mathbf {v} _{i}+kc_{i}(t)\lambda _{i}\mathbf {v} _{i}\right]\\\Rightarrow 0={}&{\frac {dc_{i}(t)}{dt}}+k\lambda _{i}c_{i}(t),\\\end{aligned}}}$

cuya solución es

${\displaystyle c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}.}$

Como se mostró antes, los valores propios de L no son negativos, lo que muestra que la solución de la ecuación de difusión se acerca a un equilibrio, porque solo decae exponencialmente o permanece constante. Esto también muestra que dada y la condición inicial , se puede encontrar la solución en cualquier momento t . ^[7]${\textstyle \lambda _{i}}$${\textstyle \lambda _{i}}$${\textstyle c_{i}(0)}$

Para encontrar cada uno en términos de la condición inicial general , simplemente proyecte sobre los vectores propios de norma unitaria ;${\textstyle c_{i}(0)}$${\textstyle i}$${\textstyle \phi (0)}$${\textstyle \phi (0)}$${\textstyle \mathbf {v} _{i}}$

${\displaystyle c_{i}(0)=\left\langle \phi (0),\mathbf {v} _{i}\right\rangle }$.

Este enfoque se ha aplicado al modelado cuantitativo de transferencia de calor en redes no estructuradas. ^[8]

En el caso de gráficos no dirigidos, esto funciona porque es simétrico y, según el teorema espectral , sus vectores propios son todos ortogonales. Entonces, la proyección sobre los vectores propios de es simplemente una transformación de coordenadas ortogonales de la condición inicial en un conjunto de coordenadas que decaen exponencial e independientemente entre sí.${\textstyle L}$${\textstyle L}$

Comportamiento de equilibrio

Para entender , los únicos términos que quedan son aquellos en los que , dado que${\textstyle \lim _{t\to \infty }\phi (t)}$${\textstyle c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}}$${\textstyle \lambda _{i}=0}$

${\displaystyle \lim _{t\to \infty }e^{-k\lambda _{i}t}={\begin{cases}0,&{\text{if}}&\lambda _{i}>0\\1,&{\text{if}}&\lambda _{i}=0\end{cases}}}$

En otras palabras, el estado de equilibrio del sistema está determinado completamente por el núcleo de . ${\textstyle L}$

Dado que, por definición, el vector de todos unos está en el núcleo. Si hay componentes conectados disjuntos en el gráfico, entonces este vector de todos se puede dividir en la suma de vectores propios independientes de unos y ceros, donde cada componente conectado corresponde a un vector propio con unos en los elementos del componente conectado y ceros en cualquier otro lugar. .${\textstyle \sum _{j}L_{ij}=0}$${\textstyle \mathbf {v} ^{1}}$${\textstyle k}$${\textstyle k}$${\textstyle \lambda =0}$

La consecuencia de esto es que para una condición inicial dada para un gráfico con vértices${\textstyle c(0)}$${\textstyle N}$

${\displaystyle \lim _{t\to \infty }\phi (t)=\left\langle c(0),\mathbf {v^{1}} \right\rangle \mathbf {v^{1}} }$

dónde

${\displaystyle \mathbf {v^{1}} ={\frac {1}{\sqrt {N}}}[1,1,\ldots ,1]}$

Para cada elemento de , es decir, para cada vértice del gráfico, se puede reescribir como${\textstyle \phi _{j}}$${\textstyle \phi }$${\textstyle j}$

${\displaystyle \lim _{t\to \infty }\phi _{j}(t)={\frac {1}{N}}\sum _{i=1}^{N}c_{i}(0)}$.

En otras palabras, en estado estable, el valor de converge al mismo valor en cada uno de los vértices del gráfico, que es el promedio de los valores iniciales en todos los vértices. Dado que esta es la solución a la ecuación de difusión de calor, tiene perfecto sentido intuitivamente. Esperamos que los elementos vecinos en el gráfico intercambien energía hasta que esa energía se distribuya uniformemente por todos los elementos que están conectados entre sí.${\textstyle \phi }$

Ejemplo del operador en una cuadrícula

Este GIF muestra la progresión de la difusión, según lo resuelto por la técnica gráfica laplaciana. Un gráfico se construye sobre una cuadrícula, donde cada píxel del gráfico está conectado a sus 8 píxeles limítrofes. Los valores en la imagen luego se difunden suavemente a sus vecinos a lo largo del tiempo a través de estas conexiones. Esta imagen en particular comienza con tres valores de puntos fuertes que se extienden lentamente a sus vecinos. Todo el sistema finalmente se establece en el mismo valor en equilibrio.

Esta sección muestra un ejemplo de una función que se difunde en el tiempo a través de un gráfico. El gráfico de este ejemplo se construye en una cuadrícula discreta 2D, con puntos en la cuadrícula conectados a sus ocho vecinos. Se especifican tres puntos iniciales para tener un valor positivo, mientras que el resto de los valores de la cuadrícula son cero. Con el tiempo, la disminución exponencial actúa para distribuir los valores en estos puntos de manera uniforme en toda la cuadrícula.${\textstyle \phi }$

El código fuente completo de Matlab que se utilizó para generar esta animación se proporciona a continuación. Muestra el proceso de especificar las condiciones iniciales, proyectando estas condiciones iniciales en los valores propios de la Matriz Laplaciana y simulando el decaimiento exponencial de estas condiciones iniciales proyectadas.

N = 20 ; % El número de píxeles a lo largo de una dimensión de la imagen.   A = ceros ( N , N ); % La imagen    Adj = ceros ( N * N , N * N ); % La matriz de adyacencia        % Use 8 vecinos y complete la matriz de adyacenciadx = [ - 1 , 0 , 1 , - 1 , 1 , - 1 , 0 , 1 ];            dy = [ - 1 , - 1 , - 1 , 0 , 0 , 1 , 1 , 1 ];            para x = 1 : N    para y = 1 : N    índice = ( x - 1 ) * N + y ;         para ne = 1 : longitud ( dx )    nuevox = x + dx ( ne );     newy = y + dy ( ne );     si nuevox > 0 && nuevox <= N && nuevo > 0 && nuevo <= N                índice2 = ( nuevox - 1 ) * N + nuevo ;         Adj ( índice , índice2 ) = 1 ;    final final finalfinal% ABAJO ES EL CÓDIGO CLAVE QUE COMPUTA LA SOLUCIÓN A LA ECUACIÓN DIFERENCIALDeg = diag ( suma ( Adj , 2 )); % Calcular la matriz de grados    L = Deg - Adj ; % Calcular la matriz laplaciana en términos de matrices de grado y adyacencia     [ V , D ] = eig ( L ); % Calcular los autovalores / vectores de la matriz laplaciana    D = diag ( D );  % Condición inicial (coloque algunos valores positivos grandes alrededor y% hacer que todo lo demás sea cero)C0 = ceros ( N , N );   C0 ( 2 : 5 , 2 : 5 ) = 5 ;   C0 ( 10 : 15 , 10 : 15 ) = 10 ;   C0 ( 2 : 5 , 8 : 13 ) = 7 ;   C0 = C0 (:);  C0V = V '* C0 ; % Transforma la condición inicial en el sistema de coordenadas   % de los autovectorespara t = 0 : 0.05 : 5    % Tiempos de bucle y decadencia de cada componente inicial Phi = C0V *. Exp ( - D * t ); % Decaimiento exponencial para cada componente         Phi = V * Phi ; % Transformación del sistema de coordenadas de vector propio al sistema de coordenadas original      Phi = remodelar ( Phi , N , N );     % Muestra los resultados y escribe en un archivo GIF imagesc ( Phi ); caxis ([ 0 , 10 ]);  title ( sprintf ( 'Difusión t =% 3f' , t ));  marco = obtener marco ( 1 );   im = frame2im ( marco );   [ imind , cm ] = rgb2ind ( im , 256 );     si t == 0    imwrite ( imind , cm , 'out.gif' , 'gif' , 'Loopcount' , inf , 'DelayTime' , 0.1 );        demás imwrite ( imind , cm , 'out.gif' , 'gif' , 'WriteMode' , 'agregar' , 'DelayTime' , 0.1 );        finalfinal

Aproximación al laplaciano continuo negativo

La gráfica matriz laplaciana puede verse además como una forma matricial de una aproximación al operador laplaciano (semidefinido positivo) obtenido por el método de diferencias finitas . (Consulte la ecuación de Poisson discreta ) ^[9] En esta interpretación, cada vértice del gráfico se trata como un punto de la cuadrícula; la conectividad local del vértice determina la plantilla de aproximación en diferencias finitas en este punto de la cuadrícula, el tamaño de la cuadrícula es siempre uno para cada borde y no hay restricciones en ningún punto de la cuadrícula, lo que corresponde al caso de la condición de límite de Neumann homogénea , es decir , límite libre.

Multigrafos dirigidos

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

${\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).

Ver también

• Matriz de rigidez
• Distancia de resistencia
• Matriz de tasas de transición
• Cálculo en gráficos ponderados finitos
• Transformada de Fourier del gráfico

Referencias

1. Weisstein, Eric W. "Matriz laplaciana" . MathWorld .
2. Godsil, C .; Royle, G. (2001). Teoría de Grafos Algebraicos, Textos de Posgrado en Matemáticas . Springer-Verlag.
3. Morbidi, F. (2013). "El Protocolo de Consenso Deformado" (PDF) . Automatica . 49 (10): 3049-3055. doi : 10.1016 / j.automatica.2013.07.006 .
4. Cvetković, Dragoš; Simić, Slobodan K. (2010). "Hacia una teoría espectral de gráficos basada en el laplaciano sin signo, III". Análisis aplicable y matemáticas discretas . 4 (1): 156–166. doi : 10.2298 / AADM1000001C . ISSN 1452-8630 . JSTOR 43671298 .  
5. Chung, Fan RK (1997). Teoría de grafos espectrales (Repr. Con corr., 2. [pr.] Ed.). Providence, RI: American Math. Soc. ISBN 978-0-8218-0315-8.
6. Chung, Fan (1997) [1992]. Teoría del gráfico espectral . Sociedad Matemática Estadounidense. ISBN 978-0821803158.
7. Newman, Mark (2010). Redes: una introducción . Prensa de la Universidad de Oxford. ISBN 978-0199206650.
8. Yavari, R .; Cole, KD; Rao, PK (2020). "Transferencia de calor computacional con teoría de gráfico espectral: verificación cuantitativa" . J. Internacional de Ciencias Térmicas . 153 : 106383. doi : 10.1016 / j.ijthermalsci.2020.106383 .
9. Smola, Alexander J .; Kondor, Risi (2003), "Kernels and regularization on graphs", Learning Theory and Kernel Machines: 16a Conferencia Anual sobre Teoría del Aprendizaje y Séptimo Taller de Kernel, COLT / Kernel 2003, Washington, DC, EE. UU., 24 al 27 de agosto de 2003, Actas , Lecture Notes in Computer Science, 2777 , Springer, págs. 144-158, CiteSeerX 10.1.1.3.7020 , doi : 10.1007 / 978-3-540-45167-9_12 , ISBN  978-3-540-40720-1.
10. 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 . 

• T. Sunada, "Análisis geométrico discreto", Actas de simposios en matemáticas puras, (ed. Por P. Exner, JP Keating, P. Kuchment, T. Sunada, A. Teplyaev), 77 (2008), 51–86.
• B. Bollobás , Modern Graph Theory , Springer-Verlag (1998, edición corregida 2013), ISBN 0-387-98488-7 , Capítulos II.3 (Espacios vectoriales y matrices asociadas con gráficos), VIII.2 (La matriz de adyacencia y el Laplaciano), IX.2 (Redes eléctricas y paseos al azar).