加权拉普拉斯方法及其理论应用.docx
版权申诉
21 浏览量
2022-12-01
09:10:42
上传
评论
收藏 100KB DOCX 举报
1. 引言
偏微分方程(PDE)在图分析领域已被广泛研究，并且已经逐渐发展成为一套强有力的
框架来帮助我们更好地理解发生在图上的一些现象.作为很多二阶偏微分方程(拉普拉斯方
程，泊松方程，演化方程)的核心算子，拉普拉斯算子在图分析领域已经产生了很多强大的
理论工具.像这一类能够处理图问题的拉普拉斯算子统一被称为图拉普拉斯(graph
Laplacian).
作为图拉普拉斯的一个成功的应用，谱图理论在聚类问题中已经演化成了一类非常有
用的技术工具，并在过去几十年内得到了系统地发展
[1]
.一般认为，谱图理论最初是从图上
的最小割问题中建立出来的，另外一个创建该理论的动机可能来自于图能量问题，其中图
划分的“割”被看成是划分的能量.由于在图分析领域中的大部分应用是基于离散化方法的，
因此我们就可以充分利用基于图拉普拉斯的谱方法来最小化一些特定的图分割的目标函
数，比如比率割(ratio cut)
[2]
，归一化割(normalized cut)
[3]
.
考虑到绝大多数现有的图拉普拉斯都是基于顶点加权图或者边加权图上的，由这些图
拉普拉斯发展而来的技术在遇到一些更复杂情况时，应用比较受到局限.由于双重加权图在
处理最近一些尚未解决的重要问题时具有很大的潜能，受到现有的图拉普拉斯理论的启
发，本文提出了一种新的加权拉普拉斯方法，使得拉普拉斯算子能够适用于双重加权图，
从而进一步扩展了图拉普拉斯的实际应用范围.为了进一步说明提出的加权图拉普拉斯方法
的优势以及它广泛的潜在应用，本文将给出两个该方法的理论应用，分别是多层图分割问
题的聚类算法设计以及平衡最小割问题.
2. 相关工作
2.1 图拉普拉斯与平衡最小割问题
谱图理论和谱方法在过去的几十年内得到了系统发展.图拉普拉斯是大多数谱方法的核
心.在一些相关文献中，有很多不同的基于边加权图的拉普拉斯，例如，非归一化的拉普拉
斯 L:=D－W，正则化的拉普拉斯 L
N
:=I－D
－1/2
WD
－1/2
, 以及随机游走拉普拉斯 L
rw
:=I－D
－1
W,
其中，W={W
ij
}，D=diag{d
i
}分别是图的权值矩阵以及度矩阵.
在最近几年的工作中，平衡最小割问题
[4]
在很多实际应用场合中也扮演着很重要的角
色.目前有很多方法可以用来定义一系列的平衡条件，这些平衡条件在平衡最小割问题中是
作为优化问题中一类约束条件的.
2.2 多层图分割
罗伯特之技术屋
- 粉丝: 3907
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
VIP享7折，此内容立减5.97元 开通VIP
相关推荐
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0
最新资源