Research On Overlapping Community Discovery Algorithms Of Local Extension Class

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.