一种面向度中心性及重叠网络社区的发现算法

针对社会网络中存在较多以度中心节点为中心并且具有多社区重叠节点的网络社区结构,提出了一种面向度中心性及重叠网络社区的两阶段发现算法。第一阶段发现初始社区:选取度最大的Top-k个节点作为候选中心节点,并将每个节点与其邻居节点形成候选初始社区,其中如果某候选社区与已形成的初始社区的重叠度低于阈值,则形成一个新的初始社区;第二阶段调整社区划分:通过偏离度机制进行调整,将偏离度最大值对应的节点划分到连接紧密的相应社区内,形成最终社区划分。实验表明,该方法不仅能够揭示网络中以某个节点为中心的密集的社区结构,还能有效处理初始社区不同程度的重叠问题。相比现有算法,所提方法对预先输入的候选初始社区数k值不敏感,并具有较高的准确性和灵活性。     

一种重叠社区发现的启发式算法

提出了一种重叠社区发现的启发式算法。该算法基于局部贡献度的思想,以度最大的节点作为初始社区,逐步把对社区贡献最大的邻节点加入社区;同时考虑了社区的重叠性,若存在对多个社区贡献都很大的边界节点,则把边界节点同时加入到这些社区中。最后利用重叠系数对所划分的社区进行调整,使社区结构更加合理。对两个经典的社会网络Zachary和American College Football进行了实验测试,实验结果表明：该算法能快速准确地划分出社区,并能挖掘出社区间的边界节点。     

面向属性网络的可重叠多向谱社区检测算法

谱社区检测算法多基于结构对网络进行划分,往往受限于划分数量且难以控制重叠程度。设计了面向属性网络的谱社区检测算法,可将属性网络划分为任意数量的可重叠社区并有效发现离群点。具体地,首先,从结构和属性两方面综合考虑,基于加权模块度设计了最大化到节点向量化的分区映射方法;其次,给出簇中心向量的初始选择策略,并将其融合在面向属性网络的重叠度和离群度制约中,实现重叠社区的发现;再次,设计节点分配策略,计算节点与簇中心向量的内积,将节点分配给具有最高内积的社区;最后,结合节点隶属情况,高效地在属性网络中检测出结构紧密、可重叠和具有离群点的社区。此外,将本文算法应用于现实世界的多个网络,验证了本文算法的有效性和效率。     

基于引力因子的加权网络重叠社区识别算法

通过挖掘大数据来识别复杂社会网络上的社区,有利于对经济、政治、人口等方面的重要问题进行定量研究,社区的识别算法已经成为当前研究的热点问题。重点研究了重叠社区识别问题,提出了基于引力因子的加权复杂网络的重叠社区识别算法GWCR。该算法首先选取万有引力因子大的节点为中心节点,将节点与中心节点之间的引力因子作为衡量标准,并将节点归入社区引力因子大于某一阈值的社区,最后通过识别重叠节点来识别重叠社区。在3个真实网络数据集上的实验结果表明,与传统的重叠社区识别算法相比,GWCR算法划分的社区的模块度较高。     

重叠社区发现的两段策略

复杂网络中的社区特别是重叠社区在信息传播与推荐、舆情控制、商业营销等领域中具有重要作用。在实际的网络中,由于有些节点天然地属于多个功能团体,重叠社区的挖掘越来越受到重视。提出了一种重叠社区挖掘的两段策略算法:初始社区抽取与社区合并。在社区抽取阶段,选择网络中最大度节点及其紧密的邻居节点作为初始社区,将与此初始社区联系紧密的节点也一并加入;在社区合并阶段,如果两个社区合并之后使得模块度增加,则合并这两个社区。用包括大规模网络在内的3个实际网络对所提算法进行了测试,结果表明,该算法可有效挖掘网络中的重叠社区。     

基于种子节点选择的重叠社区发现算法*

识别网络社区对于了解社会网络的结构和功能具有重要意义。由于网络中某些节点可能属于多个社区,因此重叠社区的研究已经吸引了人们越来越多的关注。本文针对目前从局部社区扩展成全局社区时有关算法的种子节点选择不合理的情形,提出了一种基于种子节点选择的重叠社区发现算法。本算法首先根据影响力函数找出局部影响力最大的节点,由这些节点构成的种子集合较好的分布在整个网络中,然后以这些种子点构造初始社区,根据设定的吸引度函数选择性添加节点来进行社区扩展。实验结果表明,该算法在真实网络上进行测试时能够有效的挖掘网络中的重叠社区。     

