Parallel Algorithm Research Of Community Detection In Large-scale Complex Network On GPU

The community structure is one of the most common and typical topology features in the complex network.Dividing the networks into communities correctly and efficiently is the premise of effective analysis and use of these networks. Existed Algorithm of Community Detection is difficult to meet the needs of analysis of complex network. Due to the speed limit of calculation is only suitable for the network of small-scale societies.In recent years, rapid development of GPU (graphics processing unit), high-speed floating-point capability, parallel computing and programmable function provides a good computing platform for general purpose computing. The GPU-based parallel computing has been successfully applied in the field of medical imaging, computational fluid dynamics, and environmental science and so on. In this paper, using CUDA (Compute Unified Device Architecture) to study the algorithm of for large-scale complex networks, in order to improve tht computing speed, the main work I have finished as follows:(l)For the problem of calculation of betweenness in the algorithm of GN, putting forward a parallel algorithm of betweenness on GPU. Implement this algorithm and proved that this algorithm has speedup of10-50×compared with CPU implementations, to prepare for GPU-based improvements for the GN algorithm.(2) Introducing the algorithm of Blondel based on modularity optimization, analyzing tha part of data-parallel of th algorithm,that is calculating the increment of modularity of each node and the community than the neighbor node of this node.Due to the calculation each neighbor node have no correlation,that suitable for computing on GPU. Therefore proposing a GPU-based parallel algorithm on the basis of this algorithm, the algorithm has been verified by experiment that has speedup of20%-50%. (3)Intrducing the algorithm of community detection based on simulated annealing, and implementing this algorithm.Due to the algorithm of simulated annealing has a natural parallel nature,this paper using the fine-grained parallel features of the GPU,putting forward a parallel algorithm of community detection based simulated anneling on GPU. And verfied that the improved algorithm has speedup of2-5x.