基于图正则化非负矩阵分解的二分网络社区发现算法

Identifying Community in Bipartite Networks Using Graph Regularized-based Non-negative Matrix Factorization

现实世界存在大量二分网络,研究其社区结构有助于从新角度认识和理解异质复杂网络。非负矩阵分解模型能够克服二分结构的限制,有效地挖掘二分网络的潜在结构,但也存在着时间复杂度高、收敛慢等问题。该文提出一种基于图正则化的三重非负矩阵分解(NMTF)算法应用于二分网络社区发现,通过图正则化将用户子空间和目标子空间的内部连接关系作为约束项引入到三重非负矩阵分解模型中;同时将NMTF分解为两个最小化近似误差的子问题,并给出了乘性迭代算法以交替更新因子矩阵,从而简化矩阵分解迭代,加快收敛速度。实验和分析证明:对于计算机生成网络和真实网络,该文提出的社区划分方法均表现出较高的准确率和稳定性,能够快速准确地挖掘二分网络的社区结构。

There are many bipartite networks composed of two types of nodes in the real world, studying the community structure of them is helpful to understand the complex network from a new point of view. Nonnegative matrix factorization can overcome the limitation of the two-mode structure of bipartite networks, but it is also subject to several problems such as slow convergence and large computation. In this paper, a novel algorithm using graph regularized-based non-negative matrix factorization is presented for community detection in bipartite networks. It respectively introduces the internal connecting information of two-kinds of nodes into the Nonnegative Matrix Tri-Factorization（NMTF） model as the graph regularizations. Moreover, this paper divides NMTF into two sub problems of minimizing the approximation error, and presents an alternative iterative algorithm to update the factor matrices, thus the iterations of matrix factorization can be simplified and accelerated. Through the experiments on both computer-generated and real-world networks, the results and analysis show that the proposed method has superior performances than the typical community algorithms in terms of the accuracy and stability, and can effectively discover the meaningful community structures in bipartite networks.