Design Of Parallel Louvain Method For Community Detection Algorithm Based On Graph Coloring

With the rapid development of information technology, in the real world is full of all kinds of complex networks, Such as communication networks and transportation networks. Complex network has important theory significance and broad application prospects of many fields, including computer science, sociology, biology, etc. As the research moves along, the reserachers have found an important characteristic that in complex networks have stronger community structure. So the studies of communtiy detection algorithm allow us to better understand mathematical meaning and physical characteristics of complex networks.In the past ten years the study of community detection technology has been gained widely attention and made a lot of research results. But all present algorithm of community detection are sequential, and generally has high computation complexity limitation is only suitable to small-scale networks. As the complex network scale increasing, the existing algorithms are difficult to meet the requirement to analysis large scale complex network while unable to meet the demand of fast and accurate processing. So community detection in large graph has brought great challenges to academia and industry. Parallel computing technology is currently one of the most feasible accelerating technology for improve the computational efficiency, thus parallel communtiy detection algorithm has great significance. In the process of research, how to allocate task in each processor is the key factor of parallel communtiy detection algorithm performance. Existing algorithm based on statically graph partitioning technology, parallel computing can not adjust according to community merge operation in time, resulting unbalance load and computiational efficiency to reduce. Meanwhile, the current algorithms do not pay attention to the communtiy characteristices and the relationship; reduce the accuracy of parallel community detection algorithm.To cure the above problems, we take the graph coloring as entry point to procesed parallel communtiy detection based on Louvain algorithm, named P-LM. In order to improve the efficiency and the accuracy of parallel community detection algorithm.It makes the following works:1. Propose a parallel task allocation algorithm based on distance-1 graph coloring algorithm; the purpose is to keep the computing characteristics. Overcome the information loss caused by graph partition methods. Guarantee the independence of data and avoid the concurrent decision in the process of parallel computing.2. Propose a vertex status update mechanism base on modularity. Update the communtiy structure changes and effectively improve the convergence speed of the algorithm.3. Propose a dynamic load adjustment method based on vertex degree, this method according to the vertex degree to adjustment calculation, implement load balancing.4. Propose a complex network analysis tool based on Open MP shared memory programming model, according to the parallel LM algorithm analyzed large-scale graph set.Finally, this paper use the real large-scale complex networks of different graph sets as test data, througth test the modularity and running time of the algorithm, verify the proposed parallel community detection algorithm that the effectiveness about the quality and computational efficiency.