ラプラシアン行列
となる。ここでは内積 ⟨ f , g ⟩ = ∑ v f ( v ) g ( v ) {\textstyle \langle f,g\rangle =\sum _{v}f(v)g(v)} (全ての頂点vにわたる和)を用い、 ∑ u ∼ v {\textstyle \sum _{u\sim v}} は隣接頂点 {u,v} の全ての非順序対(英語版)にわたる和を示す。量 ∑ u , v ( f ( u ) − f ( v ) ) 2 {\textstyle \sum _{u,v}(f(u)-f(v))^{2}} はfの「ディリクレ和」と呼ばれるが、式 ⟨ g , L sym g ⟩ ⟨ g , g ⟩ {\textstyle {\frac {\left\langle g,L^{\text{sym}}g\right\rangle }{\langle g,g\rangle }}} はgのレイリー商と呼ばれる。
1をそれぞれの頂点上に値1を想定する関数とする。すると、 D 1 2 1 {\textstyle D^{\frac {1}{2}}1} は固有値0を持つ L sym {\textstyle L^{\text{sym}}} の固有関数である。
実際、正規化対称ラプラシアンの固有値は0 = μ0 ≤ ... ≤ μn−1 ≤ 2を満たす。これらの固有値(正規化ラプラシアンのスペクトルと呼ばれる)は、一般グラフに対するその他のグラフ不変量とよく関連する。
ラプラシアン行列の類似物は、有向多重グラフに対しても定義することができる。この場合、ラプラシアン行列Lは
L = D − A {\displaystyle L=D-A}
と定義される。上式においてDは頂点iの出次数と等しいDi,iを持つ対角行列、Aはiからjへの辺の数(ループを含む)と等しいAi,jを持つ行列である。
対称正規化ラプラシアン行列は
L sym := D − 1 2 L D − 1 2 = I − D − 1 2 A D − 1 2 {\displaystyle L^{\text{sym}}:=D^{-{\frac {1}{2}}}LD^{-{\frac {1}{2}}}=I-D^{-{\frac {1}{2}}}AD^{-{\frac {1}{2}}}} ,
として定義される。
L sym {\textstyle L^{\text{sym}}} の要素は
L i , j sym := { 1 if i = j and deg  ( v i ) ≠ 0 − 1 deg  ( v i ) deg  ( v j ) if i ≠ j and v i is adjacent to v j 0 otherwise . {\displaystyle 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}}}
によって与えられる。
v 1 = 1 N [ 1 , 1 , . . . , 1 ] {\displaystyle \mathbf {v^{1}} ={\frac {1}{\sqrt {N}}}[1,1,...,1]}
である。
φ {\textstyle \phi } の個々の要素 φ j {\textstyle \phi _{j}} 、すなわちグラフ中の個々の頂点 j {\textstyle j} について、これを
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)}
と書き直すことができる。
言い換えると、定常状態では、 φ {\textstyle \phi } の値はグラフの個々の頂点において同じ値に収束する。この値は全ての頂点の初期値の平均である。これは熱拡散方程式の解であるため、直感的に完全に筋が通っている。グラフ中で隣接する要素は、エネルギーが互いに連結した全ての要素にわたって均等に広がるまでエネルギーを交換することが予測される。