关键词: 有向图聚类, 非负矩阵分解, 核方法, 正则化, 节点相似性

Abstract: Abstract: Most existing directed-graph clustering algorithms were based on the assumption that the relationship between nodes can be approximated linearly in the vector space, which was inadequate to discover the underlying non-linear correlations within nodes. To address this problem, a directed-graph clustering algorithm based on kernel nonnegative matrix factorization was proposed. First, the adjacency matrix of a directed graph was projected to the kernel space using a kernel learning method, with the node similarity in both the original and projected spaces constrained by a newly defined regularizer. Second, a new objective function was proposed for our regularized kernel asymmetric nonnegative matrix factorization algorithm, based on the gradient decent method with the nonnegative constraints. The new algorithm modeled the nonlinear relationship between nodes while distinguishing the directivity of the edges by kernel learning, which was able to accurately reveal the underlying structure in the directed graphs. Finally, experiments were conducted on real networks and synthesis networks, and the results show that the proposed algorithm can cluster directed networks effectively and obtain superior performance than the competing algorithms in terms of a few cluster validity indices.

Key words: Directed graph clustering, non-negative matrix factorization, kernel learning method, regularization, node similarity