ラプラシアン行列とは - わかりやすく解説 Weblio辞書

ラプラシアン行列

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/05/08 23:24 UTC 版)

この項目では、グラフ理論で用いる行列について説明しています。微分作用素のラプラシアンについては「ラプラス作用素」をご覧ください。

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

定義

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

n個の頂点を持つ単純グラフを考えると、そのラプラシアン行列 ${\textstyle L_{n\times n}}$

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

本節では、グラフにわたって経時的に拡散する関数

{\textstyle \phi }

の例を示す。この例中のグラフは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は

L=D-A

と定義される。上式においてDは頂点iの出次数と等しいD_i,iを持つ対角行列、Aはiからjへの辺の数（ループを含む）と等しいA{{sub|i,j}]を持つ行列である。

出典

^ ^a ^b Weisstein, Eric W. "Laplacian Matrix". MathWorld (英語).
^ Godsil, C.; Royle, G. (2001). Algebraic Graph Theory, Graduate Texts in Mathematics. Springer-Verlag
^ Morbidi, F. (2013). “The Deformed Consensus Protocol”. Automatica 49 (10): 3049–3055. doi:10.1016/j.automatica.2013.07.006.
^ 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
^ Chung, Fan (1997) [1992]. Spectral Graph Theory. American Mathematical Society. ISBN 978-0821803158
^ Newman, Mark (2010). Networks: An Introduction. Oxford University Press. ISBN 978-0199206650
^ 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 .
^ 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.

参考文献

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), ISBN 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).

ラプラシアン行列とは？わかりやすく解説