计算机科学 ›› 2023, Vol. 50 ›› Issue (1): 69-75.doi: 10.11896/jsjkx.211100067
刘楷文1, 黄增峰2
LIU Kaiwen1, HUANG Zengfeng2
摘要： 拉普拉斯矩阵对于无向图的研究具有重要意义,其特征值反映了图的部分结构与性质,据此可以设计有效的算法以解决图上一些相关的任务,如划分、聚类等。将拉普拉斯矩阵推广至有向图,一大难点是失去了对称性,特征值可能为复数。为了规避该问题,最近的研究引入了k次单位根作为边权,定义了复数域上的拉普拉斯矩阵,该矩阵是埃尔米特矩阵。文中提出了有向边的旋转角的概念,对该矩阵进行了推广,证明了其具有与无向图拉普拉斯矩阵类似的代数性质;给出了有向图的约束方程组和有向环路的定义,证明了拉普拉斯矩阵最小特征值为0、约束方程组有解以及图中任意有向环路旋转角为 2lπ( $l \in \mathbb{Z}$)这三者间的等价性。最后给出了一些相关推论及应用。
中图分类号:
| [1]CHUNG F R,GRAHAM F C.Spectral graph theory[M].American Mathematical Soc.,1997. [2]HOORY S,LINIAL N,WIGDERSON A.Expander graphs and their applications[J].Bulletin of the American Mathematical Society,2006,43(4):439-561. [3]LOVÁSZ L,KANNAN R.Faster mixing via average conductance[C]//Proceedings of the Thirty-first annual ACM Symposium on Theory of Computing.1999:282-287. [4]SPIELMAN D A,TENG S H.Nearly-linear time algorithms for graph partitioning,graph sparsification,and solving linear systems[C]//Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing.2004:81-90. [5]KWOK T C,LAU L C,LEE Y T,et al.Improved Cheeger's inequality:Analysis of spectral partitioning algorithms through higher order spectral gap[C]//Proceedings of the forty-fifth Annual ACM Symposium on Theory of Computing.2013:11-20. [6]MIZUTANI T.Convex programming based spectral clustering[J].Machine Learning,2021,110(5):933-964. [7]SHI J,MALIK J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905. [8]HAOCHEN J Z,WEI C,GAIDON A,et al.Provable guarantees for self-supervised deep learning with spectral contrastive loss[C]//Advances in Neural Information Processing Systems.2021. [9]CHUNG F.Laplacians and the Cheeger inequality for directed graphs[J].Annals of Combinatorics,2005,9(1):1-19. [10]LI Y,ZHANG Z L.Digraph laplacian and the degree of asymmetry[J].Internet Mathematics,2012,8(4):381-401. [11]SINGH R,CHAKRABORTY A,MANOJ B.Graph Fouriertrans-form based on directed Laplacian[C]//International Conference on Signal Processing and Communications(SPCOM).2016:1-5. [12]SEIFERT B,PÜSCHEL M.Digraph signal processing with generalized boundary conditions[J].IEEE Transactions on Signal Processing,2021,69:1422-1437. [13]LI H,SUN H,ZANETTI L.Hermitian Laplaciansand a Cheeger inequality for the Max-2-Lin problem[C]//Proceedings of the Twenty-seventh Annual European Symposium on Algorithms.2019:1-14. [14]CUCURINGU M,LI H,SUN H,et al.Hermitian matrices for clustering directed graphs:insights and applications[C]//International Conference on Artificial Intelligence and Statistics.2020:983-992. [15]LAENEN S,SUN H.Higher-Order Spectral Clustering of Directed Graphs[C]//Advances in Neural Information Processing Systems.2020:941-951. [16]TONG Z,LIANG Y,DING H,et al.Directed Graph Contrastive Learning[C]//Advances in Neural Information Processing Systems.2021. [17]BOLLOBÁS B.Modern graph theory[M].Springer Science & Business Media,2013. [18]JI S,PAN S,CAMBRIA E,et al.A survey on knowledgegraphs:Representation,acquisition,and applications[J].IEEE Transactions on Neural Networks and Learning Systems,2021,33(2):494-514. [19]SUN Z,DENG Z H,NIE J Y,et al.Rotate:Knowledge graph embedding by relational rotation in complex space[C]//International Conference on Learning Representations.2019. [20]LI Z,LIU H,ZHANG Z,et al.Learning knowledge graph embedding with heterogeneous relation attention networks[J].IEEE Transactions on Neural Networks and Learning Systems,2022,33(8):3961-3973. [21]VISHNOI N K.Laplacian solvers and their algorithmic applications[J].Theoretical Computer Science,2012,8(1/2):1-141. [22]KYNG R,LEE Y T,PENG R,et al.Sparsified cholesky andmultigrid solvers for connection laplacians[C]//Proceedings of the forty-eighth Annual ACM Symposium on Theory of Computing.2016:842-850. [23]KYNG R,SACHDEVA S.Approximate gaussian elimination for laplacians-fast,sparse,and simple[C]//IEEE fifty-seventh Annual Symposium on Foundations of Computer Science.2016:573-582. |
| [1] | 陶礼靖, 邱菡, 朱俊虎, 李航天. 面向网络安全训练评估的受训者行为描述模型 Model for the Description of Trainee Behavior for Cyber Security Exercises Assessment 计算机科学, 2022, 49(6A): 480-484. https://doi.org/10.11896/jsjkx.210800048 |
| [2] | 乔晶晶, 王莉. 基于微观行为的自适应多注意力会话推荐 Modeling User Micro-Behavior via Adaptive Multi-Attention Network for Session-based Recommendation 计算机科学, 2022, 49(11): 117-125. https://doi.org/10.11896/jsjkx.210900061 |
| [3] | 黄鑫权, 刘爱军, 梁小虎, 王桁. 基于矩阵论的一致性控制算法收敛速度分析 Matrix Theory Aided Convergence Analysis of Consensus Behavior in FANET with Beacon Loss 计算机科学, 2021, 48(6): 288-295. https://doi.org/10.11896/jsjkx.201000137 |
| [4] | 朱维军, 张春艳, 周清雷, 陈永华. 有向图k顶点导出子图的DNA粘贴算法 DNA Sticker Algorithm for k-vertex Induced Sub-graphs of Directed Graphs 计算机科学, 2019, 46(1): 309-313. https://doi.org/10.11896／j.issn.1002-137X.2019.01.048 |
| [5] | 陈冰川,陈蔼祥,吴向军,李磊. 基于数据源向图的数据库设计中数据关系的表示工具 Representation Tool of Data Relations in Database Design Based on Data Source-target Digraph 计算机科学, 2017, 44(Z6): 470-474. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.105 |
| [6] | 徐喜荣,黄亚真,张思佳,董学智. 广义Kautz有向图GK(3,n)的反馈数的界 Feedback Numbers of Generalized Kautz Digraphs GK(3,n) 计算机科学, 2016, 43(5): 13-21. https://doi.org/10.11896/j.issn.1002-137X.2016.05.003 |
| [7] | 陈秋茹,文中华,袁润,戴良伟. 利用有向环的性质求解可达关系 Solving Reachability Relationship by Property of Directed Cycle 计算机科学, 2016, 43(4): 202-205. https://doi.org/10.11896/j.issn.1002-137X.2016.04.041 |
| [8] | 李健利,王艺谋,谢悦,丁洪骞. 一种基于多样化历史信息的自动信任协商策略 Automated Trust Negotiation Based on Diverse History Information 计算机科学, 2016, 43(3): 122-126. https://doi.org/10.11896/j.issn.1002-137X.2016.03.025 |
| [9] | 栗青生,张 莉,刘 泉,熊 晶,杨新新. 一种基于云端信息保护的汉字计算模型 Chinese Character Computing Model Based on Cloud Information Protection 计算机科学, 2015, 42(11): 73-79. https://doi.org/10.11896/j.issn.1002-137X.2015.11.015 |
| [10] | 师海忠,师越. (V,R)-语言 (V,R)-Languages 计算机科学, 2014, 41(Z6): 33-36. |
| [11] | 师越,师海忠. 自然语言是正则语言 Natural Languages Are Regular Languages 计算机科学, 2014, 41(Z11): 51-54. |
| [12] | 崔宾阁,孟翱翔. 基于最近邻有向图的遥感图像快速分割算法 Fast Remote Sensing Image Segmentation Algorithm Based on Nearest Neighbor Direct Graph 计算机科学, 2013, 40(10): 274-278. |
| [13] | 史卫亚，郭跃飞. 大规模数据集下谱聚类算法的求解 Computation of Spectral Clustering Algorithm for Large-scale Data Set 计算机科学, 2012, 39(Z6): 312-314. |
| [14] | 陈科，谢明霞，成毅. 空间信息服务链模型的有向图表示及其验证 Geo-serviceChain Model Expression by Directed Graph and Verification 计算机科学, 2012, 39(10): 240-244. |
| [15] | 廖巍,吴晓平,严承华,钟志农. 一种新的道路网络连续查询处理方法 Novel Method for Continuous Queries Processing in Road Networks 计算机科学, 2009, 36(9): 151-153. |
|
||
首页