A Dynamic Community Detection Algorithm Based On Incremental Clustering

With the large-scale growth of data,the research of community detection algorithm has become a hot topic and challenge in the complex network science.Detecting communities in the network can help people analyze the network structure and understand the key information hidden in the network structure.In the past ten years,the community detection algorithm in static network has made great progress.However,in real life,the network is dynamic network,and the network changes slowly with time.In dynamic network,the detection and analysis of the community can help people understand the structure of the network and analyze the development trend of the network,which is of great significance to real life.However,the traditional static community detection algorithm ignores the temporal evolution relationship between the networks,so the communities obtained are difficult to explain and further analyze.Evolutionary clustering algorithm needs to balance the possible contradictory indexes on the network at the previous time and the current time,which leads to the low efficiency of the algorithm.Some incremental clustering algorithms have some losses in the process of updating communities.How to detect community efficiently and accurately in dynamic network has become a difficult problem in dynamic network analysis.Most of the existing dynamic community detection algorithms can’t meet the needs of efficiency and accuracy at the same time.In this paper,based on weak clique and incremental clustering we propose a dynamic community detection algorithm named DWCI.Firstly,the weak-clique identifying method and the weak-clique merging method of the static community detection algorithm W-CPM are improved to improve the accuracy of W-CPM algorithm.Then,based on the incremental clustering algorithm,we define the core of weak-clique and the set of disturbed nodes,and the set of disturbed nodes is determined by verifying the core of weak-clique at the current time and calculating the relationship between the incremental nodes and the core of weak-clique.Finally,we recalculate the community of the disturbed node set.Through the analysis of time complexity,it is found that DWCI algorithm has the characteristics of incremental clustering that is high efficiency.In this paper,experiments are carried out on synthetic data and real networks.The algorithm proposed in this paper is compared with the classical evolutionary clustering algorithm Facetnet,incremental clustering algorithm IC,d Louvain-ΔS in terms of accuracy and running time.In the DBLP network,the running time of DWCI is lower than other algorithms,whice is about 6 times shorter than d Louvain-ΔS and about 30% shorter than IC.At this network the running time of Facenet is too long to compare.Modularity of DWCI is significantly higher than IC,which is at the same level as d Louvain-ΔS.In Cellphone network,the running time of DWCI is 1-2 times shorter than d Louvain-ΔS,and 100 times shorter than Facetnet.Modularity of DWCI is slightly lower than Facetnet,but higher than IC and d Louvain-ΔS.In synthetic networks,when the number of nodes is more than 10000,the running time of DWCI is the same as that of IC,which is 3-4 times shorter than d Louvain-ΔS.At this time,the running time of Facenet is too long to compare.Through experimental verification,it is found that the time efficiency of DWCI is significantly higher than that of Facenet and d Louvain-ΔS,which is equivalent to that of IC,and has the characteristics of incremental clustering that is high time efficiency.In terms of accuracy,DWCI is significantly higher than IC,and in most cases higher than d Louvain-ΔS.All in all,the algorithm DWCI proposed in this paper is a dynamic community detection algorithm with high time efficiency and relatively good accuracy.