Matriz Laplaciana

No campo matemático da teoria dos grafos, a matriz laplaciana, às vezes chamada matriz de admitância, matriz Kirchhoff ou laplaciano discreto, é uma representação matricial de um grafo . A matriz laplaciana pode ser usada para encontrar muitas propriedades úteis de um grafo. Juntamente com o teorema de Kirchhoff, ela pode ser usada para calcular o número de árvores de abrangência para um determinado grafo. O corte mais esparso de um grafo pode ser aproximado através do segundo menor autovalor de seu Laplaciano pela desigualdade de Cheeger . Também pode ser utilizada para construir incorporações de baixa dimensão, o que pode ser útil para uma variedade de aplicativos de aprendizado de máquina .

Definição

Matriz Laplaciana para grafos simples

Dado um grafo simples $G$ com $n$ vértices, sua matriz laplaciana ${\textstyle L_{n\times n}}$ é definida como:

$L=D-A,$

onde D é a matriz de graus e A é a matriz de adjacência do grafo. Uma vez que ${\textstyle G}$ é um grafo simples, ${\textstyle A}$ contém apenas 1s ou 0s e os seus elementos diagonais são todos 0s.

No caso de grafos direcionados, pode-se utilizar os graus de entrada ou os graus de saída, dependendo da aplicação.

Os elementos de ${\textstyle L}$ são dados por

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

Onde $\operatorname {deg} (v_{i})$ é o grau do vértice $i$ .

Laplaciano simétrico normalizado

A matriz laplaciana simétrica normalizada é definida como:

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

Os elementos de ${\textstyle L^{\text{sym}}}$ são 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}}$

Laplaciano normalizado de passeio aleatório

A matriz Laplaciana normalizada de percurso aleatório é definida como:

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

Os elementos de ${\textstyle L^{\text{rw}}}$ são 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}}$

Laplaciano generalizado

O Laplaciano generalizado $Q$ é definido como  :

${\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 o Laplaciano comum é um Laplaciano generalizado.

Exemplo

Aqui está um exemplo simples de um grafo rotulado, não direcionado e sua matriz laplaciana.

Grafo rotulado	Matriz de grau	Matriz de adjacência	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)}$

Propriedades

Para um grafo (não direcionado) G e sua matriz Laplaciana L com autovalores ${\textstyle \lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{n-1}}$ :

• L é simétrico.
• L é semidefinido positivo (ou seja, ${\textstyle \lambda _{i}\geq 0}$ para todos ${\textstyle i}$ ) Isso é verificado na seção da matriz de incidência (abaixo). Isso também pode ser visto pelo fato de o laplaciano ser simétrico e diagonalmente dominante .
• L é uma matriz M (suas entradas fora da diagonal não são positivas, mas as partes reais de seus autovalores são não-negativas).
• Cada soma de linha e de coluna de L é zero. De fato, na soma, o grau do vértice é somado com um "-1" para cada vizinho.
• Em consequência, ${\textstyle \lambda _{0}=0}$, pois o vetor ${\textstyle \mathbf {v} _{0}=(1,1,\dots ,1)}$ satisfaz ${\textstyle L\mathbf {v} _{0}=\mathbf {0} .}$ Isso também implica que a matriz laplaciana é singular.
• O número de componentes conectados no grafo é a dimensão do espaço nulo do Laplaciano e a multiplicidade algébrica do autovalor 0.
• O menor autovalor não-nulo de L é chamado de gap espectral .
• O segundo menor autovalor de L (poderia ser zero) é a conectividade algébrica (ou valor de Fiedler ) de G e aproxima o corte mais esparso de um grafo.
• O Laplaciano é um operador no espaço vetorial n-dimensional de funções ${\textstyle f:V\to \mathbb {R} }$, Onde ${\textstyle V}$ é o conjunto de vértices de G e ${\textstyle n=|V|}$ .
• Quando G é um grafo regular de grau K, ou K-regular, o Laplaciano normalizado é: ${\textstyle {\mathcal {L}}={\tfrac {1}{k}}L=I-{\tfrac {1}{k}}A}$, onde A é a matriz de adjacência e I é uma matriz de identidade.
• Para um grafo com múltiplos componentes conectados, L é uma matriz diagonal de bloco, em que cada bloco é a respectiva matriz laplaciana de cada componente, possivelmente após reordenar os vértices (ou seja, L é semelhante à permutação de uma matriz diagonal de bloco).
• O traço da matriz laplaciana L é igual a ${\textstyle 2m}$ onde ${\textstyle m}$ é o número de arestas do grafo considerado.

