基于核非负矩阵分解的有向图聚类算法

现有的有向图聚类算法大多基于向量空间中节点间的近似线性关系假设，忽略了节点间存在的非线性相关性。针对该问题，提出一种基于核非负矩阵分解（KNMF）的有向图聚类算法。首先，引入核学习方法将有向图的邻接矩阵投影到核空间，并通过特定的正则项约束原空间及核空间中节点间的相似性。其次，提出了图正则化核非对称NMF算法的目标函数，并在非负约束条件下通过梯度下降方法推导出一个聚类算法。该算法在考虑节点连边的方向性的同时利用核学习方法建模节点间的非线性关系，从而准确地揭示有向图中潜在的结构信息。最后，在专利-引文网络（PCN）数据集上的实验结果表明，簇的数目为2时，和对比算法相比，所提算法将DB值和DQF值分别提高了约0.25和8%，取得了更好的聚类质量。

Directed graph clustering algorithm based on kernel nonnegative matrix factorization

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.