Research On Overlapping Communities Discovery Algorithms In Complex Networks

With the increasing development of information technology,more and more people pay more and more attention to the various forms of community organization in the mining network.In a particular network,a "community" composed of a group of closely connected vertices is called a community.Mining a complex community structure can help us recognize and solve many practical problems.At present,scholars have successively proposed a variety of community discovery algorithms.Among the proposed static overlapping community discovery algorithms,the multi-label propagation algorithm is very popular for its simplicity and efficiency,but the algorithm has the shortcomings of strong randomness and poor stability.This has been optimized accordingly.At the same time,real-world networks are constantly changing,so community discovery of dynamic networks is gradually being proposed.With the explosive growth of network data,it is particularly important to combine parallel computing with dynamic community discovery algorithms at this time.In this thesis,we have conducted in-depth research on the overlapping community discovery algorithms of static and dynamic network types.The main tasks are as follows:1.In view of the strong randomness and instability of the current static multi-label propagation algorithm,the local similarity index of nodes is proposed,the clustering coefficient and the Jaccard coefficient are effectively combined,and they are applied to the label selection of the label propagation algorithm.And the update stage.2.Based on the idea of multi-label propagation algorithm,this thesis proposes a static overlapping community discovery algorithm COPRALS based on node local similarity.In the initialization phase of the algorithm,the nodes whose degree is less than the threshold are filtered,and the minimal complete subgraph is used as the start of label propagation.At the same time,the selection and update of node labels are based on the local similarity index of nodes proposed in this thesis,which effectively improves the accuracy of the algorithm.3.Aiming at the problems of current dynamic network community discovery algorithms that cannot be applied to overlapping communities and low computational efficiency,this thesis proposes the PICDLS algorithm based on the idea of incremental clustering,which can be applied to overlapping networks.And use Spark GraphX as a parallelized computing framework,and at the same time introduce the idea of the law of gravitation in physics,and perform local adjustments of nodes by calculating the relationship between the internal and external forces received by the nodes.And after getting the community at different moments of the network,it is necessary to use the parallelization index PWCC to measure its reliability.4.In this thesis,the two algorithms of COPRALS and PICDLS are respectively applied to the LFR benchmark network and the existing real network data set,and compared with the experimental analysis of different algorithms,it is concluded that the static overlapping community discovery algorithm proposed in this thesis is COPRALS and the algorithm based on augmentation.A large number of parallel dynamic overlapping community discovery algorithms perform well in terms of extended modularity EQ,standard mutual information NMI,and time performance.There are 44 pictures,7 tables,and 55 references.