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

来源：电子与信息学报杂志2015年第9期北京时间：

作者：汪涛, 刘阳, 席耀一

单位：解放军信息工程大学信息系统工程学院 郑州 450002

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

关键词：二分网络, 社区发现, 图正则化, 非负矩阵分解

基金资助：国家863计划项目(2011AA013603)和国家重大科技专项(2013ZX 03006002)