有向图的埃尔米特拉普拉斯矩阵研究

作     者：刘楷文 黄增峰 LIU Kaiwen;HUANG Zengfeng

作者机构：复旦大学计算机科学技术学院上海200433 复旦大学大数据学院上海200433 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2023年第50卷第1期

页      码：69-75页

摘      要：拉普拉斯矩阵对于无向图的研究具有重要意义,其特征值反映了图的部分结构与性质,据此可以设计有效的算法以解决图上一些相关的任务,如划分、聚类等。将拉普拉斯矩阵推广至有向图,一大难点是失去了对称性,特征值可能为复数。为了规避该问题,最近的研究引入了k次单位根作为边权,定义了复数域上的拉普拉斯矩阵,该矩阵是埃尔米特矩阵。文中提出了有向边的旋转角的概念,对该矩阵进行了推广,证明了其具有与无向图拉普拉斯矩阵类似的代数性质;给出了有向图的约束方程组和有向环路的定义,证明了拉普拉斯矩阵最小特征值为0、约束方程组有解以及图中任意有向环路旋转角为2lπ(l∈Z)这三者间的等价性。最后给出了一些相关推论及应用。

主 题 词：谱方法 有向图 埃尔米特拉普拉斯矩阵 有向环路 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.11896/jsjkx.211100067

馆 藏 号：203116955...