图论|拉普拉斯矩阵

写在前面：欢迎关注微信公众号：亿笔记。分享药物设计、人工智能和计算机等方面知识~~

说明：本文并非全部为本人原创，是参考了诸多资料之后整理的有关拉普拉斯方面的知识。参考资料如参考资料中所示。

拉普拉斯算子与拉普拉斯矩阵

(1) 拉普拉斯矩阵是一种用于表示图的矩阵。拉普拉斯矩阵就是图上的拉普拉斯算子。
(2) 数学语言来讲，如果是欧式空间中的二阶可微实函数，那么就是在欧式空间中求其二阶微分（散度）。如果是图上定义的一组高维向量，那么就是在图空间中求其二阶微分（散度）。

拉普拉斯算子含义

梯度

(1) 如下例所示，对于一个二维输入的函数，函数可视化如下图所示：

其中箭头即是此二维输入函数在每个点处的梯度在二维平面中的投射。
(2) 用数学语言表示即函数f(x,y)在(x,y)处的一阶连续偏导数向量表示的就是该函数在该点处的梯度，记作。
(3) 梯度的物理意义即欧式空间函数在某一点处的梯度就是该函数在该点变化率最大的方向。

拉普拉斯算子

(1) 拉普拉斯算子是在N维欧氏空间中的一个二阶微分算子，定义为梯度的散度，即二阶导数。另一角度，拉普拉斯算子计算了周围点与中心点的梯度差，拉普拉斯算子计算得到的是对该点进行微小扰动后可能获得的总变化。
(2) 用数学语言表示为：

(3) 如下图所示：

，表示该点是有散发通量的正源（发散源）。如图中的蓝圈，即散度大于0，该点是一个极值点，并且是极小值。
，表示该点是有吸收通量的负源（汇聚源）。如图中的红圈，即散度小于0，该点是一个极值点，并且是极大值。
，表示该点无源。

梯度与拉普拉斯算子

(1) 梯度反映了函数的极值情况。
(2) 拉普拉斯算子（梯度的散度）则反映了函数的极值是极大值还是极小值。

图上的拉普拉斯矩阵

图的拉普拉斯矩阵计算公式

(1) 如下图所示，给定一个有n个顶点的图G=(V,E)，其拉普拉斯矩阵被定义为L=D-A，D其中为图的度矩阵，A为图的邻接矩阵。

(2) 该图的邻接矩阵A如下所示，邻接矩阵也就是权重矩阵W：

(3) 把W的每一列元素加起来得到N个数，然后把它们放在对角线上（其它地方都是零），组成一个N×N的对角矩阵，记为度矩阵D，如下所示。

(4) 则拉普拉斯矩阵L=D-A，即为：

图的拉普拉斯矩阵含义及公式推导

(1) 如上具有N个节点的图G所示，用函数表示该图，则。其中是函数在节点处的函数值。类似于在节点处的值。对节点进行扰动，它可能变为任意一个与它相邻的节点，表示节点的一阶邻域节点。
(2) 拉普拉斯算子可以计算一个点到它所有自由度上微小扰动的增益，若用图来表示即是任意一个节点变化到节点所带来的增益，则有：

两个节点不相邻时，则上式可简化为：

其中是顶点的度，是N维行向量，代表顶点与其他节点间的权重关系；是N维列向量，是每个节点自身的特征向量；是两个向量的内积。
(3) 对于具有N个节点的一张图，则有：

(4) 拉普拉斯矩阵中的第行反应了第个节点在对其他所有节点产生扰动时所产生的增益累积。图拉普拉斯反映了当我们在节点上施加一个势，这个势以哪个方向能够多顺畅的流向其他节点。

参考资料

分类：

数学

标签：

数学基础

作者介绍