基于LeaderRank和节点相似性的多标签传播重叠社团挖掘算法

针对基于多标签传播重叠社团挖掘算法COPRA因随机更新策略带来的不稳定性以及需要预先输入参数的局限性等问题,提出一种基于LeaderRank和节点相似性的多标签传播重叠社团挖掘算法.该算法首先利用LeaderRank算法对网络中的节点进行重要性排序从而确定节点的更新顺序,减少标签不必要的更新.在标签传播过程中,根据节点相似性重新设计标签的更新策略,提高算法的稳定性.将算法应用于人工网络和真实网络中进行实验,实验结果表明该算法在挖掘重叠社团上具有较高的准确性和稳定性.     

基于LeaderRank的多标签传播重叠社区发现算法*

针对多标签传播重叠社区发现算法COPRA存在的的随机性强、鲁棒性差等问题,提出一种基于多标签传播思想的重叠社区发现算法。该算法通过LeaderRank算法来量化网络中节点的重要性,再根据量化值大小对节点进行团扩展,得到可重叠的最具重要性的粗糙团,分别对粗糙团和非粗糙团中的节点进行标签初始化,再通过合理的标签迭代顺序和改进的标签删选策略进行标签更新,直到达到标签传播的终止条件结束迭代过程。在人工网络图和真实数据集上进行实验,结果表明所提算法不仅有效地增强了社区发现结果的稳定性,同时提高了准确率。     

基于LeaderRank的重叠社区发现算法

在真实的社交网络结构中常常存在着社区相互重叠的现象,发现社交网络中的重叠社区有利于研究网络特性,反映网络中的真实情况。针对多标签传播重叠社区发现算法COPRA存在的随机性,导致社区发现结果稳定性差等问题,提出一种结合节点重要性的标签传播算法。该算法首先采用LeaderRank计算出网络中各个节点的重要性,选择重要性高的节点进行团扩展作为标签初始阶段的预处理,采用合理的标签更新顺序以防止抵消预处理阶段的工作,后期引入贡献度来弱化标签选择阶段的随机性,在基准网络和真实网络上的实验结果表明本文算法提高了社区发现结果的质量。     

融合K-shell和标签熵的重叠社区发现算法

针对标签传播算法稳定性不足、准确性较差的问题,提出了融合K-shell和标签熵的标签传播重叠社区发现算法OCKELP。首先,采用K-shell算法减少了标签初始化时间,并利用标签熵的更新序列提高了算法的稳定性;其次,引入综合影响力进行标签选择,并将社区层次信息和节点局部信息融合提高了算法的准确性。在真实网络数据集上,OCKELP相较于重叠社区发现算法（COPRA）、基于多核心标签传播的重叠社区识别方法（OMKLP）、SLPA的模块度最大提升分别约68.64%、53.99%、42.29%,在人工网络数据集的归一化互信息（NMI）值上,OCKELP相较于其他三种算法也有着明显优势,且随着重叠节点隶属社区数量的增加可以挖掘出社区的真实结构。     

基于节点引力与鱼记忆的社区检测算法

标签传播算法是高效且具代表性的社团检测算法,其中不包含必需调节适应的相关参数,是大型网络社团检测的首选算法。标签传播算法具有较低的时间复杂度,但其随机性较强,且在标签传播过程中存在不确定性因素,影响了社区检测的准确性和稳定性。针对上述问题,提出一种基于节点引力和鱼记忆标签存储策略的社区检测算法CDA-GM。通过融入节点信息熵的k-shell排序策略增强社区检测的准确性,利用节点间的引力更新标签,减小标签传播的随机性。在此基础上,引入鱼记忆节点标签存储策略,避免出现标签震荡,增强标签传播的稳定性。选择人工网络和真实世界网络数据集进行实验,结果表明,该算法能够显著提高社区检测质量,获得准确的社区结构,与COPRA、SLPA、DLPA和COPRAPC算法相比,其标准化互信息值平均提高0.01、0.18、0.12、0.02,社区模块度平均提高0.04、0.02、0.07、0.01。     

局部扩展的遗传优化重叠社区发现方法

重叠社区结构是复杂网络的一种重要的特征,提出了一种局部扩展的遗传优化重叠社区发现（LEGAOCD）。借鉴局部扩展的重叠社区发现方法的思想,将少数的核心节点构成模体;同时,利用了三角形模体来判断社区的稳定性度量问题,从而量化社区结构稳定性;然后通过改进的遗传优化算法策略分配它们应归属的社区;最后通过两个评价目标函数得到高质量的重叠社区结构。该算法在数据集上与经典的CPM算法、COPRA算法作比较,实验结果表明,LEGAOCD算法在检测重叠社区结构和重叠节点方面具有较优的性能。     

基于标签传播的社区挖掘算法研究综述

