【作者】 赵亮；

【导师】 朱征宇；

【作者基本信息】 重庆大学 ， 计算机科学与技术， 2019， 硕士

【摘要】 随着互联网在现代生活中的普及,现实世界中的许多事物都以网络的形态存在,重叠社区发现算法可以帮助我们更好地理解网络的结构特征。目前重叠社区发现算法总体可以分为全局划分和局部扩展两大类。本文主要对局部扩展类的重叠社区发现算法进行研究,针对现有算法在划分结果的准确性、稳定性和算法运行时间等方面存在的一些不足进行研究,提出多种改进算法。本文的主要研究工作及贡献如下:(1)针对现有算法划分结果在准确性和稳定性方面的不足,提出了一种基于K-核迭代因子和社区隶属度的重叠社区发现算法(KIMDOC)。首先,该算法引入一种节点重要性评估方法K-核迭代因子,同时引入节点密度的概念得到节点局部影响力的计算公式,利用这两种方法来计算节点影响力,并依据节点影响力选择种子节点,作为初始社区。其次,基于节点影响力提出一种新的社区隶属度函数,利用该社区隶属度函数基础上,以初始社区为核心,逐步进行局部扩展,因不同的社区间会有交集,故KIMDOC算法可以发现重叠社区。最后,对重叠度高的社区和孤立节点进行处理,得到最终的划分结果。(2)为了提高KIMDOC算法的运行效率,提出了一种基于完全图和社区隶属度的重叠社区发现算法(KIMDOC-CG)。该算法是在KIMDOC算法的基础上进行改进。首先,用KIMDOC算法中节点影响力的计算方法,选择种子节点。其次,以种子节点为核心,寻找完全图,形成初始社区。然后,在KIMDOC算法中的社区隶属度函数基础上,以初始社区为核心,进行局部扩展。最后,对孤立节点和重叠度高的社区进行处理,得到最终的划分结果。(3)针对现有算法在时间效率和阈值参数方面的不足,提出了一种基于K-核迭代因子和完全图的重叠社区发现算法(KICGOC)。该算法引入KIMDOC算法中节点影响力的计算方法,并依据节点影响力选择种子节点。其次,以种子节点为核心,按照不断寻找完全图的方式进行局部扩展。在扩展社区时,因为使用完全图代替社区隶属度,避免阈值参数对算法结果的影响;由于没有社区隶属度的计算,提升了算法的速度。最后,对重叠度高的社区进行合并,得到最终的划分结果。(4)在真实网络和人工基准网络上,与现有多种算法进行的对比实验表明:1)KIMDOC算法具有较高的稳定性和准确性,能够得到高质量的重叠社区;2)KIMDOC-CG算法不仅具有较高稳定性和准确性,能够发现高质量的重叠社区,并且在节点数量大于1000的复杂网络上,运行速度高于现有算法和KIMDOC算法;3)KICGOC算法在社区划分结果比现有算法好的情况下,不需要设置阈值参数,同时在节点数量大于1000的复杂网络上,具有更高的时间效率。更多还原

【Abstract】 With the popularity of the Internet in modern life,many things in the real world exist in the form of network.The research on overlapping community discovery algorithms can help us better understand the structural characteristics of various networks.At present,overlapping community discovery algorithms can mainly be divided into two categories: global division and local extension.This paper mainly studies the overlapping community discovery algorithm of local extension class.By analyzing the shortcomings of existing algorithms in terms of accuracy,stability and algorithm running time,this paper proposes various improved algorithms.The main research work and contributions of this paper include the following:(1)Aiming at the shortcomings on accuracy and stability of existing algorithms in their partitioning results,this paper proposes an overlapping community discovery algorithm based on K-shell iterative factor and community membership degree(KIMDOC).Firstly,KIMDOC introduces a K-shell iterative factor as the evaluation method for node importance,and introduces the concept of node density to obtain the calculation formula of node local importance.It uses the two methods to calculate each node influence,and then the seed nodes as the initial community are selected according to the node influence.Secondly,a new community membership function is proposed based on the node influence.By the community membership function,with the initial community as the core,the local expansions are carried out gradually.There will be intersections between different communities,so KIMDOC can find overlapping communities.Finally,the similarity communities and isolated nodes are processed to achieve the final result.(2)In order to improve the running efficiency of the KIMDOC algorithm,this paper proposes an overlapping community discovery algorithm based on complete graph and community membership degree(KIMDOC-CG).KIMDOC-CG is an improved algorithm of KIMDOC.Firstly,the seed nodes are selected by the node influence calculation method in the KIMDOC algorithm.Secondly,the seed nodes are taken as the core to find the complete graph and form the initial community.Thirdly,based on the community membership function in the KIMDOC algorithm,the initial community is the core and local extension is implemented.Finally,the isolated nodes and the similarity communities are carried out to get the final result.(3)Aiming at the shortcomings of existing algorithms on time efficiency and threshold parameters,this paper presents an overlapping community discovery algorithm based on K-shell iteration factor and complete graph(KICGOC).Firstly,the seed nodes are selected by the node influence calculation method in the KIMDOC algorithm.Secondly,with each seed node as the core,the community is locally expanded outward by continuously searching for complete graphs.When expanding the community,the impact of threshold parameter on algorithmic results is avoided by using complete graph instead of community membership degree.Because there is no calculation of community membership degree,the speed of algorithm is improved.Finally,the communities with high similarity are merged to get the final result.(4)Our comparison experiments on several real networks and manual benchmark networks with existing algorithms show that: 1)The KIMDOC algorithm has better stability and accuracy,and can get high quality overlapping communities.2)The KIMDOC-CG algorithm not only has stability and accuracy,can find high-quality overlapping communities,but also its running speed is faster than existing algorithms and KIMDOC algorithms on various complex networks with more than 1000 nodes.3)The KICGOC algorithm does not need to set any threshold parameter and its community partitioning result is better than the existing algorithms.Meanwhile KICGOC algorithm has higher time efficiency on various complex networks with more than 1000 nodes.更多还原