Complex Network Community Detection Based On Particle Swarm Optimization Algorithm

Complex network is everywhere in current society. Actually people are in complex network all the time. Community detection is an interpretation of complex network and has become a popular research area. PSO is a group intelligence optimization algorithm proposed at the end of the last century, the idea of which comes from the cooperation of birds for food. This thesis studies how to apply PSO in the area of community detection, and the application strategies of different PSO algorithms are analyzed. Besides, the improvements toward the deficiency of the original PSO when applied in community detection are proposed. Furthermore, cloud computing is introduced to study how to use PSO for community discovery on larger networks.The main work of this thesis consists of the following aspects: 1) A binary particle swarm optimization algorithm based on velocity and roulette strategy VP-bPSO is proposed towards the precocity problem of PSO when applied to community detection. 2) Aiming at the deficiency of VP-bPSO in the blindness of initialization and the selection of optimization direction, an approach, denoted as FU-VP-bPSO, for community discovery by combining the VP-bPSO algorithm and Fast Unfolding algorithm is proposed. It introduces the concepts of elite swarm and ordinary swarm of particle swarm. The variation of genetic algorithm is applied in generating Elite swarm and Fast Unfolding algorithm is applied in guiding the initialization and optimization direction of algorithm, which improve the performance of the proposed algorithm. 3) VP-bPSO is further improved for the problem of the division of overlapping community, where the roulette selection is processed more than one time at the stage of position resetting and the extended modularity is applied for overlapping community detection. 4) Aiming at the problem of large-scale parallelization of VP-bPSO, a parallel VP-bPSO algorithm based on MapReduce is designed. It introduces the concept of sub particle swarm. The parallel operation of the sub particle swarm is realized in the Hadoopplatform, where the local optimal solution is updated in the sub particle swarm to accelerate the convergence rate of the whole particle swarm which improves the efficiency of the algorithm. 5) To solve the iteration problem of MapReduce framework, Redis is introduced to improve the data sharing mechanism so that the repeated restart of MapReduce task is avoided and the efficiency of the algorithm is improved. Finally, the effectiveness of the proposed algorithms is validated by experiments.