Research On Local Expanding Class Overlapping Community Discovery Algorithms

Community discovery can help us to understand the structure of the network,The role of nodes in each other,and the characteristics of the network.Therefore,community discovery is becoming more and more concerned and has become a current research hot point.At present,there are many classic community discovery algorithms,which are mainly divided into non-overlapping communities algorithms and overlapping communities algorithms.In actual networks,communities are not isolated and overlap each other.In real networks,communities overlap and cross each other instead of being isolated.Therefore,research on overlapping community discovery is more realistic.This paper mainly studies the local expansion algorithms in overlapping community discovery algorithms,analyzes the classic algorithms,and draws on the core ideas.Then,through the improvement of seed selection and fitness function,a kind of locally extended class overlapping community discovering algorithm?HDOC?is obtained,and based on this algorithm,the parallelization model of HDOC algorithm is put forward in this paper.?1?Since the LFM algorithm randomly selects and causes instability of the algorithm when selecting seeds,this article first introduce a node importance assessment method H-index.In order to consider the importance of the node more comprehensively,We improved the method of node degree as the importance of nodes and obtained the calculation method of local importance of nodes?This makes computing nodes importance not only use the node's own information,but also consider the connection status of adjacent nodes.Finally,the importance of the node is calculated by combining the local importance calculation method with the H-index,and the seed node is selected accordingly.?2?The fitness function is the core of the local extension algorithm.The greater the importance of a node,the greater the influence on other nodes,and nodes are more inclined to join more closely connected communities.Therefore,considering the influence of adjacent nodes on a node and the degree of closeness between the node and the community,we propose a new calculation formula for fitness function.?3?When dealing with large networks,the parallelization of algorithms can improve the processing speed.The local expansion algorithm uses the local information of the network,So it can be easily extended to parallelization algorithm.In this paper,a parallel algorithm?P-HDOC?is obtained by introducing multi-threaded operation to the HDOC algorithm,P-HDOC selects seed nodes and seed nodes expansion in parallel,then CAS locks and Synchronize locks are added in segments to improve the efficiency of parallelism,and the communication problems of the algorithm in parallel are solved.?4?On a set of public datasets and LFR artificial networks,Through the modularity function EQ?Q_ov and the standard information volume,we can evaluate the division results of HDOC and other community discovery algorithms.It is known on the artificial network that the HDOC can discover high-quality overlapping communities with high stability.In the real network and the randomly generated LFR benchmark network,We compared the HDOC algorithm with P-HDOC's 2-thread parallelism,3-thread parallelism,and 4-thread parallelism.The experiments show that:1)P-HDOC algorithms are not suitable for sparse networks,In other networks,the P-HDOC algorithm and HDOC algorithm are basically similar in dividing effect,can be effectively divided into communities;2)On a certain scale of network,the P-HDOC algorithm can significantly increase the speed of partitioning for the HDOC algorithm.