社会网络由于其流行程度已经成为众多学者的研究热点。通过社区挖掘算法可以发现存在于社会网络中的潜在社区,而重叠社区挖掘则可以挖掘出更具有现实意义的社区结构。但是在研究中社会网络所包含的庞大数据量又会为之带来种种不便,因此快速的社区挖掘算法就受到了越来越多的重视。基于标签传播的社区挖掘算法具有近乎线性的时间复杂度。文中将从多方面研究目前基于标签传播的社区挖掘算法的优劣,并且详细分析基于标签传播算法在以后研究中的改进思路。     

A stable community detection approach for complex network based on density peak clustering and label propagation

Dividing a network into communities has great benefits in understanding the characteristics of the network. The label propagation algorithm (LPA) is a fast and convenient community detection algorithm. However, the community initialization of LPA does not take advantage of topological information of networks, and its robustness is poor. In this paper, we propose a stable community detection algorithm based on density peak clustering and label propagation (DS-LPA). First, the local density calculation method in density peak clustering algorithm is improved in finding the community center of the network, so as to build a suitable initial community, which can improve the quality of community partition. Then, the label update order is determined reasonably by computing the information transmission power of nodes, and the solutions for multiple candidate labels are provided, which greatly improved the robustness of the algorithm. DS-LPA is compared with other seven algorithms on the synthetic network and real-world networks. NMI, ARI, and modularity are used to evaluate these algorithms. It can be concluded that DS-LPA has a higher performance than most comparison algorithms on synthetic network with ten different mixed parameters by statistical testing. And DS-LPA can quickly calculate the best community partition on different sizes of real-world networks.

     

网络重叠社区发现的谱聚类集成算法

鉴于计算代价高昂的谱聚类无法满足海量网络社区发现的需求,提出一种用于网络重叠社区发现的谱聚类集成算法(SCEA).首先,利用高效的近似谱聚类(KASP)算法生成个体聚类集合;然后,引入个体聚类选择机制对个体聚类进行优选,并对优选后的个体聚类建立簇相似图;最后,进行层次软聚类,得到网络节点的软划分.实验结果表明,与代表性算法(CPM,Link,COPRA,SSDE)相比较,SCEA能够挖掘出具有更高规范化互信息(NMI)的网络重叠社区结构,且具有相对较好的鲁棒性.     

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.     

Overlapping community detection based on discrete biogeography optimization

Community detection can be used to help mine the potential information in social networks, and uncovering community structures in social networks can be regarded as clustering optimization problems. In this paper, an overlapping community detection algorithm based on biogeography optimization is proposed. Firstly, the algorithm takes the method of label propagation based on local max degree and neighborhood overlap for initial network partitioning. The preliminary partition result used to construct initial population by cloning and mutating to accelerate the algorithm’s convergence. Next, to make biogeography optimization algorithm suitable for community detection, we design problem-specific migration rules and mutation operators based on a novel affinity degree to improve the effectiveness of the algorithm. Experiments on benchmark test data, including two synthetic networks and four real-world networks, show that the proposed algorithm can achieve results with better accuracy and stability than the compared evolutionary algorithms.     

基于标签影响力的半同步社区发现算法

微博网络与社交网络等的交互式社会信息网络规模的快速增长对社区发现提出巨大挑战。标签传播算法(LPA)虽然在时间复杂度上具有很大的优势,但是其内在的多种随机策略使得算法稳定性不高。针对LPA的随机问题,提出了一种基于影响力的半同步标签传播算法(ISLPA),能有效地避免振荡问题,巧妙地实现了相邻节点之间的同步更新,并结合影响力从初始标签、选择邻居节点和更新顺序三方面进行了改进,摒弃了原有的随机策略。真实网络和人工网络的实验结果表明,ISLPA具有较高的稳定性与有效性,与其他LPA相关算法相比存在明显的优势。     

一种新的基于标签传播的复杂网络重叠社区识别算法

针对现有基于标签传播的复杂网络重叠社区识别方法所存在的社区识别精度不稳定,以及随机性较强等缺陷,提出一种新的基于标签传播的复杂网络重叠社区识别算法NOCDLP(a novel algorithm for overlapping community detection based on label propagation).该算法首先搜索网络中若干以度较高节点为中心的完全子图,并以这些完全子图为起点进行标签传播;其次通过分析节点与社区连接强度以及社区接纳某节点后的社区内部连接紧密度情况给出节点归属社区强度函数,以此作为标签传播的依据提高社区的识别精度;再次,在标签传播过程中,NOCDLP算法设置标签传播控制标记,以避免标签传播算法随机性较强的缺陷;最后,在已形成的社区中通过整理重叠节点获得更准确的重叠社区结构.算法在人工网络与真实网络中完成测试,同时与多个经典算法进行对比分析,实验结果验证了NOCDLP算法是有效的、可行的.     

一种局部强化的多标签传播社区发现算法