基于节点层级与标签传播增益的重叠社区发现?

多标签传播算法具有接近线性的时间复杂度,但用于重叠社区发现时存在精度低、稳定性差的问题。文中基于重叠节点更可能出现在社区边缘的思想,提出基于节点层级与标签传播增益的重叠社区发现算法。该算法首先利用改进的基于节点中心度与社区分布约束的单标签传播方法发现非重叠社区,并在标签传播过程中利用局部信息同步计算节点中心度。然后根据节点中心度定义节点层级函数,标记节点在所属社区中的层级。最后基于节点间的标签传播增益,利用新的多标签更新规则,获得重叠社区结构。实验表明该算法能有效提高精度和稳定性。     

基于节点拓扑结构和属性的重叠社区检测算法

近些年来,网络中的重叠社区检测应用越来越广泛,这极大引起了人们的兴趣。通常重叠社区检测只考虑节点的拓扑结构信息,忽略了节点的属性信息,这可能会遗漏数据间的重要结构。本文提出了一种基于节点拓扑结构和属性相似度的局部社区检测算法。首先,计算出节点与社区之间属性相似度。其次,为挖掘内部紧耦合的社区,计算出能够表示耦合性的模块度增量。最后,通过融合多个已检测到局部社区,计算出隶属矩阵从而获取全局重叠社区结构。在三个有真实社区的数据集上的实验结果从内部指标模块度和与真实社区的比较验证了基于节点拓扑结构和属性相似度的重叠社区检测算法比目前基于节点结构的社区检测算法在效率和有效性上有所提升。     

基于连边相似度的重叠社区发现算法研究

针对GN算法在发现重叠社区时存在的不足,以及为了降低算法时间复杂度,提出一种基于网络图中连边相似度划分连边集的重叠社区发现算法EGN。算法依据网络图的连边集进行划分,每一条边被划分到某个特定的社区,而一个节点可以关联多条连边,因此节点可以被划分到不同的社区,从而发现重叠社区。EGN算法首先需要构造网络节点之间连边关系的边图;然后根据边图中节点的关系计算网络图中连边的相似度,在节点之间相似度的基础上提出了连边之间相似度的计算方法;再按照相似度由小到大对边图删除边,构建出边图的树状图。树状图的每一层对应网络的一个划分,采用划分密度函数来衡量划分的质量,以此寻找最优的划分。最后将算法应用到Zachary空手道俱乐部网络中,并与GN算法进行对比,实验结果表明EGN算法能够很好地发现重叠社区。     

基于密度分布的社区发现算法研究

基于密度吸引点和其对相邻节点的影响度,提出了一种密度分布社区发现算法。该算法以节点度数最大的密度吸引点为初始社区,访问社区的相邻节点,把对社区影响度最大的节点加入到社区中,如果有些节点对多个社区都有影响,则把它归属为影响度最大的那个社区中,同时如果两个社区之间的相互影响度很大,可以将这两个社区合并为一个社区。将该算法应用到Zachary空手道俱乐部网络和随机无标度网络中,实验表明该算法能够很好地分出网络中的社区,同时实验还发现社区的收敛速度与幂率分布特性近似成反比。     

基于重叠社区和结构洞度的社会网络结构洞识别算法

结构洞是社会网络中的关键位置,对信息扩散起中介作用。为高效、准确地辨识具有社团结构的社会网络中占据结构洞的节点,提出了一种基于重叠社区和结构洞度的结构洞识别算法,旨在找到一组最具信息优势和控制优势的节点。基本思想是首先定位社区之间的重叠节点,然后利用节点的邻接差异和连接的社区差异衡量其非冗余性,计算出重叠节点的结构洞度,通过对结构洞度值升序排列发现占据结构洞的节点集。应用于实际数据集的实验结果表明,与网络约束系数算法、中介中心度算法、MaxD算法相比,该算法的识别准确度最高,时间复杂度最低。     

Network representation learning based on community-aware and adaptive random walk for overlapping community detection

