ラプラシアン行列
より一般的には、もしベクトル x {\textstyle x} がグラフの頂点上の酔歩者の位置の確率分布であるとすれば、 x ′ = x P t {\textstyle x'=xP^{t}} は t {\textstyle t} 歩後の酔歩者の確率分布である。
L rw = I − D − 1 2 ( I − L sym ) D 1 2 {\displaystyle L^{\text{rw}}=I-D^{-{\frac {1}{2}}}\left(I-L^{\text{sym}}\right)D^{\frac {1}{2}}}
となることを確認することができる。
すなわち、 L rw {\textstyle L^{\text{rw}}} は正規化ラプラシアン L sym {\textstyle L^{\text{sym}}} と類似している。この理由のため、 L rw {\textstyle L^{\text{rw}}} がたとえ一般にエルミート行列でないとしても、実固有値を持つ。実際、その固有値は(エルミート行列である) L sym {\textstyle L^{\text{sym}}} のものと一致する。
グラフ理論の数学的分野において、ラプラシアン行列(ラプラシアンぎょうれつ、英: Laplacian matrix)は、グラフの行列表示(行列表現)である。アドミタンス行列 (admittance matrix)、キルヒホッフ行列 (Kirchhoff matrix)、離散ラプラシアン (discrete Laplacian)、またはラプラス行列と呼ばれることもある。ラプラシアン行列はグラフの多くの有用な性質を探るために使うことができる。キルヒホッフの定理(英語版)と一緒に、任意のグラフについての全域木の数を計算するために使うことができる。グラフの最疎カットはチーガーの不等式(英語版)によってそのラプラシアンの2番目に小さい固有値を使って近似することができる 。また、低次元埋め込み(英語版)を構築するためにも使うことができる。これは、様々な機械学習応用のために有用かもしれない。