Research On Parallel Network Community Detection Algorithm Based On Ant Colony Optimization

Various kinds of networks are present in both natural and social environment for human beings,containing enormous amount of valuable information in their complex relationships.Community detection,as a data mining method,is of great significance to the study of the characteristics of complex networks.Ant colony optimization(ACO)algorithm has been more and more frequently applied to the field of community detection because of its distributed positive feedback parallel mechanism and the strong robustness and stability.Now in the era of big data,the “information explosion” and the real-time update feature has made the single machine execution no longer capable of satisfying the data information of large-scale networks.Therefore,the distributed computing platforms,as represented by Spark,have emerged at the right moment.This paper generally discusses the shortcomings of the current ant colony optimization algorithm in dealing with community detection problems,improves the ant colony optimization algorithm,and implements it in parallel on Spark distributed platform.The novelty of this paper mainly includes the following two aspects:(1)Focusing on the defects of low precision and slow convergence speed of ant colony optimization algorithm,a specific ant colony optimization algorithm based on label propagation,namely BLP?ACO,is proposed for the first time.Firstly,this algorithm adopts a new solution vector expression,where each node in the solution vector stores the label of the community to which the node belongs.The task of the ant colony is to construct the solution vector by determining the node label.Secondly,the node cohesion measurement is introduced to the solution construction phase to determine the order of ant transfer,to reduce the randomness in the process of ant transfer,and to improve the accuracy of the algorithm.In order to increase the algorithm convergence speed,the idea of label propagation is introduced to the search process of ant colony,and an ant calibration strategy based on local community scale and community similarity bias was proposed.This strategy combines pheromone and heuristic information to comprehensively determine node labels.Thirdly,the concept of even edge rate is applied to the solution optimization stage,and the merging strategy based on modular degree optimization is adopted in order to further improve the accuracy of the algorithm.Finally,pheromones are retained on all edges within the community while updating.In the experimental part,the proposed algorithm BLP?ACO,as well as the classical ant colony optimization algorithm RWACO,MACO,IACO and the improved label propagation algorithm SOCP?LPA,are applied to both the real network and the LFR benchmark network.The results show that BLP?ACO can mine the community structure more accurately and reach the convergence state more raplidly.(2)Focusing on the big data environment,a parallel label propagation ant colony optimization algorithm based on Spark,namely SLP?ACO,is established.Based on the related technology of Spark distributed platform,the algorithm designs a distributed framework for the module of determining ant transfer order,the module of ant colony constructing optimal initial solution and the module of combination optimization in the serial BLP?ACO algorithm,so that the parallel effect is enhanced.At the same time,the RDD operator used in the parallelization process is described in detail,and the corresponding RDD data state transition diagram is given.Experimentally,the algorithm is applied to a large scale network,and SLP?ACO is proved to have improved parallelism by speedup.