Matriz de incidência

Defina uma matriz de incidência M orientada ${\textstyle |e|\times |v|}$ com elemento M_ev de aresta e (vértices de ligação i e j, com i   >   j ) e vértice v dado por

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

Então a matriz laplaciana L satisfaz

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

Onde ${\textstyle M^{\textsf {T}}}$ é a matriz transposta de M.

Agora considere uma autocomposição de ${\textstyle L}$, com autovetores de norma unitária ${\textstyle \mathbf {v} _{i}}$ e autovalores correspondentes ${\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}}$

${\textstyle \lambda _{i}}$ pode ser escrito como o produto interno do vetor ${\textstyle M\mathbf {v} _{i}}$ com ele próprio, isso mostra que ${\textstyle \lambda _{i}\geq 0}$ e, portanto, os autovalores de ${\textstyle L}$ são todos não negativos.

Laplaciano Deformado

O Laplaciano deformado é comumente definido como

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

onde I é a matriz unitária, A é a matriz de adjacência, D é a matriz de graus e s é um número (de valor complexo). O Laplaciano padrão é apenas ${\textstyle \Delta (1)}$ .

Laplaciano sem sinal

O Laplaciano sem sinal é definido como

$$Q=D+A$$

Onde $D$ é a matriz de graus e $A$ é a matriz de adjacência. Como o Laplaciano assinado $L$, o Laplaciano sem sinal $Q$ também é semi-definido positivo, pois pode ser considerado

$$Q=RR^{T}$$

onde ${\textstyle R}$ é a matriz de incidência. $Q$ tem um autovetor 0 se e somente se tiver um componente conectado bipartido que não seja vértices isolados. Isso pode ser mostrado como

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

Isso tem uma solução onde $\mathbf {x} \neq \mathbf {0}$ se e somente se o grafo tiver um componente conectado bipartido.

Laplaciano normalizado simétrico

O Laplaciano normalizado (simétrico) é definido como

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

onde L é o Laplaciano (não normalizado), A é a matriz de adjacência e D é a matriz de graus. Como a matriz de graus D é diagonal e positiva, sua raiz quadrada recíproca ${\textstyle D^{-{\frac {1}{2}}}}$ é apenas a matriz diagonal cujas entradas diagonais são as recíprocas das raízes quadradas positivas das entradas diagonais de D. O Laplaciano normalizado simétrico é uma matriz simétrica.

Um deles tem: ${\textstyle L^{\text{sym}}=SS^{*}}$, em que S é a matriz cujas linhas são indexadas pelos vértices e cujas colunas são indexadas pelas arestas de G, de modo que cada coluna correspondente a uma aresta e = {u, v} tenha uma entrada ${\textstyle {\frac {1}{\sqrt {d_{u}}}}}$ na linha correspondente a u, uma entrada ${\textstyle -{\frac {1}{\sqrt {d_{v}}}}}$ na linha correspondente a v e tenha 0 entradas em outro lugar. ( ${\textstyle S^{*}}$ denota a transposição de S).

Todos os autovalores do Laplaciano normalizado são reais e não negativos. Podemos ver isso da seguinte maneira. Como ${\textstyle L^{\text{sym}}}$ é simétrico, seus autovalores são reais. Eles são também não negativos: considere um autovetor ${\textstyle g}$ de ${\textstyle L^{\text{sym}}}$ com autovalor λ e suponha ${\textstyle g=D^{\frac {1}{2}}f}$ . (Podemos considerar g e f como funções reais nos vértices v. ) Então:

$\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,$

onde usamos o produto interno ${\textstyle \langle f,g\rangle =\sum _{v}f(v)g(v)}$, uma soma sobre todos os vértices v, e ${\textstyle \sum _{u\sim v}}$ denota a soma de todos os pares não ordenados de vértices adjacentes {u, v}. A quantidade ${\textstyle \sum _{u,v}(f(u)-f(v))^{2}}$ é chamada de soma de Dirichlet de f, enquanto a expressão ${\textstyle {\frac {\left\langle g,L^{\text{sym}}g\right\rangle }{\langle g,g\rangle }}}$ é chamada quociente de Rayleigh de g.

Seja 1 a função que assume o valor 1 em cada vértice. Então ${\textstyle D^{\frac {1}{2}}1}$ é uma autofunção de ${\textstyle L^{\text{sym}}}$ com autovalor 0.

