打开文本图片集
摘要：针对重叠社区中的重要节点（重叠节点、中心节点、离群节点）及其固有的重叠社区结构的发现问题，提出了一种新的对称非负矩阵分解算法。首先将误差逼近项和非对称惩罚项的和作为目标函数，然后基于梯度更新的原则及非负约束条件推导出该算法。对5个实际网络进行了仿真实验，结果显示所提算法能将实际网络的重要节点及其固有的社区结构发现出来。从社区发现结果的平均导电率和算法的执行时间看，所提方法优于非负矩阵分解社区发现（CDNMF）方法；从准确率和召回率的调和平均值的加权平均值看，所提方法比较适合较大数据集的重叠社区发现。
关键词：复杂网络；重叠社区；社区发现；对称非负矩阵分解；邻接矩阵
中图分类号： TP301.6
文献标志码：A
Abstract： In view of the important nodes （including overlapping nodes， central nodes and outlier nodes） in overlapping community and the inherent overlapping community structure discovery problem， a new symmetric nonnegative matrix factorization algorithm was proposed. First， the sum of the error approximation and the asymmetric penalty term was used as the objective function. Then the algorithm was derived by using the principle of gradient update and the nonnegative constraint conditions. Simulation experiments were carried out on five real networks. The results show that the proposed algorithm can find the important nodes of the actual networks and their inherent community structures. The average conductance and the algorithms execution time of the community discovery results are better than those of Community Detection with Nonnegative Matrix Factorization （CDNMF） method； the weighted average of the accuracy and recall rates harmonic mean value shows that the proposed method is more suitable for the large databases.
Key words： complex network； overlapping community； community discovery； symmetric nonnegative matrix factorization； adjacency matrix
0引言
很多系统以复杂网络的形式存在，网络中的节点表示复杂系统中的个体，边则表示个体之间的关系[1]，如社会关系网络[2-4]、生物网络[5-6]、技术网络[7]等。近年来，复杂网络的研究成了很多应用领域的研究热点。其中社区结构是复杂网络中一个很普遍的特征，整个网络由多个社区组成，同一社区内的节点间连接比较紧密，而不同社区节点间的连接比较稀疏。当前学术界对网络中节点的社区属性假设可分为两大类[8]：1）网络中每个节点仅属于单一社区，即非重叠社区。非重叠社区发现方法假设网络中每个节点仅属于单一社区。对于社区内部节点，这一假设是合理的，而对于社区边界节点则不然，它们可能同时属于多个社区。2）网络中每个节点可同时属于多个社区，即重叠社区。重叠社区发现方法假设网络中每个节点同时属于多个社区，这符合真实网络的实际社区结构。
关于非重叠社区发现方法已经有很多种，如基于模块度函数优化的社区发现方法[9-10]、基于概率模型的社区发现方法[11-12]、基于聚类算法的社区发现方法[13-14]、基于生物智能算法的社区发现方法[15-16]等。对于真实网络中常见的重叠社区结构，因为这些重叠节点在不同社区之间起着桥梁作用，在社区中发挥着重要作用，于是，重叠社区发现成了近年来研究的热点。最早的重叠社区发现算法是Palla等[17]提出的基于完全子图的派系过滤算法，很快，不少研究者对派系过滤算法进行改进，如Kumpula等[18] 在派系过滤算法基础上提出了一种快速团渗透算法，Farkas等[19]对派系过滤算法进行扩展，使得可以针对有向网络和加权网络的重叠社区发现，等等。
非负矩阵分解（Nonnegative Matrix Factorization， NMF）是机器学习中一种特征提取和降维的方法，近年来被用于社区发现。如Wang等[20]提出了将非负矩阵分解分别用于无向网络、有向网络和混合网络的社区发现，但没考虑重叠社区发现问题； Psorakis等[21]基于传统的NMF模型可按一定的方法进行重叠社区的发现，但分解后的非负矩阵因子的元素不能直接解释为各节点属于某个社区的标识，要结合其他聚类算法才能划分社区；Zhang等[22]基于带约束的NMF能对有向网络和无向网络进行重叠社区的发现；