基于改进对称二值非负矩阵分解的重叠社区发现方法

针对复杂网络社区结构具有重叠性的问题，目前已提出许多不同类型的解决方法，其中基于对称二值非负矩阵分解（SBNMF）的重叠社区发现方法是具有代表性的方法。然而，SBNMF在面对社区内部链接稀疏的网络时，其重叠社区发现性能低下，为此提出一种基于改进SBNMF（ISBNMF）的重叠社区发现方法。首先利用对称非负矩阵分解得到的因子矩阵构建社区内部链接稠密的新网络，然后再使用基于Frobenius范数的SBNMF模型对新网络的邻接矩阵进行分解，最后通过网格搜索法或梯度下降法得到可以显式指示节点的社区隶属关系的二值矩阵。在人工合成的和真实的网络数据集上进行大量实验，结果表明ISBNMF的社区发现性能优于SBNMF和其他代表性方法。     

基于对称非负矩阵分解的重叠社区发现方法

针对重叠社区中的重要节点(重叠节点、中心节点、离群节点)及其固有的重叠社区结构的发现问题,提出了一种新的对称非负矩阵分解算法。首先将误差逼近项和非对称惩罚项的和作为目标函数,然后基于梯度更新的原则及非负约束条件推导出该算法。对5个实际网络进行了仿真实验,结果显示所提算法能将实际网络的重要节点及其固有的社区结构发现出来。从社区发现结果的平均导电率和算法的执行时间看,所提方法优于非负矩阵分解社区发现(CDNMF)方法;从准确率和召回率的调和平均值的加权平均值看,所提方法比较适合较大数据集的重叠社区发现。     

基于迭代框架的主动链接选择半监督社区发现算法

针对非负矩阵分解（NMF）半监督社区发现方法随机选择先验约束,导致提升相同性能需要更多约束信息的问题,提出一种基于迭代框架的主动链接选择半监督社区发现算法——ALS_GNMF。在迭代框架下,首先,主动选择不确定性高且对社区划分指导性强的链接对作为先验信息;其次,为主动选择的链接对增加must-link约束,增强社区间连接,生成先验矩阵;同时,增加cannot-link约束,减弱社区间连接,修改邻接矩阵;最后,将先验矩阵作为正则项,加入基于NMF的最优化目标函数,并融合网络拓扑结构信息,以期用较少的先验信息,达到较高的社区发现准确性和鲁棒性。实验结果表明,ALS_GNMF算法在真实网络及人工网络上,相同的先验比例下,性能比未采用迭代框架和主动策略的NMF半监督社区发现方法有更大的提升,且在结构不清晰的网络中表现稳定。     

基于链接模型的主动半监督社区发现方法

链接模型可对网络的社区发现问题建模,相比具有相同目标的对称模型和条件模型,PPL模型处理网络类型更多、社区发现准确率更高。但PPL模型是一个无监督模型,在网络社区结构不清晰时效果不佳,且不能利用易获取的先验信息。为使用尽可能少的先验,获得社区发现链接模型性能较大的提升,提出了一个主动节点先验学习（ANPL）算法,该算法主动选择效用高、易标记的成对约束进行标记,基于标记的约束对自动生成信息量更大的标记节点集合。基于PPL模型设计了一个融合网络拓扑结构和标记节点先验的半监督社区发现（SPPL）模型,并给出模型用于半监督社区发现的参数估计算法。人工网络和实际网络上的实验结果表明,利用ANPL获得的标记节点先验和网络拓扑结构,SPPL模型的社区发现准确率高于无监督PPL模型及当前流行的基于非负矩阵分解（NMF）的半监督社区发现模型。     

一种结合小世界模型改良的NMF社区发现算法

社区发现是当前复杂网络与数据挖掘的热点,非负矩阵分解是社区发现的常用手段。针对当前非负矩阵分解的社区发现算法,为提高算法的准确率与可解释性,提出多阶邻居节点的概念,在小世界模型的基础上构建了规模可控的多阶复合信息矩阵,用后处理的方法减少了算法中随机因素带来的不稳定性。对于真实网络与人工网络的实验证明,新背景下的算法较原算法在性能上有一定的提升。     