De fato, os autovalores do Laplaciano simétrico normalizado satisfazem 0 = μ ₀ ≤… ≤ μ _{n − 1} ≤ 2. Esses autovalores (conhecidos como o espectro do Laplaciano normalizado) se relacionam bem com outros invariantes de grafos para grafos gerais.

Laplaciano normalizado de passeio aleatório

O Laplaciano normalizado de passeio aleatório é definido como

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

onde D é a matriz de graus. Como a matriz de graus D é diagonal, sua inversa ${\textstyle D^{-1}}$ é simplesmente definida como uma matriz diagonal, com entradas diagonais que são as recíprocas das entradas diagonais positivas correspondentes de D.

Para os vértices isolados (aqueles com grau 0), uma escolha comum é definir o elemento correspondente ${\textstyle L_{i,i}^{\text{rw}}}$ para 0.

Esta convenção resulta em uma propriedade boa de que a multiplicidade do autovalor 0 é igual ao número de componentes conectados no grafo.

Os elementos matriciais de ${\textstyle L^{\text{rw}}}$ são 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}}$

O nome do Laplaciano normalizado de passeio aleatório provém do fato de que essa matriz é ${\textstyle L^{\text{rw}}=I-P}$, onde ${\textstyle P=D^{-1}A}$ é simplesmente a matriz de transição de um passeio aleatório no grafo. Por exemplo, deixe ${\textstyle e_{i}}$ denotar o i-ésimo vetor da base canônica . Então ${\textstyle x=e_{i}P}$ é um vetor de probabilidade que representa a distribuição das localizações de um passeio aleatório após ter dado um único passo a partir do vértice ${\textstyle i}$ ; ou seja, ${\textstyle x_{j}=\mathbb {P} \left(v_{i}\to v_{j}\right)}$ . De maneira mais geral, se o vetor ${\textstyle x}$ é uma distribuição probabilística da localização de um passeio aleatório nos vértices do grafo, então ${\textstyle x'=xP^{t}}$ é a distribuição probabilística do andador após ${\textstyle t}$ passos.

Pode-se verificar que

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

ou seja, ${\textstyle L^{\text{rw}}}$ é semelhante ao Laplaciano normalizado ${\textstyle L^{\text{sym}}}$ . Por essa razão, mesmo que ${\textstyle L^{\text{rw}}}$ não é, em geral, hermitiana, ela possui autovalores reais. De fato, seus autovalores concordam com os de ${\textstyle L^{\text{sym}}}$ (que é hermitiana).

Grafos

Como um aparte sobre passeios aleatórios em grafos, considere um grafo simples e não direcionado . Considere a probabilidade de o andador estar no vértice i no tempo t, dada a distribuição de probabilidade de que ele estava no vértice j no tempo t-1 (assumindo uma chance uniforme de dar um passo ao longo de qualquer uma das arestas ligadas a um determinado vértice) :

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

ou em notação de vetor de matriz:

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

(O equilíbrio, que se estabelece em como ${\textstyle t\rightarrow \infty }$, é definido por ${\textstyle p=AD^{-1}p}$ . )

Podemos reescrever essa relação como

$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}}}}$ é uma matriz simétrica chamada matriz de adjacência reduzida . Portanto, dar passos nesse passeio aleatório requer poderes de ${\textstyle A_{\text{reduced}}}$, que é uma operação simples porque ${\textstyle A_{\text{reduced}}}$ é simétrica.

Interpretação com o operador de Laplace discreto

A matriz laplaciana pode ser interpretada como uma representação matricial de um caso particular do operador de Laplace discreto . Tal interpretação permite, por exemplo, generalizar a matriz laplaciana para o caso de grafos com um número infinito de vértices e arestas, levando a uma matriz laplaciana de dimensão infinita.

Suponha que ${\textstyle \phi }$ descreve uma distribuição de calor através de um grafo, onde ${\textstyle \phi _{i}}$ é o calor no vértice ${\textstyle i}$ . De acordo com a lei de resfriamento de Newton, o calor transferido entre os nós ${\textstyle i}$ e ${\textstyle j}$ é proporcional a ${\textstyle \phi _{i}-\phi _{j}}$ se os nós ${\textstyle i}$ e ${\textstyle j}$ estão conectados (se não estiverem conectados, nenhum calor será transferido). Então, para a capacidade calorífica ${\textstyle k}$ ,

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

Na notação de vetor de matriz,

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

que dá

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

Observe que essa equação assume a mesma forma que a equação do calor, onde a matriz - L está substituindo o operador Laplaciano ${\textstyle \nabla ^{2}}$ ; consequentemente, o "grafo Laplaciano".

