摘要
现有的有向图聚类算法大多基于向量空间中节点间的近似线性关系假设,忽略了节点间存在的非线性相关性。针对该问题,提出一种基于核非负矩阵分解(KNMF)的有向图聚类算法。首先,引入核学习方法将有向图的邻接矩阵投影到核空间,并通过特定的正则项约束原空间及核空间中节点间的相似性。其次,提出了图正则化核非对称NMF算法的目标函数,并在非负约束条件下通过梯度下降方法推导出一个聚类算法。该算法在考虑节点连边的方向性的同时利用核学习方法建模节点间的非线性关系,从而准确地揭示有向图中潜在的结构信息。最后,在专利-引文网络(PCN)数据集上的实验结果表明,簇的数目为2时,和对比算法相比,所提算法将DB值和DQF值分别提高了约0.25和8%,取得了更好的聚类质量。
Most of the existing directed graph clustering algorithms are based on the assumption of approximate linear relationship between nodes in vector space,ignoring the existence of non-linear correlation between nodes.To address this problem,a directed graph clustering algorithm based on Kernel Nonnegative Matrix Factorization(KNMF)was proposed.First,the adjacency matrix of a directed graph was projected to the kernel space by using a kernel learning method,and the node similarity in both the original and kernel spaces was constrained by a specific regularization term.Second,the objective function of graph regularization kernel asymmetric NMF algorithm was proposed,and a clustering algorithm was derived by gradient descent method under the non-negative constraints.The algorithm accurately reveals the potential structural information in the directed graph by modeling the non-linear relationship between nodes using kernel learning method,as well as considering the directivity of the links of nodes.Finally,experimental results on the Patent Citation Network(PCN)dataset show that compared with the comparison algorithm,when the number of clusters is 2,the proposed algorithm improves the Davies-Bouldin(DB)and Distance-based Quality Function(DQF)by about 0.25 and 8%respectively,achieving better clustering quality.
作者
陈献
胡丽莹
林晓炜
陈黎飞
CHEN Xian;HU Liying;LIN Xiaowei;CHEN Lifei(College of Computer and Cyber Security,Fujian Normal University,Fuzhou Fujian 350117,China;Digit Fujian Internet-of-Things Laboratory of Environmental Monitoring(Fujian Normal University),Fuzhou Fujian 350117,China;Center for Applied Mathematics of Fujian Province(Fujian Normal University),Fuzhou Fujian 350117,China)
出处
《计算机应用》
CSCD
北大核心
2021年第12期3447-3454,共8页
journal of Computer Applications
基金
国家自然科学基金资助项目(U1805263)
福建省自然科学基金资助项目(2018J01775)。
关键词
有向图聚类
核非负矩阵分解
核学习方法
正则化
节点相似性
directed graph clustering
Kernel Nonnegative Matrix Factorization(KNMF)
kernel learning method
regularization
node similarity
