A Community Detection Algorithm Based On The Louvain Algorithm

Network science provides a series of tools for the analysis and study of complex systems and is considered as an interdisciplinary research platform.The community structure in complex network is correlated closely with the functional and dynamic features of the system,and it turns into the vital point of the analysis of networks.With the development of research on community detection algorithms in the recent decade,a lot of research achievements have been reached.But there are still some drawbacks.First,an evaluation method of the efficiency of practical application of a community detection algorithm is still lacking.In most cases,the mean value of repeated experiments is used to evaluate the performance.However,the mean value can only show the average performance of an algorithm,rather than the efficiency in empirical application.Second,there is randomness in the result of community detection algorithms.To get an accurate and reasonable partition from several different partitions obtained by repeated experiments to analyze the given network,a fast algorithm is still lacking.To solve these problems,in this paper,a new evaluation measure is proposed to show the efficiency of an algorithm in practical applications,a community detection algorithm with higher efficiency is proposed,the cause of the difference of partitions is analyzed,and an algorithm to find accurate and reasonable partition from different partitions is also proposed.The main research achievements and academic contributions are as follows:1)The Self-adaptive Random Neighbor Louvain algorithm based on the principle of small probability event is proposed.The algorithm randomly choose several neighbors to calculate the modularity increment,so as to decrease the modularity increment calculating times to accelerate the algorithm.The number of the neighbors to choose is derived by the principle of small probability events.The algorithm exploits information of community structure from intermediate result to estimate the measure used in the calculation.The algorithm is tested on LFR benchmarks and empirical networks,comparing with the original Louvain algorithm and the Random Neighbor Louvain algorithm.Our SARNL algorithm can maintain the modularity and the stability of the result and increase the running speed.The speedup ratio can reach over100% on the Youtube network which contains over 1.1 million nodes.2)The equivalent computing time is proposed.Based on the practical using environment of community detection algorithms,the equivalent computing time is proposed as an evaluation measure of the efficiency of practical application in this dissertation.Evaluated by this new measure,our SARNL algorithm can increase the efficiency in most networks.In empirical networks,the speedup ratio of SARNL can reach over 4 times.3)The noisy community structure model is proposed.It is pointed out that the edges in the network can be considered as information edges and noise edges. The information edges can help the community detection algorithm to find the ground-truth of the network,while the noise edges can disturb the algorithm so that the ground-truth cannot be discovered accurately and stably.4)The Network Denoising algorithm exploiting Partitions is proposed.Based on the noisy community structure model,the Network Denoising algorithm calculates the fraction of membership of the two vertices of an edge in a set of partitions and update the weight of this edge.The algorithm distinguishes the information edges and the noise edges by their updated weight and filtering the noise edges so as to obtain the network structure which only contains information edges.The NDP algorithm is tested on the LFR benchmarks and empirical networks by combining with the SARNL algorithm.The results show that the Network Denoising algorithm can effectively increase the accuracy,overcome the limitation of modularity.Compared with the Consensus Clustering algorithm,the NDP algorithm can not only obtain a more accurate partition,but also decrease the runtime.The time complexity of the NDP algorithm is O(m),which is dramatically lower than that of the Consensus Clustering algorithm,which is considered to be O(n~2).