Research On Community Found Algorithm Based On Parrallel K-Means Clustering

The research on complex network community discovery algorithm not only has important theoretical significance, but also has wide application prospects, for analyzing the complex network’s topology, understanding the complex network’s function, finding the hidden rules in the complex network, and predicting complex network’s behavior. Now, the algorithm has been widely used in the analysis of the social network, such as the identification of terrorist organizations and the management of organizational structure.In recent years, community discovery of the complex network has been widely concerned, and many new algorithms spring up. But, there are also many problems exist in the current algorithms. For example, a better division effect algorithm is always with a high time complexity, or a better division speed algorithm is always with a poor quality.For the shortcomings of the K-Means algorithm, this thesis combines with other algorithms’characteristics, adds the gain function,in condition of the uncertain K value, choose the cluster centers based on the furthest distance principle, and choose the cluster elements based on the closest distance principle, to improve the divided accuracy. Then this thesis combines with the parallel technology,changes the original serial K-Means algorithm into a parallel K-Means algorithm based on GPU, and uses the CUDA of NVIDIA as the computing platform to implement the parallel algorithms.When applied in community found of actual complex network, this algorithm uses the associate degree principle to improve the algorithm, and and uses some relevant network dats sets to compare the serial algorithm with the parallel algorithm. The expriments show that two algorithms have the same result of division, but the parallel algorithm much faster than the serial algorithm clearly.The K-Means community found algorithm combined with parallel technology can quickly and accurately locate community structure on the network, and provide effective help for the researchers to analyze the community structure, and can use some similar means of parallel processing to analyse and optimize other community found algorithm.