基于聚类信息和对称非负矩阵分解的链路预测模型研究

现有的大部分基于非负矩阵分解的链路预测方法仅考虑网络拓扑结构信息而忽略节点与链接聚类信息.针对此问题,提出一个融合聚类信息的对称非负矩阵分解的链路预测模型.首先,该模型利用对称非负矩阵分解去捕获网络节点相似度信息;其次,使用基于Jaccard的节点和链接聚类系数去保持网络局部结构信息;最后,启用拉格朗日乘法规则去学习模型参数.在六个真实无向无权和四个加权网络上的实验结果表明,该方法在两种不同类型网络预测精确度分别提升了1.6％和8.9％.     

改进的Gabor变换和二维NMF融合的人脸识别

为了得到高质量的人脸特征,提高人脸识别性能,提出基于改进的Gabor变换和（2D）2NMF（二维非负矩阵分解法）的人脸识别方法。改进的Gabor变换提取的特征有较高的品质,鲁棒性增强。二维非负矩阵分解法降维能大大降低图像数据维数,缩短计算时间,提高识别率。最后在ORL人脸库中进行实验,结果表明改进的Gabor变换和二维NMF方法相结合计算时间略微增加,但识别效率明显提高,从而证明了该方法的有效性。     

基于非负矩阵分解的人脸识别算法的改进

非负矩阵分解方法是基于局部特征的特征提取方法，已经成功用于人脸识别。研究基于非负矩阵分解的人脸图像识别的改进算法是一个有重要意义的研究课题。采用二维非负矩阵分解方法（2DNMF）和对角非负矩阵分解方法（DiaNMF），并且使用正交的基矩阵进行Matlab实验。实验结果表明，以上改进措施能够有效提高人脸图像识别的正确率。     

基于矩阵分解的属性网络嵌入和社区发现算法

属性网络不但包含节点之间复杂的拓扑结构,还包含拥有丰富属性信息的节点,其可以比传统网络更有效地建模现代信息系统,属性网络的社区划分对于分析复杂系统的层次结构、控制信息在网络中的传播和预测网络用户的群体行为等方面具有重要的研究价值.为了更好地利用拓扑结构信息和属性信息进行社区发现,提出了一种基于矩阵分解的属性网络嵌入和社区发现算法(CDEMF).首先提出基于矩阵分解的属性网络嵌入方法,基于网络局部链接信息计算相邻节点的相似性,将其与属性接近度联合建模,通过矩阵分解的分布式算法得到每个节点对应的低维嵌入向量,即把网络节点映射为低维向量表示的数据点集合.接着提出基于曲率和模块度的社区划分方法,自动确定数据点集合中蕴含的社区数量,并通过对数据点集合聚类完成属性网络社区划分.在真实网络数据集上,将CDEMF方法与其他8种知名算法进行比较,实验结果表明CDEMF具有良好的性能.     

基于Hessian正则化的多视图联合非负矩阵分解算法

非负矩阵在表征多视图数据时没有考虑数据本身的流型结构,不能有效表达数据内部信息。为此,提出一种基于Hessian正则化的非负矩阵分解算法。利用Hessian泛函的L2模,保持样本局部拓扑结构,并扩展成基于Hessian正则化的联合非负矩阵分解算法,以对多视图数据进行变换。实验结果表明,基于Hessian正则化的非负矩阵分解算法和基于Hessian正则化的联合非负矩阵分解算法的聚类精度以及互信息值都有较大提高,2种算法的数据变化性能都优于传统非负矩阵分解算法。     

一种面向语义重叠社区发现的Link-Block算法

语义社会网络是一种由信息节点及社会关系构成的新型复杂网络,传统语义社会网络分析算法在进行社区挖掘时需要预先设定社区个数,且无法发现重叠社区.针对这一问题,提出一种面向语义社区发现的link-block算法.该算法首先以LDA模型为语义信息模型,创新性地建立了以link为核心的block区域LBT(link-block-topic)取样模型;其次,根据link-block语义分析结果,建立可度量link-block区域的语义链接权重方法,实现了语义信息的可度量化;最后,根据语义链接权重建立了以link-block为单位的聚类算法以及可评价语义社区的SQ模型,并通过实验分析,验证了该算法及SQ模型的有效性及可行性.     

