ラプラシアン行列

ウィキペディア

ラプラシアン行列

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/08/02 13:37 UTC 版)

グラフ理論の数学的分野において、ラプラシアン行列（ラプラシアンぎょうれつ、英: Laplacian matrix）は、グラフの行列表示（行列表現）である。アドミタンス行列 (admittance matrix)、キルヒホッフ行列 (Kirchhoff matrix)、離散ラプラシアン (discrete Laplacian)、またはラプラス行列と呼ばれることもある。ラプラシアン行列はグラフの多くの有用な性質を探るために使うことができる。キルヒホッフの定理と一緒に、任意のグラフについての全域木の数を計算するために使うことができる。グラフの最疎カットはチーガーの不等式によってそのラプラシアンの2番目に小さい固有値を使って近似することができる 。また、低次元埋め込みを構築するためにも使うことができる。これは、様々な機械学習応用のために有用かもしれない。

定義

単純グラフのラプラシアン行列

n個の頂点を持つ単純グラフ（ループや多重辺を持たない無向グラフ）を考えると、そのラプラシアン行列 ${\textstyle L_{n\times n}}$ ${\textstyle \left({\begin{array}{rrrrrr}2&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{array}}\right)}$

このGIFは、グラフラプラシアン法によって解かれたような拡散の進行を示している。グラフはグリッドにわたって構築され、グラフ中の個々のピクセルは隣接している8個のピクセルに連結している。次に、画像中の値はこれらの連結を介して隣接ピクセルへと滑らかに拡散する。この画像は、3つの点に強い値を持つ状態から始まり、この値はゆっくりと隣へ波及する。系全体は最終的に平衡に達すると同じ値に落ち着く。

本節では、グラフにわたって経時的に拡散する関数 ${\textstyle \phi }$ カテゴリ / コモンズ