查看“︁调和矩阵”︁的源代码

{{Roughtranslation|time=2020-02-17T10:41:42+00:00}}
在[[图论]]中，'''调和矩阵'''（'''harmonic matrix'''），也称'''拉普拉斯矩阵'''或'''拉氏矩阵'''（'''Laplacian matrix'''）、'''离散拉普拉斯'''（'''discrete Laplacian'''），是[[图 (数学)|图]]的[[矩阵]]表示。<ref name=":0">{{Cite mathworld|title=Laplacian Matrix|urlname=LaplacianMatrix|accessdate=2020-02-14|language=en|archive-date=2019-12-23|archive-url=https://web.archive.org/web/20191223051501/http://mathworld.wolfram.com/LaplacianMatrix.html|dead-url=no}}</ref>

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

== 定义 ==
若G是简单[[图 (数学)|图]]，G有n个[[顶点]]，A是[[邻接矩阵]]，D是[[度数矩阵]]，则'''调和矩阵'''是<ref name=":0" />

<math>L = D - A</math>

<math>L_{i,j} := \begin{cases}
  \deg(v_i) & \mbox{if}\ i = j \\
         -1 & \mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\
          0 & \mbox{otherwise}
\end{cases}</math>

=== 动机 ===
这跟拉普拉斯算子有什么关系？若f 是[[加权图]]G的顶点函数，则<ref name=":1">{{Cite web|title=Muni Sreenivas Pydi (ముని శ్రీనివాస్ పైడి)'s answer to What's the intuition behind a Laplacian matrix? I'm not so much interested in mathematical details or technical applications. I'm trying to grasp what a laplacian matrix actually represents, and what aspects of a graph it makes accessible. - Quora|url=https://www.quora.com/Whats-the-intuition-behind-a-Laplacian-matrix-Im-not-so-much-interested-in-mathematical-details-or-technical-applications-Im-trying-to-grasp-what-a-laplacian-matrix-actually-represents-and-what-aspects-of-a-graph-it-makes-accessible/answer/Muni-Sreenivas-Pydi|accessdate=2020-02-14|work=www.quora.com}}</ref>

<math>E(f) = \sum w(uv)(f(u)-f(v))^2 / 2 = f^t L f</math>

w是边的权重函数。u、v是顶点。f = (f(1), ..., f(n)) 是n维的[[矢量]]。上面[[泛函]]也称为Dirichlet泛函。<ref name=":2">{{Cite journal|title=The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains|url=http://arxiv.org/abs/1211.0053|last=Shuman|first=David I.|last2=Narang|first2=Sunil K.|date=2013-05|journal=IEEE Signal Processing Magazine|issue=3|doi=10.1109/MSP.2012.2235192|volume=30|pages=83–98|issn=1053-5888|last3=Frossard|first3=Pascal|last4=Ortega|first4=Antonio|last5=Vandergheynst|first5=Pierre|access-date=2020-02-14|archive-date=2020-01-11|archive-url=https://web.archive.org/web/20200111080302/https://arxiv.org/abs/1211.0053|dead-url=no}}</ref>

=== 接续矩阵 ===
而且若K是[[接续矩阵]]（incidence matrix），则<ref name=":1" />

<math>K_{ev} = \left\{\begin{array}{rl}
   1, & \text{if } v = i\\
  -1, & \text{if } v = j\\
   0, & \text{otherwise}.
\end{array}\right.</math>

<math>L = K^tK</math>

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

<math>\begin{align}
  \lambda_i & = \mathbf{v}_i^\textsf{T} L \mathbf{v}_i \\
            & = \mathbf{v}_i^\textsf{T} M^\textsf{T} M \mathbf{v}_i \\
            & = \left(M \mathbf{v}_i\right)^\textsf{T} \left(M \mathbf{v}_i\right) \\
\end{align}</math>

== 举例 ==
{| class="wikitable"
!图
![[度矩阵]]
![[邻接矩阵]]
!调和矩阵
|-
|[[File:6n-graf.svg|175x175像素]]
|<math display="inline">\left(\begin{array}{rrrrrr}
  2 &  0 &  0 &  0 &  0 &  0\\
  0 &  3 &  0 &  0 &  0 &  0\\
  0 &  0 &  2 &  0 &  0 &  0\\
  0 &  0 &  0 &  3 &  0 &  0\\
  0 &  0 &  0 &  0 &  3 &  0\\
  0 &  0 &  0 &  0 &  0 &  1\\
\end{array}\right)</math>
|<math display="inline">\left(\begin{array}{rrrrrr}
  0 &  1 &  0 &  0 &  1 &  0\\
  1 &  0 &  1 &  0 &  1 &  0\\
  0 &  1 &  0 &  1 &  0 &  0\\
  0 &  0 &  1 &  0 &  1 &  1\\
  1 &  1 &  0 &  1 &  0 &  0\\
  0 &  0 &  0 &  1 &  0 &  0\\
\end{array}\right)</math>
|<math display="inline">\left(\begin{array}{rrrrrr}
   2 & -1 &  0 &  0 & -1 &  0\\
  -1 &  3 & -1 &  0 & -1 &  0\\
   0 & -1 &  2 & -1 &  0 &  0\\
   0 &  0 & -1 &  3 & -1 & -1\\
  -1 & -1 &  0 & -1 &  3 &  0\\
   0 &  0 &  0 & -1 &  0 &  1\\
\end{array}\right)</math>
|}

== 其他形式 ==

=== 对称正規化调和矩阵 ===
<math>L^\text{sym} := D^{-\frac{1}{2}} L D^{-\frac{1}{2}} = I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}</math>

<math>L^\text{sym}_{i,j} := \begin{cases}
                                     1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\
  -\frac{1}{\sqrt{\deg(v_i)\deg(v_j)}} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\
                                     0 & \mbox{otherwise}.
\end{cases}</math>

注意<ref>{{cite book|last=Chung|first=Fan|authorlink=金芳蓉|title=Spectral Graph Theory|url=http://www.math.ucsd.edu/~fan/research/revised.html|origyear=1992|year=1997|publisher=American Mathematical Society|isbn=978-0821803158|access-date=2020-02-14|archive-date=2020-02-14|archive-url=https://web.archive.org/web/20200214030109/http://www.math.ucsd.edu/~fan/research/revised.html|dead-url=no}}</ref>

<math>
  \lambda \ = \ 
  \frac{\langle g, L^\text{sym}g\rangle}{\langle g, g\rangle} \ = \ 
  \frac{\left\langle g, D^{-\frac{1}{2}} L D^{-\frac{1}{2}} g\right\rangle}{\langle g, g\rangle} \ = \ 
  \frac{\langle f, Lf\rangle}{\left\langle D^\frac{1}{2} f, D^\frac{1}{2} f\right\rangle} \  = \ 
  \frac{\sum_{u \sim v}(f(u) - f(v))^2}{\sum_v f(v)^2 d_v} \ \geq \ 
  0,
</math>

=== [[随机漫步]] ===
<math>L^\text{rw} := D^{-1}L = I - D^{-1}A</math>

<math>L^\text{rw}_{i,j} := \begin{cases}
                     1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\
  -\frac{1}{\deg(v_i)} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\
                     0 & \mbox{otherwise}.
\end{cases}</math>

==[[动力学]]和[[微分方程]]==
例如，离散的[[冷却定律]]使用调和矩阵<ref>{{cite book|last=Newman|first=Mark|authorlink=マーク・ニューマン|title=Networks: An Introduction|url=https://archive.org/details/networksintroduc0000newm|year=2010|publisher=Oxford University Press|isbn=978-0199206650}}</ref>

<math>\begin{align}
  \frac{d \phi_i}{d t}
    &= -k \sum_j A_{ij} \left( \phi_i - \phi_j \right) \\
    &= -k \left( \phi_i \sum_j A_{ij} - \sum_j A_{ij} \phi_j \right) \\
    &= -k \left( \phi_i \ \deg(v_i) - \sum_j A_{ij} \phi_j \right) \\
    &= -k \sum_j \left( \delta_{ij} \ \deg(v_i) - A_{ij} \right) \phi_j \\
    &= -k \sum_j \left( \ell_{ij} \right) \phi_j.
\end{align}</math>

使用矩阵矢量

<math>\begin{align}
  \frac{d\phi}{dt} &= -k(D - A)\phi \\
                   &= -kL \phi
\end{align}</math>

<math>\frac{d \phi}{d t} + kL\phi = 0</math>

解是

<math>\begin{align}
  \frac{d\left(\sum_i c_i \mathbf{v}_i\right)}{dt} + kL\left(\sum_i c_i \mathbf{v}_i\right) &= 0 \\
                    \sum_i \left[\frac{dc_i}{dt} \mathbf{v}_i + k c_i L \mathbf{v}_i\right] &= \\
            \sum_i \left[\frac{dc_i}{dt} \mathbf{v}_i + k c_i \lambda_i \mathbf{v}_i\right] &= \\
                                                          \frac{dc_i}{dt} + k \lambda_i c_i &= 0\\
\end{align}</math>

<math>c_i(t) = c_i(0) e^{-k \lambda_i t}</math>

<math>c_i(0) = \left\langle \phi(0), \mathbf{v}_i \right\rangle </math>

=== 平衡举动 ===
当<math display="inline">\lim_{t \to \infty}\phi(t)</math>的时候，

<math>\lim_{t\to\infty} e^{-k \lambda_i t} = \left\{\begin{array}{rlr}
  0 & \text{if} & \lambda_i > 0 \\
  1 & \text{if} & \lambda_i = 0
\end{array}\right\}</math>

<math>\lim_{t\to\infty}\phi(t) = \left\langle c(0), \mathbf{v^1} \right\rangle \mathbf{v^1}</math>

<math>\mathbf{v^1} = \frac{1}{\sqrt{N}} [1, 1, ..., 1] </math>

<math>\lim_{t\to\infty}\phi_j(t) = \frac{1}{N} \sum_{i = 1}^N c_i(0) </math>

=== MATLAB代码 ===
<syntaxhighlight lang="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

</syntaxhighlight>
[[File:Graph_Laplacian_Diffusion_Example.gif|缩略图|GIF：离散拉普拉斯过程，使用拉普拉斯矩阵]]

== 应用 ==

*[[Kirchoff定理]]：调和矩阵的[[行列式]]
*[[人工智能]]
*[[非线性降维#拉普拉斯特征映射|非线性降维]]
*[[谱聚类]]
*Cheeger不等式：调和矩阵的第二大的[[特征值]]跟[[最大割問題]]有关
*图Signal processing<ref name=":2" />

== 参考文献 ==
<references group=""></references>

== 阅读 ==

* {{cite book|author=T. Sunada|chapter=Chapter 1. Analysis on combinatorial graphs. Discrete geometric analysis|title='Proceedings of Symposia in Pure Mathematics|editor=P. Exner, J. P. Keating, P. Kuchment, T. Sunada, A. Teplyaev|volume=77|year=2008|pages=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).

[[Category:代数图论]]
[[Category:图论]]