Para encontrar uma solução para esta equação diferencial, aplique técnicas padrão para resolver uma equação diferencial matricial de primeira ordem. Ou seja, escreva ${\textstyle \phi }$ como uma combinação linear de autovetores ${\textstyle \mathbf {v} _{i}}$ de L (para que ${\textstyle L\mathbf {v} _{i}=\lambda _{i}\mathbf {v} _{i}}$ ), com ${\textstyle \phi =\sum _{i}c_{i}\mathbf {v} _{i}.}$ dependente do tempo.

Conectando-se à expressão original (porque L é uma matriz simétrica, seus autovetores de norma unitária ${\textstyle \mathbf {v} _{i}}$ ortogonais):

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

cuja solução é

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

Como mostrado anteriormente, os autovalores ${\textstyle \lambda _{i}}$ de L são não-negativos, mostrando que a solução para a equação de difusão aproxima-se de um equilíbrio, pois apenas decai exponencialmente ou permanece constante. Isso também mostra que, dado um ${\textstyle \lambda _{i}}$ e a condição inicial ${\textstyle c_{i}(0)}$, a solução em qualquer tempo t pode ser encontrada.

Para encontrar ${\textstyle c_{i}(0)}$ para cada ${\textstyle i}$ em termos da condição inicial geral ${\textstyle \phi (0)}$, basta projetar ${\textstyle \phi (0)}$ nos autovetores de norma unitária ${\textstyle \mathbf {v} _{i}}$ ;

No caso de grafos não direcionados, isso funciona porque ${\textstyle L}$ é simétrico e, pelo teorema espectral, seus autovetores são todos ortogonais. Portanto, a projeção sobre os autovetores de ${\textstyle L}$ é simplesmente uma transformação de coordenadas ortogonais da condição inicial em um conjunto de coordenadas que decaem exponencialmente e independentemente umas das outras.

Comportamento de equilíbrio

Para entender ${\textstyle \lim _{t\to \infty }\phi (t)}$, os únicos termos ${\textstyle c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}}$ que restam são aqueles onde ${\textstyle \lambda _{i}=0}$, uma vez que

$\lim _{t\to \infty }e^{-k\lambda _{i}t}=\left\{{\begin{array}{rlr}0&{\text{if}}&\lambda _{i}>0\\1&{\text{if}}&\lambda _{i}=0\end{array}}\right\}$

Em outras palavras, o estado de equilíbrio do sistema é determinado completamente pelo núcleo de ${\textstyle L}$ .

Uma vez que, por definição, ${\textstyle \sum _{j}L_{ij}=0}$, o vetor ${\textstyle \mathbf {v} ^{1}}$ de valores 1 está no núcleo. Se houver ${\textstyle k}$ componentes conexos disjuntos no grafo, então esse vetor de uns pode ser dividido na soma de ${\textstyle k}$ autovetores independente de ${\textstyle \lambda =0}$ de uns e zeros, em que cada componente conexa corresponde a um autovetor com valores 1 nos elementos do componente conexo e zeros nos outros locais.

A conseqüência disso é que, para uma determinada condição inicial ${\textstyle c(0)}$ para um grafo com ${\textstyle N}$ vértices

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

Onde

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

Para cada elemento ${\textstyle \phi _{j}}$ de ${\textstyle \phi }$, ou seja, para cada vértice ${\textstyle j}$ no grafo, ele pode ser reescrito como

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

Em outras palavras, no estado estacionário, o valor de ${\textstyle \phi }$ converge para o mesmo valor em cada um dos vértices do grafo, que é a média dos valores iniciais em todos os vértices. Como esta é a solução para a equação de difusão de calor, isso faz todo o sentido intuitivamente. Esperamos que os elementos vizinhos no grafo troquem energia até que essa energia seja distribuída uniformemente por todos os elementos que estão conectados entre si.

Exemplo do operador em uma grade

Este GIF mostra a progressão da difusão, conforme resolvido pela técnica laplaciana do grafo. Um grafo é construído sobre uma grade, onde cada pixel no grafo é conectado aos seus 8 pixels adjacentes. Os valores na imagem difundem-se então suavemente para os seus vizinhos ao longo do tempo através dessas conexões. Essa imagem em particular começa com três valores de pontos fortes que se espalham lentamente para os seus vizinhos. Todo o sistema acaba se estabelecendo com o mesmo valor em equilíbrio.

