la matrice Laplacienne peut être interprétée comme une représentation matricielle d’un cas particulier de L’opérateur de Laplace discret. Une telle interprétation permet, par exemple, de généraliser la matrice Laplacienne au cas des graphes avec un nombre infini de sommets et d’arêtes, conduisant à une matrice Laplacienne de taille infinie.
d ϕ i d t = − k ∑ j i j ( ϕ i − ϕ j ) = − k ( ϕ i ∑ j A i j − ∑ j A i j ϕ j ) = − k ( ϕ i deg ( v i ) − ∑ j A i j ϕ j ) = − k ∑ j ( δ i j deg ( v i ) − A i j ) ϕ j = − k ∑ j ( ℓ i j ) ϕ j ., {\displaystyle {\begin{aligné}{\frac {d\phi _{i}}{dt}}&=-k\am _{j}A_{ij}\left(\phi _{i}-\phi _{j}\right)\\&=-k\left(\phi _{i}\am _{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{aligné}}}
En utilisant la notation matricielle,
d ϕ d t = − k ( D − A ) ϕ = − k L ϕ , {\displaystyle {\begin{aligné}{\frac {d\phi }{dt}}&=-k(D-A)\phi \\&=-kL\phi\end{aligné}}}
ce qui donne
d ϕ d t + k L ϕ = 0. {\displaystyle {\frac {d\phi }{dt}}+kL\phi =0.}
notez que cette équation prend la même forme que l’équation de la chaleur, où la matrice-L remplace l’opérateur Laplacien ∇ 2 {\textstyle \ nabla ^{2}} ; d’où le « graphe Laplacien ».,
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{aligné}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}\left\\\Rightarrow &{\frac {dc_{i}(t)}{dt}}+k\lambda _{i}c_{i}(t)=0,\\\end{aligné}}}
dont la solution est
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 } .
dans le cas des graphes non orientés, cela fonctionne parce que L {\textstyle l} est symétrique, et par le théorème spectral, ses vecteurs propres sont tous orthogonaux. Ainsi, la projection sur les vecteurs propres de l {\textstyle l} est simplement une transformation de coordonnées orthogonales de la condition initiale en un ensemble de coordonnées qui se désintègrent exponentiellement et indépendamment les unes des autres.,
l’Équilibre behaviorEdit
lim t → ∞ e − k λ i t = { 0 si λ i > 0 1 si λ i = 0 } {\displaystyle \lim _{t\to \infty }e^{-k\lambda _{i}t}=\left\{{\begin{array}{rlr}0&{\text{si}}&\lambda _{i}>0\\1&{\text{si}}&\lambda _{i}=0\end{array}}\right\}}
En d’autres termes, l’état d’équilibre du système est entièrement déterminée par le noyau de L {\textstyle L} .,
La conséquence de cela est que, pour une condition initiale c ( 0 ) {\textstyle c(0)} pour un graphe ayant N {\textstyle N} de sommets
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}} }
où
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)} .,
En d’autres termes, à l’état d’équilibre, la valeur de ϕ {\textstyle \phi } converge vers la même valeur à chacun des sommets du graphe, qui est la moyenne des valeurs initiales à tous les sommets. Puisque c’est la solution à l’équation de diffusion de la chaleur, cela a un sens parfait intuitivement. Nous nous attendons à ce que les éléments voisins du graphique échangent de l’énergie jusqu’à ce que cette énergie soit répartie uniformément dans tous les éléments connectés les uns aux autres.,
Exemple de l’opérateur sur un gridEdit
Ce GIF montre la progression de la diffusion, comme résolu par le graphique laplacien technique. Un graphique est construit sur une grille, où chaque pixel du graphique est connecté à ses 8 pixels limitrophes. Les valeurs de l’image se diffusent ensuite en douceur vers leurs voisins au fil du temps via ces connexions. Cette image particulière commence avec trois valeurs de points forts qui débordent lentement sur leurs voisins. L’ensemble du système finit par atteindre la même valeur à l’équilibre.,
Cette section montre un exemple d’une fonction diff {\textstyle \phi } diffusant dans le temps à travers un graphique. Le graphique de cet exemple est construit sur une grille discrète 2D, avec des points sur la grille connectés à leurs huit voisins. Trois points initiaux sont spécifiés pour avoir une valeur positive, tandis que les autres valeurs de la grille sont nulles. Au fil du temps, la décroissance exponentielle agit pour répartir les valeurs à ces points uniformément dans toute la grille.
le code source Matlab complet qui a été utilisé pour générer cette animation est fourni ci-dessous., Il montre le processus de spécification des conditions initiales, de projection de ces conditions initiales sur les valeurs propres de la matrice Laplacienne et de simulation de la décroissance exponentielle de ces conditions initiales projetées.