ラプラシアン行列
酔歩 (random walk) 正規化ラプラシアンは
L rw := D − 1 L {\displaystyle L^{\text{rw}}:=D^{-1}L}
として定義される。Dは次数行列である。次数行列D対角行列であるため、その逆行列 D − 1 {\textstyle D^{-1}} は単純に対角行列として定義され、これはDの対応する正の対角成分の逆数である対角成分を持つ。
孤立した頂点(次数が0)について、一般的な選択は対応する要素 L i , i rw {\textstyle L_{i,i}^{\text{rw}}} を0にすることでる。
この慣習によって、固有値0の多重度がグラフの連結した構成要素の数と等しくなるという良い性質がもたらされる。
L rw {\textstyle L^{\text{rw}}} の行列要素は以下の式で与えられる。
d ( ∑ i c i v i ) d t + k L ( ∑ i c i v i ) = 0 ∑ i [ d c i d t v i + k c i L v i ] = ∑ i [ d c i d t v i + k c i λ i v i ] = d c i d t + k λ i c i = 0 {\displaystyle {\begin{aligned}{\frac {d\left(\sum _{i}c_{i}\mathbf {v} _{i}\right)}{dt}}+kL\left(\sum _{i}c_{i}\mathbf {v} _{i}\right)&=0\\\sum _{i}\left[{\frac {dc_{i}}{dt}}\mathbf {v} _{i}+kc_{i}L\mathbf {v} _{i}\right]&=\\\sum _{i}\left[{\frac {dc_{i}}{dt}}\mathbf {v} _{i}+kc_{i}\lambda _{i}\mathbf {v} _{i}\right]&=\\{\frac {dc_{i}}{dt}}+k\lambda _{i}c_{i}&=0\\\end{aligned}}}
この解
c i ( t ) = c i ( 0 ) e − k λ i t {\displaystyle c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}}
である。
前掲のように、Lの固有値 λ i {\textstyle \lambda _{i}} は非負であり、これは微分方程式の解が(指数関数的に減衰するか一定に留まるかのいずれかのみであるため)平衡に近づくことを示している。
一般化ラプラシアンQは
{ Q i , j < 0 if i ≠ j and v i is adjacent to v j Q i , j = 0 if i ≠ j and v i is not adjacent to v j any number otherwise . {\displaystyle {\begin{cases}Q_{i,j}<0&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\Q_{i,j}=0&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is not adjacent to }}v_{j}\\{\mbox{any number}}&{\mbox{otherwise}}.\end{cases}}}
として定義される。
普通のラプラシアンは一般化ラプラシアンであることが分かる。