
亿笔记
2022/03/20阅读:101主题:默认主题
图论|拉普拉斯矩阵
图论|拉普拉斯矩阵
写在前面:欢迎关注微信公众号:亿笔记。分享药物设计、人工智能和计算机等方面知识~~

说明:本文并非全部为本人原创,是参考了诸多资料之后整理的有关拉普拉斯方面的知识。参考资料如参考资料中所示。
拉普拉斯算子与拉普拉斯矩阵
(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) 拉普拉斯算子可以计算一个点到它所有自由度上微小扰动的增益,若用图来表示即是任意一个节点
两个节点不相邻时
其中
(3) 对于具有N个节点的一张图,则有:
(4) 拉普拉斯矩阵中的第
参考资料
分类:
数学标签:
数学基础作者介绍
