Matriz laplaciana

En teoría de grafos la matriz laplaciana — también denominada matriz de admitancia o matriz de Kirchhoff — es una representación matricial de un grafo. Otro tipo de representación matricial la proporciona la matriz de adyacencia, pero la matriz laplaciana es ideal para realizar la teoría espectral de grafos.

Definición

Dado un grafo G con n nodos, la matriz laplaciana $L:=(\ell _{i,j})_{n\times n}$ se define como:​

$\ell _{i,j}:={\begin{cases}\kappa _{i}&{\mbox{si}}\ i=j\\-1&{\mbox{si}}\ i\neq j\ {\mbox{y}}\ n_{i}{\mbox{ es adyacente a }}n_{j}\\0&{\mbox{otro caso}}.\end{cases}}$

siendo $\kappa _{i}$ el grado del nodo i-ésimo $n_{i}$. La matriz laplaciana normalizada ${\mathcal {L}}:=({\hat {\ell }}_{i,j})_{n\times n}$ se define como:​

${\hat {\ell }}_{i,j}:={\begin{cases}1&{\mbox{si}}\ i=j\ {\mbox{y}}\ \kappa _{i}\neq 0\\-{\frac {1}{\sqrt {\kappa _{i}\kappa _{j}}}}&{\mbox{si}}\ i\neq j\ {\mbox{y}}\ n_{i}{\mbox{ es adyacente a }}n_{j}\\0&{\mbox{otro caso}}.\end{cases}}$

Tomando ${\hat {T}}$ como la matriz diagonal de elementos $(i,i)$ de entrada $\kappa _{i}$, se tiene que:

${\hat {\mathcal {L}}}={\hat {T}}^{-1/2}{\hat {L}}{\hat {T}}^{-1/2}$

con la convención $({\hat {T}}^{-1})_{v,v}=0$ para $\kappa _{v}=0$.

Propiedades

Relación con la matriz de adyacencias

Cuando el grafo $\Gamma$ es k-regular se puede observar que:

${\hat {\mathcal {L}}}={\hat {\mathbb {I} }}-{\frac {1}{k}}{\hat {A}}$

donde $A$ es la matriz de adyacencias y ${\hat {\mathbb {I} }}$ es la identidad. Para un grafo sin vértices aislados, tenemos entonces que:

${\hat {\mathcal {L}}}={\hat {T}}^{-1/2}{\hat {L}}{\hat {T}}^{-1/2}={\hat {\mathbb {I} }}-{\hat {T}}^{-1/2}{\hat {A}}{\hat {T}}^{-1/2}$.

Ejemplo

Ejemplo de la representación en forma de grafo de una red y su representación matricial laplaciana:

grafo	matriz laplaciana
	$\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)$

Espectro de ${\hat {\mathcal {L}}}$

Para un grafo $\Gamma$ y matriz laplaciana $L(\Gamma )$, con los autovalores ordenados (el espectro de $L$) $\lambda _{0}\leqslant \lambda _{1}\leqslant \dotsc \leqslant \lambda _{n-1}$:

1. La matriz laplaciana es siempre definida positiva.
2. El primer autovalor $\lambda _{0}=0$ es siempre nulo; existe un autovector que es siempre $[1,1,\dots ,1]$. La multiplicidad de $\lambda _{0}$ indica el número de subgrafos inconexos que hay.
3. El segundo autovalor no nulo $\lambda _{2}$ se denomina conectividad algebraica.​ Es una medida de la conectividad del grafo. A medida que $\lambda _{2}$ se hace más pequeño el grafo adquiere una estructura más modular. A través de la percolación a través de un grafo, la sincronización máxima se da para el valor más alto posible de $\lambda _{2}$. También se denomina salto espectral, gap o parámetro de Fiedler.​

Véase también

• Modelo en grafo
• Algoritmo de Floyd
• Relación social
• Iconografía de las correlaciones

Referencias

• Datos: Q772067