| With the rapid development of Internet,the data on it is growing at an explosive rate.The size of various networks made up of users on the Internet grows rapidly,declaring that the era of large-scale network has come.When analyzing the large-scale network,we hope to have a fast,efficient way to analyze the community evolution of a complex network.Although a lot of work has been done on community detection in static networks in the past,researchers pay relatively less attention to the community detection in dynamic networks.And many shortcomings emerge while applying the traditional algorithm for community detection in static networks to dynamic networks.To address the issue about community detection in the dynamic network,in this paper we propose a new dynamic community detection algorithm based on incremental identification according to a vertex-based metric called permanence.The algorithm adopts the hypothesis that the community evolution is smooth in a few time steps,and we incrementally analyze the community ownership of partial vertices,so as to avoid the reassignment of all the vertices in the network to their respective communities.In addition,we propose a new metrics called evolution strength to measure the error probably caused by incrementally assigning the community ownership or the abrupt change of network structure.Meanwhile,due to the lack of dynamic network data with ground-truth structure and limitation of existing synthetic methods,we propose a novel method for generating synthetic data of dynamic network with ground-truth structure,which defines evolution events and evolution rate of events,to obtain more realistic synthetic data.Besides,in order to provide a way to research community evolution in the large-scale dynamic network,we implement the dynamic community detection algorithm based on a parallel computing framework named Spark.Through experiments on dynamic network datasets of various scale,we analyze and verify our distributed methods. |
PDF Full Text Request