ラプラシアン行列

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』

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

定義[編集]

単純グラフのラプラシアン行列[編集]

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

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

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

の要素は式

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

対称正規化ラプラシアン[編集]

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

,

として定義される[1]

の要素は

によって与えられる。

酔歩正規化ラプラシアン[編集]

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

として定義される。

の要素は

によって与えられる。

一般化ラプラシアン[編集]

一般化ラプラシアンQ

として定義される[2]

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

[編集]

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

ラベル付けされたグラフ英語版 次数行列 隣接行列 ラプラシアン行列
6n-graf.svg

性質[編集]

(無向)グラフG固有値を持つそのラプラシアン行列Lについて:

  • Lは対称である。
  • L半正定値である(すなわち全てのについて)。これは接続行列の節で検証される。これは、ラプラシアンが対称であり、優対角英語版であるという事実からも見ることができる。
  • LM-行列である(その非対角成分は非正であり、そのうえその固有値の実部は非負である)。
  • Lの全ての行の和と列の和はゼロである。実際、和の計算において、頂点の次数には隣接する頂点ごとに「−1」が足される。
  • その結果、となる。これは、ベクトルを満たすためである。これは、ラプラシアン行列が特異行列であることも暗示する。
  • グラフ中の連結成分英語版の数はラプラシアンの零空間の次元であり、0固有値の代数的多重度英語版である。
  • Lの最小の非ゼロ固有値はスペクトルギャップ英語版と呼ばれる。
  • Lの2番目に小さな固有値(ゼロかもしれない)はG代数的連結度英語版(Fiedler値)であり、グラフの最疎カットを近似する。
  • ラプラシアンは、関数Gの頂点セット、)のn次元ベクトル空間上の作用素である。
  • Gがk正則である時、正規化ラプラシアンはである(Aは隣接行列、Iは単位行列)。
  • 複数の連結成分を持つグラフについて、L区分対角行列であり、それぞれの区分はそれぞれの成分についての(場合によると頂点を順序付けし直した後の)各ラプラシアン行列である(すなわちLは区分対角行列と置換相似である)。
  • ラプラシアン行列L(トレース)はは考慮されているグラフの辺の数)と等しい。

接続行列[編集]

によって与えられる辺e(頂点ijを連結している; i > j)と頂点vについて要素Mevを持つ有向接続行列Mを定義する。

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

を満たす(M転置行列)。

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

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

変形ラプラシアン[編集]

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

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

対称正規化ラプラシアン[編集]

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

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

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

正規化ラプラシアンの全ての固有値は実数かつ非負である。これは以下のように見ることができる。は対称であるため、その固有値は実数である。これらの固有値は全て非負である。固有値λを持つの固有ベクトル を考え、を仮定する(gおよびfを頂点v上の実関数と見なすことがけいる)。すると、

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

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

実際、正規化対称ラプラシアンの固有値は0 = μ0 ≤ … ≤ μn−1 ≤ 2を満たす。これらの固有値(正規化ラプラシアンのスペクトルと呼ばれる)は、一般グラフに対するその他のグラフ不変量とよく関連する[5]

酔歩正規化ラプラシアン[編集]

酔歩(random walk)正規化ラプラシアン

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

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

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

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

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

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

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

グラフ[編集]

グラフ上の酔歩に関する余談として、単純無向グラフを考える。酔歩者が時間tに頂点iにいる確率を考え、酔歩者が時間t-1に頂点jにいた確率分布を仮定する(任意の頂点に結合したいかなる辺に沿った一歩について一様の見込みを仮定する):

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

として設定される平衡はとして定義される。)

この関係は

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

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

離散ラプラス演算子としての解釈[編集]

ラプラシアン行列は、離散ラプラス演算子英語版の特定の事例の行列表現として解釈することができる。このような解釈によって、例えば、ラプラシアン行列を無限の数の頂点と辺を持つグラフ(無限サイズのラプラシアン行列となる)の場合に一般化することが可能となる。

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

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

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

これから、

が得られる。

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

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

元の式に代入する(ここで留意すべきは、Lが対称行列であるためにその単位ノルム固有ベクトルは直交であるという事実を用いる点である):

この解

である。

前掲のように、Lの固有値は非負であり、これは微分方程式の解が(指数関数的に減衰するか一定に留まるかのいずれかのみであるため)平衡に近づくことを示している。これは、と初期条件が与えられれば、いかなる時点における解も見つけることができることも示している[6]


全体の初期条件の観点からそれぞれのに対するを探すためには、単純にを単位ノルム固有ベクトルへと射影する。

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

平衡挙動[編集]

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

となるためである。

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

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

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

となる。上式において、

である。

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

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

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

グリッド上の作用素の例[編集]

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

本節では、グラフにわたって経時的に拡散する関数の例を示す。この例中のグラフは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

負の連続的ラプラシアンに対する近似[編集]

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

有向多重グラフ[編集]

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

と定義される。上式においてDは頂点iの出次数と等しいDi,iを持つ対角行列、Aiからjへの辺の数(ループを含む)と等しいAi,jを持つ行列である。

出典[編集]

  1. ^ a b Weisstein, Eric W. "Laplacian Matrix". MathWorld(英語).
  2. ^ Godsil, C.; Royle, G. (2001). Algebraic Graph Theory, Graduate Texts in Mathematics. Springer-Verlag. 
  3. ^ Morbidi, F. (2013). “The Deformed Consensus Protocol”. Automatica 49 (10): 3049–3055. doi:10.1016/j.automatica.2013.07.006. 
  4. ^ Chung, Fan R. K. (1997). Spectral graph theory (Repr. with corr., 2. [pr.] ed.). Providence, RI: American Math. Soc.. ISBN 978-0-8218-0315-8. 
  5. ^ Chung, Fan (1997) [1992]. Spectral Graph Theory. American Mathematical Society. ISBN 978-0821803158. http://www.math.ucsd.edu/~fan/research/revised.html. 
  6. ^ Newman, Mark (2010). Networks: An Introduction. Oxford University Press. ISBN 978-0199206650. 
  7. ^ Smola, Alexander J.; Kondor, Risi (2003), “Kernels and regularization on graphs”, Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24–27, 2003, Proceedings, Lecture Notes in Computer Science, 2777, Springer, pp. 144–158, doi:10.1007/978-3-540-45167-9_12, ISBN 978-3-540-40720-1 .
  8. ^ Chaiken, S.; Kleitman, D. (1978). “Matrix Tree Theorems”. Journal of Combinatorial Theory, Series A 24 (3): 377–381. doi:10.1016/0097-3165(78)90067-5. ISSN 0097-3165. http://www.sciencedirect.com/science/article/pii/0097316578900675. 

参考文献[編集]

  • T. Sunada (2008). “Chapter 1. Analysis on combinatorial graphs. Discrete geometric analysis”. In P. Exner, J. P. Keating, P. Kuchment, T. Sunada, A. Teplyaev. 'Proceedings of Symposia in Pure Mathematics. 77. pp. 51–86. ISBN 978-0-8218-4471-7. 
  • B. Bollobás, Modern Graph Theory, Springer-Verlag (1998, corrected ed. 2013), 0-387-98488-7, Chapters II.3 (Vector Spaces and Matrices Associated with Graphs), VIII.2 (The Adjacency Matrix and the Laplacian), IX.2 (Electrical Networks and Random Walks).

関連項目[編集]

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