ラプラシアン行列

グラフ理論の数学的分野において、ラプラシアン行列（ラプラシアンぎょうれつ、）は、グラフの行列表示（行列表現）である。アドミタンス行列 (admittance matrix)、キルヒホッフ行列 (Kirchhoff matrix)、離散ラプラシアン (discrete Laplacian)、またはラプラス行列と呼ばれることもある。ラプラシアン行列はグラフの多くの有用な性質を探るために使うことができる。と一緒に、任意のグラフについての全域木の数を計算するために使うことができる。グラフの最疎カットはによってそのラプラシアンの2番目に小さい固有値を使って近似することができる 。また、を構築するためにも使うことができる。これは、様々な機械学習応用のために有用かもしれない。
定義.
単純グラフのラプラシアン行列.
"n"個の頂点を持つ単純グラフを考えると、そのラプラシアン行列formula_1は以下の式で定義される。
上式において、"D"はグラフの次数行列、"A"は隣接行列である。formula_3は単純グラフであるため、formula_4の成分は1または0のみであり、その対角要素は全て0である。
の場合は、入次数または出次数のいずれかが、応用に依存して使われるだろう。
formula_5の要素は式
によって与えられる。上式において、formula_7は頂点formula_8の次数である。
対称正規化ラプラシアン.
対称正規化ラプラシアン行列は
として定義される。
formula_10の要素は
によって与えられる。
酔歩正規化ラプラシアン.
酔歩正規化ラプラシアン行列は
として定義される。
formula_13の要素は
によって与えられる。
一般化ラプラシアン.
一般化ラプラシアン"Q"は
として定義される。
普通のラプラシアンは一般化ラプラシアンであることが分かる。
例.
以下はラベル付けされた無向グラフとそのラプラシアン行列の単純な例である。
性質.
（無向）グラフ"G"と固有値formula_16を持つそのラプラシアン行列"L"について:
接続行列.
によって与えられる辺"e"（頂点"i"と"j"を連結している; "i" > "j"）と頂点"v"について要素"M"を持つformula_29有向接続行列"M"を定義する。
次に、ラプラシアン行列"L"は
を満たす（formula_31は"M"の転置行列）。
ここで、単位ノルム固有値ベクトルformula_32および対応する固有値formula_33を使ったformula_5の固有値分解を考える。
formula_33はベクトルformula_37とそれ自身の内積として書くことができるため、これはformula_18であり、したがってformula_5の固有値は全て非負であることを示す。
変形ラプラシアン.
変形ラプラシアン（deformed laplacian）は通常以下のように定義される。
上式において、"I"は単位行列、"A"は隣接行列、"D"は次数行列、"s"は（複素）数である。ここで留意すべきは、標準的なラプラシアンは単にformula_41となることである。
対称正規化ラプラシアン.
（対称）正規化ラプラシアンは以下のように定義される。
上式において、"L"は（非正規化）ラプラシアン、"A"は隣接行列、"D"は次数行列である。次数行列"D"は対角行列で正であるため、その逆数平方根formula_43は単にその対角成分が"D"の対角成分の正の平方根の逆数である対角行列となる。対称正規化ラプラシアンは対称行列である。
formula_44が存在する。Sは、列が頂点によって添え字を付けられ、行がGの辺によって添え字が付けられた行列である。これらは、辺e = {u, v} に対応するそれぞれの行がuに対応する列において成分formula_45を、vに対応する列において成分formula_46を、それ以外では0成分を持つことになるように索引付けされる（注: formula_47はSの転置行列を示す）。
正規化ラプラシアンの全ての固有値は実数かつ非負である。これは以下のように見ることができる。formula_10は対称であるため、その固有値は実数である。これらの固有値は全て非負である。固有値λを持つformula_10の固有ベクトル formula_50を考え、formula_51を仮定する（gおよびfを頂点v上の実関数と見なすことができる）。すると、
となる。ここでは内積formula_53（全ての頂点vにわたる和）を用い、formula_54は隣接頂点 {u,v} の全てのにわたる和を示す。量formula_55はfの「ディリクレ和」と呼ばれるが、式formula_56はgのレイリー商と呼ばれる。
1をそれぞれの頂点上に値1を想定する関数とする。すると、formula_57は固有値0を持つformula_58の固有関数である。
実際、正規化対称ラプラシアンの固有値は0 = μ ≤ … ≤ μ ≤ 2を満たす。これらの固有値（正規化ラプラシアンのスペクトルと呼ばれる）は、一般グラフに対するその他のグラフ不変量とよく関連する。
酔歩正規化ラプラシアン.
酔歩 (random walk) 正規化ラプラシアンは
として定義される。"D"は次数行列である。次数行列"D"対角行列であるため、その逆行列formula_60は単純に対角行列として定義され、これは"D"の対応する正の対角成分の逆数である対角成分を持つ。
孤立した頂点（次数が0）について、一般的な選択は対応する要素formula_61を0にすることでる。
この慣習によって、固有値0の多重度がグラフの連結した構成要素の数と等しくなるという良い性質がもたらされる。
formula_13の行列要素は以下の式で与えられる。
酔歩正規化ラプラシアンの名称は、この行列がformula_64（formula_65は単純にグラフ上の酔歩者〈ランダムウォーカー〉の遷移行列）という事実から来ている。例えば、formula_66がi番目の標準基底ベクトルを示すものとする。すると、formula_67は頂点formula_17から一歩進んだ後の酔歩者の位置の分布を示すである; すなわち、 formula_69。より一般的には、もしベクトルformula_70がグラフの頂点上の酔歩者の位置の確率分布であるとすれば、formula_71はformula_72歩後の酔歩者の確率分布である。
となることを確認することができる。
すなわち、formula_13は正規化ラプラシアンformula_10と類似している。この理由のため、formula_13がたとえ一般にエルミート行列でないとしても、実固有値を持つ。実際、その固有値は（エルミート行列である）formula_10のものと一致する。
グラフ.
グラフ上の酔歩に関する余談として、単純無向グラフを考える。酔歩者が時間"t"に頂点"i"にいる確率を考え、酔歩者が時間"t-1"に頂点"j"にいた確率分布を仮定する（任意の頂点に結合したいかなる辺に沿った一歩について一様の見込みを仮定する）:
または行列-ベクトル記法で:
（formula_80として設定される平衡はformula_81として定義される。）
この関係は
と書き直すことができる。
formula_83は簡約隣接行列と呼ばれる対称行列である。したがって、この酔歩者の一歩はformula_84の累乗を必要とする。formula_84は対称行列であるため、これは単純な操作である。
離散ラプラス演算子としての解釈.
ラプラシアン行列は、の特定の事例の行列表現として解釈することができる。このような解釈によって、例えば、ラプラシアン行列を無限の数の頂点と辺を持つグラフ（無限サイズのラプラシアン行列となる）の場合に一般化することが可能となる。
formula_86がグラフにわたる熱分布を記述すると想定する（formula_87は頂点formula_17における熱である）。ニュートンの冷却の法則に従えば、節formula_17と節formula_90の間を移る熱は、もし節formula_17と節formula_90が連結されているならば、formula_93に比例する（節が連結されていないならば、熱は移らない）。
すると、熱用量formula_94について、
行列-ベクトル記法では、
これから、
が得られる。
この方程式が、行列 −"L"がラプラス演算子formula_98を置き換えていると同じ形式であることに気付く。ゆえに、"L"は「グラフラプラシアン」と呼ばれる。
この微分方程式の解を探すため、1階のを解くための標準的な技法を適用する。すなわち、"L"の固有ベクトルformula_32（formula_100）の線形結合としてformula_86を書く。時間に依存するformula_102。
元の式に代入する（ここで留意すべきは、"L"が対称行列であるためにその単位ノルム固有ベクトルformula_32は直交であるという事実を用いる点である）:
この解
である。
前掲のように、"L"の固有値formula_33は非負であり、これは微分方程式の解が（指数関数的に減衰するか一定に留まるかのいずれかのみであるため）平衡に近づくことを示している。これは、formula_33と初期条件formula_108が与えられれば、いかなる時点における解も見つけることができることも示している。全体の初期条件formula_109の観点からそれぞれのformula_17に対するformula_108を探すためには、単純にformula_109を単位ノルム固有ベクトルformula_32へと射影する。
無向グラフの場合は、formula_5が対称行列であるためこれはうまくいき、スペクトル定理によって、その固有ベクトルは全て直交する。そのため、formula_5の固有ベクトルに対する射影は単純に、指数関数的に減衰し、互いに独立な一連の座標への初期条件の直交座標変換である。
平衡挙動.
formula_117を理解するためには、残る項formula_118はformula_119のもののみであることに留意すべきである。これは
となるためである。
言い換えると、系の平衡状態はformula_5の核によって完全に決定される。
なぜなら定義formula_122によれば、全てが1のベクトルformula_123は核内にある。また、グラフ中にformula_94個の互いに素な連結成分が存在するならば、この全てが1のベクトルは1と0からなるformula_94個の独立なformula_126固有ベクトルの和へと分割できる。それぞれの連結成分は連結成分中の要素では1を持つ固有ベクトルと、その他の場所では0を持つ固有ベクトルと対応している。
この結果は、formula_127個の頂点を持つグラフについて任意の初期条件formula_128では、
となる。上式において、
である。
formula_86の個々の要素formula_132、すなわちグラフ中の個々の頂点formula_90について、これを
と書き直すことができる。
言い換えると、定常状態では、formula_86の値はグラフの個々の頂点において同じ値に収束する。この値は全ての頂点の初期値の平均である。これは熱拡散方程式の解であるため、直感的に完全に筋が通っている。グラフ中で隣接する要素は、エネルギーが互いに連結した全ての要素にわたって均等に広がるまでエネルギーを交換することが予測される。
グリッド上の作用素の例.
本節では、グラフにわたって経時的に拡散する関数formula_86の例を示す。この例中のグラフは2次元離散グリッド上に構築され、グリッド上の点は8個の隣接点と連結している。3つの初期点は正の値を持つと指定されているのに対し、グリッド中の残りの値は0である。経時的に、指数関数的減衰によってグリッド全体へとこれらの点上の値が均等に分布する。
このアニメーションを生成するために使われた完全なMATLABのソースコードを以下に示す。ソースコードは、初期条件の指定、これらの初期条件のラプラシアン行列の固有値への射影、これらの射影された初期条件の指数関数的減衰のシミュレーションの過程を示す。
N = 20;%The number of pixels along a dimension of the image
A = zeros(N, N);%The image
Adj = zeros(N*N, N*N);%The adjacency matrix
%Use 8 neighbors, and fill in the adjacency matrix
dx = [-1, 0, 1, -1, 1, -1, 0, 1];
dy = [-1, -1, -1, 0, 0, 1, 1, 1];
for x = 1:N
 for y = 1:N
 index = (x-1)*N + y;
 for ne = 1:length(dx)
 newx = x + dx(ne);
 newy = y + dy(ne);
 if newx > 0 && newx <= N && newy > 0 && newy <= N
 index2 = (newx-1)*N + newy;
 Adj(index, index2) = 1;
 end
 end
 end
