Laplaciaanse matrix

De Laplaciaanse matrix kan worden geïnterpreteerd als een matrixrepresentatie van een bepaald geval van de discrete laplaceoperator. Een dergelijke interpretatie maakt het bijvoorbeeld mogelijk om de Laplaciaanse matrix te veralgemenen tot het geval van grafieken met een oneindig aantal hoekpunten en randen, wat leidt tot een Laplaciaanse matrix van een oneindige grootte.

d ϕ i d t = − k ∑ j i j ( ϕ i − ϕ j ) = − k ( ϕ i ∑ j i j − ∑ j i j ϕ j ) = − k ( ϕ ik deg ⁡ ( v-i ) − ∑ j i j ϕ j ) = − k ∑ j ( δ i j deg ⁡ ( v-i ) − i j ) ϕ j = − k ∑ j ( ℓ i j ) ϕ j ., {\displaystyle {\begin{aligned}{\frac {d\phi _{i}}{dt}}&=-k\am _{j}A_{ij}\left(\phi _{i}-\phi _{j}\right)\\&=-k\left(\phi _{i}\ben _{j}A_{ij}-\am _{j}A_{ij}\phi _{j}\right)\\&=-k\left(\phi _{i}\ \deg(v_{i})-\I _{j}A_{ij}\phi _{j}\right)\\&=-k\am _{j}\left(\delta _{ij}\ \deg(v_{i})-A_{ij}\right)\phi _{j}\\&=-k\am _{j}\left(\ell _{ij}\right)\phi _{j}.,\end{aligned}}}

in matrix-Vector notatie,

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

Wat

D ϕ d t + k l ϕ = 0 geeft. {\displaystyle {\frac {d \ phi }{dt}}+kL\phi = 0.}

merk op dat deze vergelijking dezelfde vorm aanneemt als de warmtevergelijking, waarbij de matrix −L de laplaciaanse operator vervangt ∇ 2 {\textstyle \nabla ^{2}} ; vandaar de “graph Laplacian”.,

0 d = ( ∑i c i ( t ) v i ) d t + k) L ( ∑ i c i ( t ) v i ) = ∑ i = ∑ i ⇒ d c i ( t ) d t + k) λ i c i ( t ) = 0 , {\displaystyle {\begin{aligned}0=&{\frac {d\left(\som _{i}c_{i}(t)\mathbf {v} _{i}\right)}{dt}}+kL\left(\som _{i}c_{i}(t)\mathbf {v} _{i}\right)\\=&\som _{i}\left\\=&\som _{i}\links\\\Rightarrow &{\frac {dc_{i}(t)}{dt}}+k\lambda _{i}c_{i}(t)=0,\\\end{aligned}}}

waarvan de oplossing is

c i ( t ) = c i ( 0 ) e − k λ i t . {\displaystyle c_{i} (t) = c_{i}(0) e^{-k\lambda _{i}t}.,} c i (0)=⟨ ϕ ( 0), v i ⟩ {\displaystyle C_{i}(0) = \left\langle \phi (0),\mathbf {v} _{i}\right\rangle } .

in het geval van niet-gerichte grafieken werkt dit omdat L {\textstyle L} symmetrisch is, en door de spectrale stelling zijn de eigenvectoren allemaal orthogonaal. Dus de projectie op de eigenvectoren van L {\textstyle L} is gewoon een orthogonale coördinatentransformatie van de beginconditie tot een verzameling coördinaten die exponentieel en onafhankelijk van elkaar vervallen.,

Evenwicht behaviorEdit

lim t → ∞ e − k λ i t = { 0 als λ i > 0 1 als λ i = 0 } {\displaystyle \lim _{t\to \infty }e^{-k\lambda _{i}t}=\left\{{\begin{array}{rlr}0&{\text{als}}&\lambda _{i}>0\\1&{\text{als}}&\lambda _{i}=0\end{array}}\right\}}

In andere woorden, de evenwichtstoestand van het systeem wordt volledig bepaald door de kernel van L {\textstyle L} .,

Het gevolg hiervan is dat voor een gegeven begintoestand c ( 0 ) {\textstyle c(0)} voor een grafiek met N {\textstyle N} hoekpunten

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

waar

v 1 = 1 N {\displaystyle \mathbf {v^{1}} ={\frac {1}{\sqrt {N}}}} lim t → ∞ ϕ j ( t ) = 1 N ∑ i = 1 N c i ( 0 ) {\displaystyle \lim _{t\to \infty }\phi _{j}(t)={\frac {1}{N}}\som _{i=1}^{N}c_{i}(0)} .,

met andere woorden, bij steady state convergeert de waarde van ϕ {\textstyle \phi } naar dezelfde waarde op elk van de hoekpunten van de grafiek, wat het gemiddelde is van de beginwaarden op alle hoekpunten. Aangezien dit de oplossing is voor de warmtediffusievergelijking, is dit intuïtief volkomen logisch. We verwachten dat naburige elementen in de grafiek energie zullen uitwisselen totdat die energie gelijkmatig verdeeld is over alle elementen die met elkaar verbonden zijn.,

voorbeeld van de operator op een rooster

Deze sectie toont een voorbeeld van een functie ϕ {\textstyle \ phi } die in de loop van de tijd door een grafiek verspreidt. De grafiek in dit voorbeeld is geconstrueerd op een 2D discreet raster, met punten op het raster verbonden met hun acht buren. Drie beginpunten worden gespecificeerd om een positieve waarde te hebben, terwijl de rest van de waarden in het raster nul zijn. Na verloop van tijd, de exponentiële verval werkt om de waarden op deze punten gelijkmatig te verdelen over het hele raster.

de volledige Matlab-broncode die werd gebruikt om deze animatie te genereren wordt hieronder weergegeven., Het toont het proces van het specificeren van initiële condities, het projecteren van deze initiële condities op de eigenwaarden van de Laplaciaanse Matrix, en het simuleren van het exponentiële verval van deze geprojecteerde initiële condities.