Research On Evolutionary Clustering Based On Reference Points

With the rapid development of the Internet and the ability to collect data,there are more and more time-evolving data in real life and we call this type of data for evolutionary data.Recently,the clustering problem of evolutionary data attracts many researchers' interest.In general,evolutionary clustering has two requirements:1)the clustering structure found at each time step should be as good as possible to divide the snapshot data of the current time;2)the clustering structure found at each time step should keep temporal smoothness,that is,the clustering structure found at the current time step can not deviate drastically compared with previous ones.Evolutionary data clustering has a very broad application background and the research about evolutionary data is of important significance.This paper studies evolutionary clustering from the perspective of leader nodes and reference points.The main contents of this paper include three aspects.(1)Inspired by the static community discovery algorithm(i.e.Top Leaders algorithm),we propose an evolutionary community discovery algorithm based on the leader nodes,named EvoLeaders.First,we use the time-based update strategy to get the initial leader nodes at each time step.By keeping the temporal smoothness of the leader nodes,the communities detected at each time step could reflect a valuable partition for the current snapshot,while simultaneously do not shift too much from the previous one.Then,the community quality could be improved through a split-merge operation.The experimental results of the two real datasets show that the EvoLeaders algorithm works better than the Top Leaders algorithm.This work demonstrates the feasibility of dealing with evolutionary community discovery problem from the perspective of leader nodes.(2)The major weakness of Top Leaders algorithm is that the number of leader nodes should be set manually or obtained from other algorithms.According to the relationship between each node in the network and its neighbor nodes,and the degree of overlap of nodes' common neighbors,we improve the Top Leaders algorithm and propose the AutoLeaders algorithm which could automatically discover the number of communities.Experimental results on three classical datasets show that the AutoLeaders algorithm not only can find the reasonable number of communities,but also discovers a reasonable community structure.Further,based on two temporal smoothness strategies,we propose a new solution for discovering communities in dynamic networks,i.e.the EvoAutoLeaders algorithm.The results on the two real-world datasets show that the EvoAutoLeaders algorithm works well.(3)We deal with evolutionary clustering from the perspective of reference points.First,we introduce three strategies to define the reference point and to calculate the distance between the reference point and an individual;then,based on the r-dominance relation and multi-objective evolutionary algorithm,we propose an evolutionary clustering algorithm(i.e.,rEvoC algorithm).Experimental results show that compared with the classical algorithm,rEvoC algorithm is more suitable to cluster evolutionary data,and can achieve better results.In general,we deal with evolutionary data clustering problem from the perspective of leader nodes and reference points,and we prove its effectiveness through experiments,and the performance is better than the classical algorithm.The work of this paper has some reference value for the research of evolutionary community discovery and evolutionary clustering.