An Algorithm For Dynamic Community Detection Based On Incremental Clustering

As a tool to portray the complex system of the real world,complex networks have been widely used in sociology,biology and other fields.However,the real complex system slowly changes with time.Modeling the system at different times and sorting it according to time can get a dynamic network.The community is an important feature of the network.Detecting communities for dynamic networks can make people better understand the characteristics of the network and its evolution.Moreover,it has important theoretical and practical significance.However,if the traditional clustering algorithm is used,the relationship between networks at adjacent moments will be ignored.The evolutionary clustering algorithm has high accuracy,but it is limited by time complexity and not suitable for large-scale networks.Incremental clustering algorithm utilizes the slow change of the dynamic networks.Based on the communities found at the previous moment,the algorithm avoids the repartitioning of all nodes in the network.It not only effectively reduces the time complexity,but also ensures the consistency of the results of the neighboring time.Based on incremental clustering and connection density,we propose a community detection algorithm for dynamic networks named IPSCAN.Firstly,according to the influence of the addition and deletion of edges in the dynamic network on the structural similarity and similarity degree of nodes,the area affected by the edge update is analyzed,and the set of incremental nodes is redefined.Then,the nodes in the incremental nodes set are divided into core nodes and non-core nodes according to the similarity degree.When processing a core node added at a certain moment,an attempt is made to expand from this node and determine whether to generate a new community,overcoming the defects of IC and other incremental algorithms which have a fixed number of communities and cannot detect newly emerging communities.Through the analysis of the time complexity,the IPSCAN algorithm has the characteristics of high efficiency than some of the incremental algorithms.The algorithm proposed in this paper is tested on synthetic datasets and real datasets.The performance of the algorithm is verified in terms of accuracy and time complexity,and compared with the evolutionary clustering algorithm Facetnet,incremental clustering algorithms IC and DABP.For example,on the real dynamic network dataset Football,the modularity of IPSCAN algorithm results is 5% higher than the Facetnet,12% higher than the IC,and 11% higher than the DABP.The result on the large-scale real data set DBLP is shown that the modularity of the community results obtained by IPSCAN is 11% higher than that of the DABP and significantly higher than that of the IC.Moreover,the IPSCAN algorithm runs within 6s at each moment,while the DABP algorithm runs up to 67 s.The experimental results show that the accuracy of the proposed algorithm is higher than the IC algorithm.While the DABP algorithm can find new communities,the accuracy is lower than the IPSCAN algorithm,and the time efficiency is worse than the IPSCAN algorithm.The algorithm proposed in this paper not only has good community detection capabilities,but also has the advantage of incremental algorithm,and can be used for community detection of large-scale dynamic networks.The algorithm proposed in this paper has good community detection capabilities,and can discover emerging communities.Moreover,it has the advantage of incremental algorithms and can be used for community discovery of large-scale dynamic networks.