ラプラシアン行列

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

1. 定義
-----

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

//n//個の頂点を持つ単純グラフを考えると、そのラプラシアン行列は以下の式で定義される。

上式において、//D//はグラフの次数行列、//A//は隣接行列である。は単純グラフであるため、の成分は1または0のみであり、その対角要素は全て0である。

有向グラフの場合は、入次数または出次数のいずれかが、応用に依存して使われるだろう。

の要素は式

によって与えられる。上式において、は頂点の次数である。

1.1.1. 対称正規化ラプラシアン
------------------

対称正規化ラプラシアン行列は

,として定義される。

の要素は

によって与えられる。

1.1.2. 酔歩正規化ラプラシアン
------------------

酔歩正規化ラプラシアン行列は

として定義される。

の要素は

によって与えられる。

1.1.3. 一般化ラプラシアン
----------------

一般化ラプラシアン//Q//は

として定義される。

普通のラプラシアンは一般化ラプラシアンであることが分かる。

2. 例
----

以下はラベル付けされた無向グラフとそのラプラシアン行列の単純な例である。



3. 性質
-----

グラフ//G//と固有値を持つそのラプラシアン行列//L//について:

//L//は対称である。
//L//は半正定値である。これは接続行列の節で検証される。これは、ラプラシアンが対称であり、優対角行列であるという事実からも見ることができる。
//L//はM-行列である。
//L//の全ての行の和と列の和はゼロである。実際、和の計算において、頂点の次数には隣接する頂点ごとに「−1」が足される。
その結果、となる。これは、ベクトルがを満たすためである。これは、ラプラシアン行列が特異行列であることも暗示する。
グラフ中の成分 の数はラプラシアンの零空間の次元であり、0固有値の代数的多重度である。
//L//の最小の非ゼロ固有値はスペクトルギャップと呼ばれる。
//L//の2番目に小さな固有値は//G//の代数的連結度であり、グラフの最疎カットを近似する。
ラプラシアンは、関数のn次元ベクトル空間上の作用素である。
Gがk正則である時、正規化ラプラシアンはである。
複数の連結成分を持つグラフについて、//L//は区分対角行列であり、それぞれの区分はそれぞれの成分についての各ラプラシアン行列である。
ラプラシアン行列//L//の跡はと等しい。

4. 接続行列
-------

によって与えられる辺//e//と頂点//v//について要素//M//を持つ有向接続行列//M//を定義する。

次に、ラプラシアン行列//L//は

を満たす。

ここで、単位ノルム固有値ベクトルおよび対応する固有値を使ったの固有値分解を考える。

はベクトルとそれ自身の内積として書くことができるため、これはであり、したがっての固有値は全て非負であることを示す。

5. 変形ラプラシアン
-----------

変形ラプラシアンは通常以下のように定義される。

上式において、//I//は単位行列、//A//は隣接行列、//D//は次数行列、//s//は数である。ここで留意すべきは、標準的なラプラシアンは単にとなることである。

6. 対称正規化ラプラシアン
--------------

正規化ラプラシアンは以下のように定義される。

上式において、//L//はラプラシアン、//A//は隣接行列、//D//は次数行列である。次数行列//D//は対角行列で正であるため、その逆数平方根は単にその対角成分が//D//の対角成分の正の平方根の逆数である対角行列となる。対称正規化ラプラシアンは対称行列である。

が存在する。Sは、列が頂点によって添え字を付けられ、行がGの辺によって添え字が付けられた行列である。これらは、辺e = {u, v} に対応するそれぞれの行がuに対応する列において成分を、vに対応する列において成分を、それ以外では0成分を持つことになるように索引付けされる。

正規化ラプラシアンの全ての固有値は実数かつ非負である。これは以下のように見ることができる。は対称であるため、その固有値は実数である。これらの固有値は全て非負である。固有値λを持つの固有ベクトル を考え、を仮定する。すると、

となる。ここでは内積を用い、は隣接頂点 {u,v} の全てのにわたる和を示す。量はfの「ディリクレ和」と呼ばれるが、式はgのレイリー商と呼ばれる。

1をそれぞれの頂点上に値1を想定する関数とする。すると、は固有値0を持つの固有関数である。

実際、正規化対称ラプラシアンの固有値は0 = μ ≤ … ≤ μ ≤ 2を満たす。これらの固有値は、一般グラフに対するその他のグラフ不変量とよく関連する。

7. 酔歩正規化ラプラシアン
--------------

酔歩  正規化ラプラシアンは

として定義される。//D//は次数行列である。次数行列//D//対角行列であるため、その逆行列は単純に対角行列として定義され、これは//D//の対応する正の対角成分の逆数である対角成分を持つ。

孤立した頂点について、一般的な選択は対応する要素を0にすることでる。

この慣習によって、固有値0の多重度がグラフの連結した構成要素の数と等しくなるという良い性質がもたらされる。

の行列要素は以下の式で与えられる。

酔歩正規化ラプラシアンの名称は、この行列がという事実から来ている。例えば、がi番目の標準基底ベクトルを示すものとする。すると、は頂点から一歩進んだ後の酔歩者の位置の分布を示すである; すなわち、 。より一般的には、もしベクトルがグラフの頂点上の酔歩者の位置の確率分布であるとすれば、は歩後の酔歩者の確率分布である。

となることを確認することができる。

すなわち、は正規化ラプラシアンと類似している。この理由のため、がたとえ一般にエルミート行列でないとしても、実固有値を持つ。実際、その固有値はのものと一致する。

7.1. グラフ
--------

グラフ上の酔歩に関する余談として、単純無向グラフを考える。酔歩者が時間//t//に頂点//i//にいる確率を考え、酔歩者が時間//t-1//に頂点//j//にいた確率分布を仮定する:

