Research On Dynamic Graph Clustering Algorithm

Dynamic data is different from traditional static data,and there is a time dimension in dynamic data.In actual application scenario,the number of data and its characteristics will evolve with time.This also leads to the fact that static clustering can not be simply used to analyze dynamic data.Clustering dynamic data is called evolutionary clustering.How to use historical data effectively has always been a difficult problem in evolutionary clustering(dynamic clustering).Most of the existing evolutionary clustering algorithms are limited by the temporal smoothness hypothesis,and the inherent connection of dynamic data is not taken into account from the data itself.This paper transforms the evolutionary clustering problem into the clustering problem on the dynamic graph,and constructs the dynamic graph using the data driven way,and provides a more robust evolutionary clustering analysis method.At present,the research of evolutionary clustering has attracted a lot of researchers'attention.However,clustering is a category of unsupervised learning and lacks the guidance of label information,most traditional methods are based on temporal smoothing hypothesis.This leads to the following three problems:(1)At present,the dynamic data are becoming more and more complex.Many data will exhibit bifurcation evolution when evolving.Traditional methods cannot deal with this problem well.(2)The temporal smoothness hypothesis constrains the current data and recent history.However,the time difference between current data and recent history is quite different in different data sets.Temporal smoothness hypothesis can only process these data equally.This makes the traditional method difficult to get better results when dealing with data with large time delay.(3)Because of the evolution characteristics of dynamic data,the number of data samples will change at different times.And as time goes on,the amount of data will also increase greatly,resulting in high computational complexity.Traditional evolutionary clustering method is often difficult to solve this problem.To solve these problems,we propose three clustering algorithms on dynamic graph.The main research works and achievements obtained in this paper are as follows:(1)A dynamic graph clustering algorithm based on evolutionary tree is proposed to deal with the bifurcation characteristics of data during evolution.Through the design of tree smoothing,the dynamic evolutionary tree structure is obtained by measuring the covariance distance of the graph,and the bifurcation phenomenon in the evolutionary clustering is handled well.The experiments are carried out on multiple real data sets,and the better clustering results are obtained than the other methods.(2)A dynamic graph clustering algorithm based on evolutionary graph is proposed,which uses data driven graph structure to describe the complex evolution structure of data.It solves the problem that data can not be smoothed due to large span of time in the evolution of data.By using the neighbor relation of dynamic graph to restrict the current time data,the structure smoothness of the dynamic graph is used to solve the optimization target,and the discontinuous problem of time slice is dealt with well.Experiments on several real datasets show that the method not only improves the quality of dynamic clustering,but also can discover the evolution rules of data.(3)An evolutionary graph clustering algorithm based on graph kernels is proposed to deal with the dramatic changes of nodes and reduce the time complexity of dynamic graph clustering algorithm.By using the graph kernel to construct the evolutionary graph,the effect on the dynamic graph clustering data is greatly reduced.The time and space complexity of the dynamic clustering algorithm is greatly reduced,and an efficient method to deal with the sharp changes in the number of nodes is provided.Experimental results on real datasets show that the proposed algorithm outperforms similar algorithms in terms of clustering quality and computation cost.