LinkLPA: A Link‐Based Label Propagation Algorithm for Overlapping Community Detection in Networks

Community detection is an important methodology for understanding the intrinsic structure and function of complex networks. Because overlapping community is one of the characteristics of real‐world networks and should be considered for community detection, in this article, we propose an algorithm, called link‐based label propagation algorithm (LinkLPA), to detect overlapping communities. Because the link partition is conceptually natural for the problem of overlapping community detection, LinkLPA first transforms node partition problem into link partition problem and employs a new label propagation algorithm with preference on links instead of nodes to detect communities due to the simplicity and efficiency of label propagation algorithm. Then the proposed LinkLPA performs a postprocessing to refine the detected overlapping communities by avoiding over‐overlapping and incorrect partition of weak ties. Experimental results on a large number of real‐world and synthetic networks show that the proposed method achieves high accuracy on detecting overlapping communities in networks.     

一种基于局部扩展优化的重叠社区发现算法

挖掘复杂网络的重叠社区结构对研究复杂系统具有重要的理论和实践意义。提出一种基于局部扩展优化的重叠社区识别算法。 首先基于网络节点的聚集系数筛选种子节点,选取不相关的、局部聚集系数大的种子作为初始社区;然后采用贪心策略扩展初始社区,得到局部连接紧密的自然社区;最后检测并合并相似的社区,获得高覆盖率的重叠社区结构。在人工生成网络和真实网络数据集上的实验结果表明,与现有的基于局部扩展的代表性重叠社区发现算法相比,所提算法能在稀疏程度不同的网络上发现更高质量的重叠社区。     

一种基于粗糙集和密度峰值的重叠社区发现方法

随着互联网和社会的发展,各个领域每天都会产生大量相互关联、彼此依赖的数据,这些数据根据不同的主题形成了各种复杂网络。挖掘社区结构是复杂网络领域中的一项重要研究内容,因为其在推荐系统、行为预测和信息传播等方面具有极其重要的意义。社区结构中的重叠社区结构在生活中普遍存在,更具有实际研究意义。为有效发现复杂网络中的重叠社区,文中引入了粗糙集理论对社区进行分析,识别出重叠节点,进而提出了一种基于粗糙集和密度峰值的重叠社区发现方法OCDRD(Overlapping Community Detection Algorithm Based on Rough Sets and Density Peaks)。该方法在传统网络节点局部相似性度量的基础上,结合灰色关联分析方法求出网络节点间的全局相似性,进而将其转化为节点间距离。将密度峰值聚类算法的思想应用于该算法中,以根据网络结构自动选取社区中心节点。依据网络中节点的距离比例关系,定义了社区的上近似、下近似以及边界域。最后,不断调整距离比率阈值并进行划分迭代,在每次迭代中针对社区的边界域进行计算,从而获得最佳重叠社区划分结构。在LFR基准人工网络数据集和真实网络数据集上,基于标准互信息(Normalized Mutual Information,NMI)和具有重叠性模块度EQ这两个评价指标,将OCDRD方法与近几年效果较好的其他社区发现算法进行测试比较。实验结果显示,OCDRD方法在社区划分结构方面整体优于其他社区发现算法,表明了该算法的可行性和有效性。     

结合拓扑势与信任度调整的重叠社区发现算法

现实世界中的复杂系统可建模为复杂网络,探究复杂网络中的社区发现算法对于分析复杂网络的拓扑结构和层次结构具有重要作用。早期研究通常将网络中的节点局限在一个社区中,但随着研究的深入发现社区结构呈现重叠特性。针对现有重叠社区发现算法存在划分社区结构不稳定、忽略节点交互和属性等问题,提出一种基于网络拓扑势与信任度调整的重叠社区发现算法。融合节点的属性和结构特征计算节点的拓扑势,依据节点的拓扑势选取核心节点。从核心节点出发构建初始社区群,计算各个社区间的调整信任度,实现社区的合并与再调整,从而识别重叠社区。在多个人工模拟网络和真实网络数据集上的实验结果表明,与基于贪婪派系扩张、种子扩张等的重叠社区发现算法相比,该算法将扩展模块度最高提升至0.719,能有效识别社区结构及重叠节点,提升重叠社区检测性能。     