Esta seção apresenta um exemplo de uma função ${\textstyle \phi }$ difundindo-se ao longo do tempo através de um grafo. O grafo neste exemplo é construído em uma grade 2D discreta, com pontos na grade conectados aos seus oito vizinhos. Três pontos iniciais são especificados para ter um valor positivo, enquanto o restante dos valores na grade são zero. Com o tempo, o decaimento exponencial atua para distribuir os valores nesses pontos uniformemente por toda a grade.

O código fonte completo do Matlab utilizado para gerar esta animação é fornecido abaixo. Ele mostra o processo de especificação das condições iniciais, projetando essas condições iniciais nos autovalores da Matriz Laplaciana e simulando o decaimento exponencial dessas condições iniciais previstas.

N = 20;%The number of pixels along a dimension of the image
A = zeros(N, N);%The image
Adj = zeros(N*N, N*N);%The adjacency matrix

%Use 8 neighbors, and fill in the adjacency matrix
dx = [-1, 0, 1, -1, 1, -1, 0, 1];
dy = [-1, -1, -1, 0, 0, 1, 1, 1];
for x = 1:N
  for y = 1:N
    index = (x-1)*N + y;
    for ne = 1:length(dx)
      newx = x + dx(ne);
      newy = y + dy(ne);
      if newx > 0 && newx <= N && newy > 0 && newy <= N
        index2 = (newx-1)*N + newy;
        Adj(index, index2) = 1;
      end
    end
  end
end

%%%BELOW IS THE KEY CODE THAT COMPUTES THE SOLUTION TO THE DIFFERENTIAL
%%%EQUATION
Deg = diag(sum(Adj, 2));%Compute the degree matrix
L = Deg - Adj;%Compute the laplacian matrix in terms of the degree and adjacency matrices
[V, D] = eig(L);%Compute the eigenvalues/vectors of the laplacian matrix
D = diag(D);

%Initial condition (place a few large positive values around and
%make everything else zero)
C0 = zeros(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;%Transform the initial condition into the coordinate system 
%of the eigenvectors
for t = 0:0.05:5
  %Loop through times and decay each initial component
  Phi = C0V.*exp(-D*t);%Exponential decay for each component
  Phi = V*Phi;%Transform from eigenvector coordinate system to original coordinate system
  Phi = reshape(Phi, N, N);
  %Display the results and write to GIF file
  imagesc(Phi);
  caxis([0, 10]);
  title(sprintf('Diffusion t = %3f', t));
  frame = getframe(1);
  im = frame2im(frame);
  [imind, cm] = rgb2ind(im, 256);
  if t == 0
   imwrite(imind, cm, 'out.gif', 'gif', 'Loopcount', inf, 'DelayTime', 0.1); 
  else
   imwrite(imind, cm, 'out.gif', 'gif', 'WriteMode', 'append', 'DelayTime', 0.1);
  end
end

Aproximação ao Laplaciano contínuo negativo

A Matriz Laplaciana do grafo pode ainda ser vista como uma forma matricial de uma aproximação ao operador Laplaciano ( semidefinido positivo) obtido pelo método das diferenças finitas . (Veja equação discreta de Poisson) Nesta interpretação, todo vértice do grafo é tratado como um ponto de grade; a conectividade local do vértice determina o estêncil da aproximação por diferença finita nesse ponto da grade, o tamanho da grade é sempre um para cada aresta e não há restrições em nenhum ponto da grade, o que corresponde ao caso da condição de fronteira de Neumann homogênea, ou seja, fronteira livre.

Multigrafos orientados

Um análogo da matriz laplaciana pode ser definido para multigrafos orientados. Nesse caso, a matriz laplaciana L é definida como

$L=D-A$

onde D é uma matriz diagonal com D _{i, i} igual ao grau de saída do vértice i e A é uma matriz com A _{i, j} igual ao número de arestas de i a j (incluindo laços).

Veja também

• Matriz de rigidez
• Distância de resistência
• Matriz de taxa de transição
• Cálculo em grafos ponderados finitos

Referências

• T. Sunada, "Análise geométrica discreta", Proceedings of Symposia in Pure Mathematics, (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, corrigido ed. 2013), ISBN 0-387-98488-7 , capítulos II.3 (Espaços vetoriais e matrizes associadas a gráficos), VIII.2 (Matriz de adjacência e o Laplaciano), IX.2 (Redes elétricas e passeios aleatórios).

[[Categoria:Matrizes]] [[Categoria:Grafos]] [[Categoria:!Páginas com traduções não revistas]]