在社交网络中,社区和圈子均表现为一组内部连接相对紧密的节点,但后者规模较小。圈子是重要的局部社区信息,利用这一特点有助于进行社区发现。然而,现有的大部分基于标签传播的社区发现算法并没有考虑圈子的信息。为此,提出一种基于局部强化的多标签传播(LSMLP)社区发现算法。给出圈子的定义,提出一种基于圈子信息的迭代多标签传播策略,并从每个节点的多个标签中选择归属系数最大的标签作为其从属的临时社区。采用两步优化方法使模度最大化。在真实网络的数据实验结果表明,与已有的社区发现算法相比,LSMLP算法能更高效地发现社区。     

基于多标签传播机制的蛋白质相互作用网络功能模块检测*

鉴于多标签传播算法在发现社会网络的社区结构研究上具有快速、高效的求解能力,提出融合多源蛋白质生物学知识的基于多标签传播机制的蛋白质相互作用(PPI)网络功能模块检测算法.首先,结合PPI网络功能信息和结构信息初始化节点的标签.然后,利用基因表达数据描述蛋白质间的共表达性,依据共表达性构建标签集合,从中选择标签以实现标签在节点间真实可靠的传播.最后,将具有相同标识符的节点划分到同一功能模块中,获得最终结果.实验表明文中算法不仅具有良好的时间性能,而且在检测精度上也具有一定的竞争性.     

一种基于信息扩散的复杂网络重叠社区发现算法

社区结构可以为网络的其他分析挖掘提供中观尺度的分析视角,在大规模复杂网络的各项研究中是一项非常重要而基础的工作。社区的重叠是真实世界网络中常见的一种现象,重叠社区结构可以更准确地描述网络中真实的结构信息,因此,复杂网络重叠社区发现具有更加突出的现实意义。在综合对比分析了当前主要的重叠社区发现算法的基础上,结合信息论的相关知识,给出了一种基于信息论的社区定义,并进一步借鉴信息传播理论,从单个节点对关于某种主题的信息的掌握程度的角度出发提出了一种复杂网络重叠社区结构发现算法。基于实际数据集的相关实验表明,与传统的社区定义和社区发现算法相比,本算法发现的重叠社区从内容角度来看具有更加明确的实际意义,并且具有较低的时间复杂度。     

面向属性网络的重叠社区发现算法

针对现实世界的网络节点中包含大量属性信息并且社区之间呈现出重叠特性的问题,提出了一种面向属性网络的重叠社区发现算法。融合网络的拓扑结构和节点属性定义了节点的密集度和间隔度,分别用于描述社区内部连接紧密和外部连接松散的特点。基于密度峰值聚类的思想搜索局部密度中心作为社区中心,在此基础上给出了非中心节点关于各个社区的隶属度的迭代计算方法,实现了重叠社区的划分。在真实数据集上进行了仿真实验,实验结果表明所提算法相对于LINK、COPRA和DPSCD能获得更好的社区划分结果。     

Dual modularity optimization for detecting overlapping communities in bipartite networks

Many algorithms have been designed to discover community structure in networks. These algorithms are mostly dedicated to detecting disjoint communities. Very few of them are intended to discover overlapping communities, particularly the bipartite networks have hardly been explored for the detection of such communities. In this paper, we describe a new approach which consists in forming overlapping mixed communities in a bipartite network based on dual optimization of modularity. To this end, we propose two algorithms. The first one is an evolutionary algorithm dedicated for global optimization of the Newman’s modularity on the line graph. This algorithm has been tested on well-known real benchmark networks and compared with several other existing methods of community detection in networks. The second one is an algorithm that locally optimizes the graph Mancoridis modularity, and we have adapted to a bipartite graph. Specifically, this second algorithm is applied to the decomposition of vertices, resulting from the evolutionary process, and also characterizes the overlapping communities taking into account their semantic aspect. Our approach requires a priori no knowledge on the number of communities searched in the network. We show its interest on two datasets, namely, a group of synthetic networks and real-world network whose structure is also difficult to understand.     

Recurrent Neural Networks Training With Stable Bounding Ellipsoid Algorithm

Bounding ellipsoid (BE) algorithms offer an attractive alternative to traditional training algorithms for neural networks, for example, backpropagation and least squares methods. The benefits include high computational efficiency and fast convergence speed. In this paper, we propose an ellipsoid propagation algorithm to train the weights of recurrent neural networks for nonlinear systems identification. Both hidden layers and output layers can be updated. The stability of the BE algorithm is proven.      

复杂网络重叠社区结构发现的演化算法研究

复杂网络重叠社区结构的划分已成为复杂网络研究的一个热点,目前已提出了很多关于社区结构发现的算法。提出了一种基于个体从众的演化算法ICEA,基本思想是由节点邻居组成的个体依概率进行从众和变异操作,用较短时间找到最优(或拟最优)模块度的社区划分,社区结构确定后利用邻居投票机制NV发现网络的重叠节点,完成重叠社区的划分。在真实网络的实验结果表明,此算法的使用时间和划分结果都优于典型算法。