复杂网络大数据中重叠社区检测算法

大数据时代互联网用户数量呈爆炸性增长,社交网络、电商交易网络等复杂网络规模快速发展,准确有效地检测复杂网络大数据中重叠社区结构对用户兴趣点推荐和热点传播具有重要意义。提出一种新的面向复杂网络大数据的重叠社区检测算法DOC（Detecting Overlapping Communities over complex network big data）,时间复杂度为O（nlog²（n））,算法基于模块度聚类和图计算思想应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法。相对于传统重叠节点检测算法,对每个节点分析的频率大大降低,可以在较低的算法运行时间下获得较高的识别准确率。复杂网络大数据集上的算法测试结果表明：DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法。     

True-link clustering through signaling process and subcommunity merge in overlapping community detection

To overcome the difficulty in detecting reliable overlapping communities in complex networks, “true-link” and “pseudo-link” are firstly proposed on the basis of the original network graph. Then, the “true-link” graph is obtained through the preprocessing of the original network graph. And then the line graph is partitioned by means of signaling process and single-linkage hierarchical clustering. Meanwhile, the subcommunities are merged based on the proposed similarity between communities, which eradicates the inherently redundant overlapping communities to a certain extent. Compared with other overlapping community detection algorithms, this proposed algorithm is of strong robustness and high accuracy. All the results of the experiments boil down to the conclusion that this True-link Clustering Community Detection is an overlapping community detection algorithm prevailing over others.

     

D-HOCS: an algorithm for discovering the hierarchical overlapping community structure of a social network

Social networks often demonstrate a hierarchical organization, with communities embedded within other communities; moreover, nodes can be shared between different communities, i.e. communities in social networks may be overlapping. In this paper, we define a hierarchical overlapping community structure to present overlapping communities of a social network at different levels of granularity. Discovering the hierarchical overlapping community structure of a social network can provide us a deeper understanding of the complex nature of social networks. We propose an algorithm, called D-HOCS, to derive the hierarchical overlapping community structure of social networks. Firstly, D-HOCS generates a probability transition matrix by applying random walk to a social network, and then trains a Gaussian Mixture Model using the matrix. Further D-HOCS derives overlapping communities by analyzing mean vectors of the Gaussian mixture model. Varying the number of components, D-HOCS repeatedly trains the Gaussian mixture model, detecting the overlapping communities at different levels of granularity. Organizing the overlapping communities into a hierarchy, D-HOCS can finally obtain the hierarchical overlapping community structure of the social network. The experiments conducted on synthetic and real dataset demonstrate the feasibility and applicability of the proposed algorithm. We further employ D-HOCS to explore Enron e-mail corpus, and obtain several interesting insights. For example, we find out a coordinator who coordinated many sections of the Enron Corporation to complete an important task during first half of 2001. We also identify a community that corresponds to a real organization in Enron Corporation.     

Semi-supervised community detection on attributed networks using non-negative matrix tri-factorization with node popularity

The World Wide Web generates more and more data with links and node contents, which are always modeled as attributed networks. The identification of network communities plays an important role for people to understand and utilize the semantic functions of the data. A few methods based on non-negative matrix factorization (NMF) have been proposed to detect community structure with semantic information in attributed networks. However, previous methods have not modeled some key factors (which affect the link generating process together), including prior information, the heterogeneity of node degree, as well as the interactions among communities. The three factors have been demonstrated to primarily affect the results. In this paper, we propose a semi-supervised community detection method on attributed networks by simultaneously considering these three factors. First, a semi-supervised non-negative matrix tri-factorization model with node popularity (i.e., PSSNMTF) is designed to detect communities on the topology of the network. And then node contents are integrated into the PSSNMTF model to find the semantic communities more accurately, namely PSSNMTFC. Parameters of the PSSNMTFC model is estimated by using the gradient descent method. Experiments on some real and artificial networks illustrate that our new method is superior over some related stateof- the-art methods in terms of accuracy.