The Network representation learning methods based on random walk aim to learn a low-dimensional embedding vector for each node in a network by randomly traversing the network to capture the features of nodes and edges, which is beneficial to many downstream machine learning tasks such as community detection. Most of the existing random-walk-based network representation learning algorithms emphasize the neighborhood of nodes but ignore the communities they may form and apply the same random walk strategy to all nodes without distinguishing the characteristics of different nodes. In addition, it is time-consuming to determine the most suitable random walk parameters for a given network. In this paper, we propose a novel overlapping community detection algorithm based on network representation learning which integrates community information into embedding vectors to improve the cohesion degree of similar nodes in the embedding space. First, a node-centrality-based walk strategy is designed to determine the parameters of random walk automatically to avoid the time-consuming manual selection. Second, two community-aware random walk strategies for high and low degree nodes are developed to capture the characteristics of the community centers and boundaries. The experimental results on the synthesized and real-world datasets demonstrate the effectiveness and efficiency of our algorithm on overlapping community detection compared with the state-of-the-art algorithms

     

融合特征向量中心性与标签熵的标签传播算法

重叠社区结构挖掘旨在发现复杂网络中多个独立社区之间的重叠部分，其在社交、交通、舆情乃至反恐等领域具有广泛的应用。然而，目前基于标签传播的重叠社区挖掘算法在社区结构模糊的网络中表现出较强的随机性，导致准确度不高。针对重叠社区模糊边界导致的不确定性和低准确度问题，提出一种融合特征向量中心性与标签熵的标签传播算法ECLE-LPA。ECLE-LPA通过融合节点的K-核迭代因子与特征向量中心性来计算节点影响力并初始化节点标签，在标签传播过程中，通过节点标签熵和节点间亲密度更新节点标签列表及其标签隶属度，从而较好地克服了社区模糊边界的识别问题。实验结果表明：在Les Miserables、Polbooks、Football、Polblogs和Netscience等真实网络中，ECLE-LPA划分结果的EQ值普遍比对比算法提高了1%～3%;在社区结构模糊的人工网络中，ECLE-LPA划分结果的NMI值比其他标签传播算法提高了10%以上。     

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

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

一个基于中心度的社团结构发现新算法*

针对GN算法在社团结构发现中时间复杂度高等问题,提出一种基于中心度的GN改进算法（DCGN）。该算法根据节点中心度以及节点之间的最短路径首先确定社团结构中心节点集,然后逐步删除社团结构中心节点之间的最大边介数连边,完成社团结构划分。DCGN算法避免了GN算法边介数计算开销大的问题,算法的时间复杂度约为O(cmn),其中c为常数,n为网络成员数,m为网络连边数。将DCGN和GN算法同时应用到Zachary网络及计算机随机生成网络中并进行了比较。实验结果表明,所提出的DCGN算法在运行效率和效果方面较之GN算     

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

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

融入K-核迭代因子的重叠社区发现算法

基于局部扩展的重叠社区发现算法,利用社区的局部扩展特性可有效扩展出重叠社区,但是现有算法存在划分结果不稳定和准确性较低等问题,因此提出了一种基于[K]-核迭代因子和社区隶属度的重叠社区发现算法。该算法引用[K]-核迭代因子的思想,并且与节点密度值相结合,量化节点的影响力,找出节点影响力最大的节点,提高种子节点选择的稳定性和准确性;同时以影响力大的节点为种子节点,通过节点影响力计算得到邻接节点的社区隶属度,根据社区隶属度选择性地添加邻接节点进行社区扩展,提高社区发现的质量。在人工网络图和真实数据集上进行实验,结果表明所提的算法与现有的算法比较具有较高的稳定性和准确性。     

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

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

A community detection algorithm based on Quasi-Laplacian centrality peaks clustering

Searching for key nodes in social networks and clustering communities are indispensable components in community detection methods. With the wide application demand of detecting community networks, more and more algorithms have been proposed. Laplacian centrality peaks clustering (LPC) is an efficient and simple algorithm which is proposed on the basis of density peaks clustering (DPC) to identify clusters without parameters and prior knowledge. Before LPC is widely applied in community detection algorithms, some shortcomings should be addressed. Firstly, LPC fails to search for key nodes in networks accurately because of the similarity calculation method. Secondly, it takes too much time for LPC to calculate the Laplacian centrality of each point. To address these issues, a community detection algorithm based on Quasi-Laplacian centrality peaks clustering (CD-QLPC) is proposed after studying the advantages of Quasi-Laplacian centrality which can replace density or Laplacian centrality to characterize the importance of nodes in networks. Quasi-Laplacian centrality is obtained by the degree of each node directly, which needs less time than Laplacian centrality. In addition, a trust-based function is utilized to obtain the similarity accurately. Moreover, a new modularity-based merging strategy is adopted to identify the optimal number of communities adaptively. Experimental results show that CD-QLPC outperforms many state-of-the-art methods on both real-world networks and synthetic networks.