Research On Improvement Of Louvain Community Detection Algorithm

With the progress of society and technology,and the continuous development of complex network,the algorithms and applications of community detection are gradually extensive.Louvain community detection algorithm is a community detection algorithm based on modularity,which has relatively reliable community detection results and high efficiency.However,due to the continuous development and change of real world data,the traditional Louvain community detection algorithm is limited in its application.Firstly,according to the characteristics of the graph data structure,the redundant calculation can be reduced and the calculation time of Louvain community detection algorithm can be further accelerated.Secondly,Louvain community detection algorithm is a greedy algorithm based on module degree.Although module degree is an indicator to evaluate the quality of a community detection,blindly improving the module degree of the full map does not mean that it can obtain better results in subsequent downstream tasks or applications after the community detection result.Finally,the Louvain community detection algorithm is aimed at the connected graph,which can not be effectively applied to the disconnected graph,so that the Louvain community detection algorithm is limited in the application scenarios.Aiming at the above problems,this paper carried out the improvement of Louvain community detection algorithm.The main work content is summarized as follows in this paper:(1)According to the characteristics of graph data structure,combining calculation process of the Louvain community detection algorithm,pruning method is proposed.The experimental results show that the pruning strategy improves the calculation speed of Louvain community detection algorithm.(2)Use the heuristic method to optimize the Louvain the division of community detection algorithm as a result,and revise the results in parts of the community divided edge nodes,and set the downstream tasks to improve the effect evaluation.The experimental results show that the evaluation indexes in the downstream task are improved when the modularity is basically unchanged.(3)The WCC(Weakly Connected Components)algorithm is first implemented on the unconnected graphs.The WCC algorithm is optimized so that it can run on large scale graph data to find and divide the connected components of the unconnected graph.After that,the unconnected graph is reconstructed again,and the Open MP parallel method based on shared memory is adopted to give each connected component to different threads in parallel using the improved Louvain community detection algorithm.The experimental results show that the parallel algorithm has a good acceleration effect in the case of uniform data distribution,and can also play a certain acceleration effect in the case of extreme data.