The Research Of Dynamic Network Community Detection Algorithm

Today, we live in an era that networks are everywhere, such as transportation network, mobile communications network, the Internet, online social networks and so on. These networks are so complex that we can’t directly extract useful information from them. Community detection, as an important technology of network analysis, can digs up nodes which have something in common and helps us to understand the network structure. So it has attracted the attention of many experts. As the change of real network and requirements of the people, the emphasis of the research in community detection is also changing. At early period, we research community detection algorithms applying to static small-scale network. Then, due to the increase of network scale, the scalability of algorithms is challenged, so people begin to research how to improve the efficiency of algorithm. Given the nature of the network dynamic change and to meet the requirements of accuracy and real-time, the research of dynamic network community detection algorithm begins to receive attention.In this paper, we introduce the community detection related technology and analyze some classic static and dynamic community detection algorithms and point their advantages and disadvantages, such as GN algorithm, KL algorithm, CMP algorithm, GraphScope algorithm, FaceNet algorithm, etc. Then we study the SHRINK-G algorithm which is based on greedy thought. The algorithm does not require users to provide parameters and visits only once for each node. Nevertheless, SHRINK-G algorithm’s treatment of community boundary point is not appropriate. So we improve the SHRINK-G and propose MSHRINK-G algorithm. Based on MSHRINK-G algorithm, we study community detection algorithms in dynamic network and put forward the DMSHRINK-G algorithm based on incremental processing.Experiment results in the LFR synthetic data sets and real data sets of different size show that the accuracy of MSHRINK-G algorithm has been greatly improved and DMSHRINK-G algorithm can accurately handle network changes and has a higher efficiency.