Matricea laplaciană

matricea laplaciană poate fi interpretată ca o reprezentare matricială a unui caz particular al operatorului Laplace discret. O astfel de interpretare permite, de exemplu, generalizarea matricei Laplaciene în cazul graficelor cu un număr infinit de vârfuri și muchii, ceea ce duce la o matrice laplaciană de o dimensiune infinită.

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

În matrice-vector notație,

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

care oferă

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

observați că această ecuație are aceeași formă ca ecuația de căldură, unde matricea-L înlocuiește operatorul laplacian ∇ 2 {\textstyle \ nabla ^{2}}; prin urmare,”graficul Laplacian”.,

0 = d ( ∑ c i ( t ) v i ) d t + k L ( ∑ c i ( t ) v i ) = ∑ i = ∑ m ⇒ d c i ( t ) d t + k λ i c i ( t ) = 0 , {\displaystyle {\begin{aliniat}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\\=&\sum _{i}\stâng\\\Rightarrow &{\frac {dc_{m}(t)}{dt}}+k\lambda _{i}c_{i}(t)=0,\\\end{aliniat}}}

cărei soluție este

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 ⟩ {\displaystyle c_{i}(0)=\left\langle \phi (0),\mathbf {v} _{i}\corect\rangle } .

în cazul graficelor nedirecționate, aceasta funcționează deoarece l {\textstyle l} este simetric, iar prin teorema spectrală, vectorii săi proprii sunt toți ortogonali. Deci proiecția pe vectorii proprii de L {\textstyle L} este pur și simplu o transformare de coordonate ortogonale de condiția inițială pentru un set de coordonate care cariilor exponențial și independent unul de celălalt.,

Echilibru behaviorEdit

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

cu alte cuvinte, starea de echilibru a sistemului este complet determinată de nucleul de L {\textstyle L} .,

consecința acestui fapt este că pentru o anumită condiție inițială c ( 0 ) {\textstyle c(0)} pentru un graf cu N {\textstyle N} nodurile

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

unde

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}}\sum _{i=1}^{N}c_{i}(0)} .,

cu alte cuvinte, la starea de echilibru, valoarea lui ϕ {\textstyle \ phi } converge la aceeași valoare la fiecare dintre vârfurile graficului, care este media valorilor inițiale la toate vârfurile. Deoarece aceasta este soluția ecuației de difuzie a căldurii, acest lucru are sens perfect intuitiv. Ne așteptăm ca elementele vecine din grafic să facă schimb de energie până când acea energie este distribuită uniform în toate elementele care sunt conectate între ele.,

Exemplu de operator pe un gridEdit

această secțiune prezintă un exemplu de funcție ϕ {\textstyle \phi } difuzând în timp printr-un grafic. Graficul din acest exemplu este construit pe o grilă discretă 2D, cu puncte de pe grilă conectate la cei opt vecini ai lor. Trei puncte inițiale sunt specificate pentru a avea o valoare pozitivă, în timp ce restul valorilor din grilă sunt zero. În timp, decăderea exponențială acționează pentru a distribui valorile în aceste puncte în mod egal pe întreaga rețea.codul sursă Matlab complet care a fost folosit pentru a genera această animație este furnizat mai jos., Acesta arată procesul de specificare a condițiilor inițiale, proiectând aceste condiții inițiale pe valorile proprii ale matricei Laplaciene și simulând degradarea exponențială a acestor condiții inițiale proiectate.