ラプラシアン行列
以下はラベル付けされた無向グラフとそのラプラシアン行列の単純な例である。
D − 1 2 p ( t ) = [ D − 1 2 A D − 1 2 ] D − 1 2 p ( t − 1 ) {\displaystyle D^{-{\frac {1}{2}}}p(t)=\left[D^{-{\frac {1}{2}}}AD^{-{\frac {1}{2}}}\right]D^{-{\frac {1}{2}}}p(t-1)}
と書き直すことができる。
A reduced ≡ D − 1 2 A D − 1 2 {\textstyle A_{\text{reduced}}\equiv D^{-{\frac {1}{2}}}AD^{-{\frac {1}{2}}}} は簡約隣接行列と呼ばれる対称行列である。したがって、この酔歩者の一歩は A reduced {\textstyle A_{\text{reduced}}} の累乗を必要とする。 A reduced {\textstyle A_{\text{reduced}}} は対称行列であるため、これは単純な操作である。
{\displaystyle {\begin{aligned}{\frac {d\phi _{i}}{dt}}&=-k\sum _{j}A_{ij}\left(\phi _{i}-\phi _{j}\right)\\&=-k\left(\phi _{i}\sum _{j}A_{ij}-\sum _{j}A_{ij}\phi _{j}\right)\\&=-k\left(\phi _{i}\ \deg(v_{i})-\sum _{j}A_{ij}\phi _{j}\right)\\&=-k\sum _{j}\left(\delta _{ij}\ \deg(v_{i})-A_{ij}\right)\phi _{j}\\&=-k\sum _{j}\left(\ell _{ij}\right)\phi _{j}.\end{aligned}}}
行列-ベクトル記法では、
d φ d t = − k ( D − A ) φ = − k L φ {\displaystyle {\begin{aligned}{\frac {d\phi }{dt}}&=-k(D-A)\phi \\&=-kL\phi \end{aligned}}}
これから、
d φ d t + k L φ = 0 {\displaystyle {\frac {d\phi }{dt}}+kL\phi =0}
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}}}
酔歩正規化ラプラシアンの名称は、この行列が L rw = I − P {\textstyle L^{\text{rw}}=I-P} ( P = D − 1 A {\textstyle P=D^{-1}A} は単純にグラフ上の酔歩者〈ランダムウォーカー〉の遷移行列)という事実から来ている。例えば、 e i {\textstyle e_{i}} がi番目の標準基底ベクトルを示すものとする。すると、 x = e i P {\textstyle x=e_{i}P} は頂点 i {\textstyle i} から一歩進んだ後の酔歩者の位置の分布を示す確率ベクトル(英語版)である; すなわち、 x j = P ( v i → v j ) {\textstyle x_{j}=\mathbb {P} \left(v_{i}\to v_{j}\right)} 。
これは、 λ i {\textstyle \lambda _{i}} と初期条件 c i ( 0 ) {\textstyle c_{i}(0)} が与えられれば、いかなる時点における解も見つけることができることも示している。全体の初期条件 φ ( 0 ) {\textstyle \phi (0)} の観点からそれぞれの i {\textstyle i} に対する c i ( 0 ) {\textstyle c_{i}(0)} を探すためには、単純に φ ( 0 ) {\textstyle \phi (0)} を単位ノルム固有ベクトル v i {\textstyle \mathbf {v} _{i}} へと射影する。
c i ( 0 ) = ⟨ φ ( 0 ) , v i ⟩ {\displaystyle c_{i}(0)=\left\langle \phi (0),\mathbf {v} _{i}\right\rangle }
無向グラフの場合は、 L {\textstyle L} が対称行列であるためこれはうまくいき、スペクトル定理によって、その固有ベクトルは全て直交する。そのため、 L {\textstyle L} の固有ベクトルに対する射影は単純に、指数関数的に減衰し、互いに独立な一連の座標への初期条件の直交座標変換である。