调和矩阵

在图论中，调和矩阵（harmonic matrix），也称拉普拉斯矩阵或拉氏矩阵（Laplacian matrix）、离散拉普拉斯（discrete Laplacian），是图的矩阵表示。

调和矩阵也是拉普拉斯算子的离散化。换句话说，调和矩阵的缩放极限是拉普拉斯算子。它在机器学习和物理学中有很多应用。

 定义 
若G是简单图，G有n个顶点，A是邻接矩阵，D是度数矩阵，则调和矩阵是

 动机 
这跟拉普拉斯算子有什么关系？若f 是加权图G的顶点函数，则

w是边的权重函数。u、v是顶点。f = (f(1), ..., f(n)) 是n维的矢量。上面泛函也称为Dirichlet泛函。

 接续矩阵 
而且若K是接续矩阵（incidence matrix），则

Kf 是f 的图梯度。另外，特征值满足

 举例 
图度矩阵邻接矩阵调和矩阵175x175像素

 其他形式 

 对称正規化调和矩阵 

注意

 随机漫步 

动力学和微分方程
例如，离散的冷却定律使用调和矩阵

使用矩阵矢量

解是

 平衡举动 
当的时候，

 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
缩略图|GIF：离散拉普拉斯过程，使用拉普拉斯矩阵

 应用 

Kirchoff定理：调和矩阵的行列式
人工智能
非线性降维
谱聚类
Cheeger不等式：调和矩阵的第二大的特征值跟最大割問題有关
图Signal processing

 参考文献 

 阅读 


 B. Bollobás, Modern Graph Theory, Springer-Verlag (1998, corrected ed. 2013), , 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).

Category:代数图论
Category:图论