Research On The Method For Tracing The Source Of A Local Community In Dynamic Networks

With the rapid development of the information technology,a large number of dynamic networks have been formed which are constantly changing over time,and these networks contain rich information.As an important attribute of network,community evolves with the change of network.Analyzing the evolution process of communities can effectively help mine the information contained in dynamic networks,and can be used for network anomaly detection,information dissemination control,marketing strategy development and other practical applications.Existing studies describe the evolution of all communities in networks from a global perspective.However,in some application scenarios,people only care about the formation process of a specific community after a period of time,and do not pay attention to other communities in the network.At present,there is a lack of research on tracing the formation process of a designated community in a dynamic network.This paper focuses on the evolution point identification and community tracking in the process of community evolution analysis.The main work includes:Firstly,for the problem of large evolution point deviation caused by fixed time length,a method of evolution point identification based on truth-false community classifier was proposed.The classifier is trained for judging whether a node subset is a community of a graph snapshot or not.The classification algorithm uses the decision tree technology,and the features for classification include internal cohesion degree,external coupling degree and local modularity.The evolution-point identifying method is proposed based on the trained classifier.As the graph evolves,the method continuously uses the classifier to predict whether the subset of nodes contained in the interested community is still a community of the newest graph.Whenever the answer is negative,an evolutionary event is presumed to have occurred and a new evolution-point is generated.Experimental results show that our proposed method effectively reduce the deviation of evolution-point identification.Secondly,for the low accuracy and poor quality of community tracking,this paper proposes a community tracking method based on multi-node local community discovery.The goal of community tracking is to find out which communities in the previous evolution-point form the designated community.In this paper,the community tracking problem is transformed into the local community discovery problem of multi-seed nodes on the network at the previous evolution-point.Since the location of the seed node in the community greatly affects the accuracy of local community discovery,the method in this paper find out the community core nodes associated with each seed node,and then independently discovers each local community based on each core node.To deal with the intersection among multiple communities,these communities are merged into a subgraph,and the community detection is performed on the subgraph to get the final community tracking result.The experimental results show that the accuracy and quslity of the community tracking method in this paper have been greatly improved.Thirdly,a system for tracing the source of a local community in dynamic networks is designed and implemented based on the previous two parts.The system can trace the formation process of user-specified community in a dynamic network and visually display it.