ラプラシアン行列
ラプラシアン行列は、離散ラプラス演算子(英語版)の特定の事例の行列表現として解釈することができる。このような解釈によって、例えば、ラプラシアン行列を無限の数の頂点と辺を持つグラフ(無限サイズのラプラシアン行列となる)の場合に一般化することが可能となる。
φ {\textstyle \phi } がグラフにわたる熱分布を記述すると想定する( φ i {\textstyle \phi _{i}} は頂点 i {\textstyle i} における熱である)。ニュートンの冷却の法則に従えば、節 i {\textstyle i} と節 j {\textstyle j} の間を移る熱は、もし節 i {\textstyle i} と節 j {\textstyle j} が連結されているならば、 φ i − φ j {\textstyle \phi _{i}-\phi _{j}} に比例する(節が連結されていないならば、熱は移らない)。
すると、熱用量 k {\textstyle k} について、
d φ i d t = − k ∑ j A 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 ( l i j ) φ j .
酔歩正規化ラプラシアン行列は
L rw := D − 1 L = I − D − 1 A {\displaystyle L^{\text{rw}}:=D^{-1}L=I-D^{-1}A}
として定義される。
L rw {\textstyle L^{\text{rw}}} の要素は
L i , j rw := { 1 if i = j and deg  ( v i ) ≠ 0 − 1 deg  ( v i ) if i ≠ j and v i is adjacent to v j 0 otherwise . {\displaystyle 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}}}
によって与えられる。