または行列-ベクトル記法で:

この関係は

と書き直すことができる。

は簡約隣接行列と呼ばれる対称行列である。したがって、この酔歩者の一歩はの累乗を必要とする。は対称行列であるため、これは単純な操作である。

8. 離散ラプラス演算子としての解釈
------------------

ラプラシアン行列は、の特定の事例の行列表現として解釈することができる。このような解釈によって、例えば、ラプラシアン行列を無限の数の頂点と辺を持つグラフの場合に一般化することが可能となる。

がグラフにわたる熱分布を記述すると想定する。ニュートンの冷却の法則に従えば、節と節の間を移る熱は、もし節と節が連結されているならば、に比例する。

すると、熱用量について、

行列-ベクトル記法では、

これから、

が得られる。

この方程式が、行列 −//L//がラプラス演算子を置き換えていると同じ形式であることに気付く。ゆえに、//L//は「グラフラプラシアン」と呼ばれる。

この微分方程式の解を探すため、1階のを解くための標準的な技法を適用する。すなわち、//L//の固有ベクトルの線形結合としてを書く。時間に依存する。

元の式に代入する:

この解

である。

前掲のように、//L//の固有値は非負であり、これは微分方程式の解が平衡に近づくことを示している。これは、と初期条件が与えられれば、いかなる時点における解も見つけることができることも示している。全体の初期条件の観点からそれぞれのに対するを探すためには、単純にを単位ノルム固有ベクトルへと射影する。

無向グラフの場合は、が対称行列であるためこれはうまくいき、スペクトル定理によって、その固有ベクトルは全て直交する。そのため、の固有ベクトルに対する射影は単純に、指数関数的に減衰し、互いに独立な一連の座標への初期条件の直交座標変換である。

8.1. 平衡挙動
---------

を理解するためには、残る項はのもののみであることに留意すべきである。これは

となるためである。

言い換えると、系の平衡状態はの核によって完全に決定される。

なぜなら定義によれば、全てが1のベクトルは核内にある。また、グラフ中に個の互いに素な連結成分が存在するならば、この全てが1のベクトルは1と0からなる個の独立な固有ベクトルの和へと分割できる。それぞれの連結成分は連結成分中の要素では1を持つ固有ベクトルと、その他の場所では0を持つ固有ベクトルと対応している。

この結果は、個の頂点を持つグラフについて任意の初期条件では、

となる。上式において、

である。

の個々の要素、すなわちグラフ中の個々の頂点について、これを

と書き直すことができる。

言い換えると、定常状態では、の値はグラフの個々の頂点において同じ値に収束する。この値は全ての頂点の初期値の平均である。これは熱拡散方程式の解であるため、直感的に完全に筋が通っている。グラフ中で隣接する要素は、エネルギーが互いに連結した全ての要素にわたって均等に広がるまでエネルギーを交換することが予測される。

8.2. グリッド上の作用素の例
----------------

本節では、グラフにわたって経時的に拡散する関数の例を示す。この例中のグラフは2次元離散グリッド上に構築され、グリッド上の点は8個の隣接点と連結している。3つの初期点は正の値を持つと指定されているのに対し、グリッド中の残りの値は0である。経時的に、指数関数的減衰によってグリッド全体へとこれらの点上の値が均等に分布する。

このアニメーションを生成するために使われた完全なMATLABのソースコードを以下に示す。ソースコードは、初期条件の指定、これらの初期条件のラプラシアン行列の固有値への射影、これらの射影された初期条件の指数関数的減衰のシミュレーションの過程を示す。

N = 20;%The number of pixels along a dimension of the image A = zeros;%The image Adj = zeros;%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 = *N + y; for ne = 1:length newx = x + dx; newy = y + dy; if newx > 0 && newx <= N && newy > 0 && newy <= N index2 = *N + newy; Adj = 1; end end end end

%%%BELOW IS THE KEY CODE THAT COMPUTES THE SOLUTION TO THE DIFFERENTIAL %%%EQUATION Deg = diag);%Compute the degree matrix L = Deg - Adj;%Compute the laplacian matrix in terms of the degree and adjacency matrices [V, D] = eig;%Compute the eigenvalues/vectors of the laplacian matrix D = diag;

%Initial condition  C0 = zeros; C0 = 5; C0 = 10; C0 = 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;%Exponential decay for each component Phi = V*Phi;%Transform from eigenvector coordinate system to original coordinate system Phi = reshape; %Display the results and write to GIF file imagesc; caxis; title); frame = getframe; im = frame2im; [imind, cm] = rgb2ind; if t == 0 imwrite; else imwrite; end end<WtXmlEndTag />

9. 負の連続的ラプラシアンに対する近似
--------------------

グラフラプラシアン行列は、有限差分法によって得られたラプラシアン作用素に対する近似の行列形式としてさらに見ることができる。この解釈では、グラフの全ての頂点はグリッド点として扱われる; 頂点の局所連結性はグリッド点における有限差分近似を決定し、グリッドのサイズは常に全ての辺について1であり、いかなるグリッド点上にも制約はない。これは斉次なノイマン境界条件、すなわち自由境界の場合に相当する。

10. 有向多重グラフ
-----------

ラプラシアン行列の類似物は、有向多重グラフに対しても定義することができる。この場合、ラプラシアン行列//L//は

と定義される。上式において//D//は頂点//i//の出次数と等しい//D//を持つ対角行列、//A//は//i//から//j//への辺の数と等しい//A//を持つ行列である。

11. 出典
------

12. 参考文献
--------

B. Bollobás, //Modern Graph Theory//, Springer-Verlag , , Chapters II.3 , VIII.2 , IX.2 .

13. 関連項目
--------

剛性行列
抵抗距離
推移速度行列

14. 外部リンク
---------