end
%%%BELOW IS THE KEY CODE THAT COMPUTES THE SOLUTION TO THE DIFFERENTIAL
%%%EQUATION
Deg = diag(sum(Adj, 2));%Compute the degree matrix
L = Deg - Adj;%Compute the laplacian matrix in terms of the degree and adjacency matrices
[V, D] = eig(L);%Compute the eigenvalues/vectors of the laplacian matrix
D = diag(D);
%Initial condition (place a few large positive values around and
%make everything else zero)
C0 = zeros(N, N);
C0(2:5, 2:5) = 5;
C0(10:15, 10:15) = 10;
C0(2:5, 8:13) = 7;
C0 = C0(:);
C0V = V'*C0;%Transform the initial condition into the coordinate system
%of the eigenvectors
for t = 0:0.05:5
 %Loop through times and decay each initial component
 Phi = C0V.*exp(-D*t);%Exponential decay for each component
 Phi = V*Phi;%Transform from eigenvector coordinate system to original coordinate system
 Phi = reshape(Phi, N, N);
 %Display the results and write to GIF file
 imagesc(Phi);
 caxis([0, 10]);
 title(sprintf('Diffusion t = %3f', t));
 frame = getframe(1);
 im = frame2im(frame);
 [imind, cm] = rgb2ind(im, 256);
 if t == 0
 imwrite(imind, cm, 'out.gif', 'gif', 'Loopcount', inf, 'DelayTime', 0.1);
 else
 imwrite(imind, cm, 'out.gif', 'gif', 'WriteMode', 'append', 'DelayTime', 0.1);
 end
end
負の連続的ラプラシアンに対する近似.
グラフラプラシアン行列は、有限差分法によって得られた（半正定値）ラプラシアン作用素に対する近似の行列形式としてさらに見ることができる。この解釈では、グラフの全ての頂点はグリッド点として扱われる; 頂点の局所連結性はグリッド点における有限差分近似を決定し、グリッドのサイズは常に全ての辺について1であり、いかなるグリッド点上にも制約はない。これは斉次なノイマン境界条件、すなわち自由境界の場合に相当する。
有向多重グラフ.
ラプラシアン行列の類似物は、有向多重グラフに対しても定義することができる。この場合、ラプラシアン行列"L"は
と定義される。上式において"D"は頂点"i"の出次数と等しい"D"を持つ対角行列、"A"は"i"から"j"への辺の数（ループを含む）と等しい"A"を持つ行列である。