Algorithm For Dynamic Community Detection Based On Local Modularity

Complex systems slowly changing with time can be modeled as an abstract dynamic network. Due to the widely range of application of dynamic network in the field of sociology, bioinformatics, physics, computer science, etc, it has get more and more attention of researchers of various disciplines and various industries. In recent years, dynamic network become a hot research field, and the meaningful dynamic community structure is a common and important feature in dynamic network.Current algorithm for dynamic community detection is mainly based on the theoretical knowledge associated with static detection. Dynamic community detection algorithm based on maximizing Q function has a problem of resolution that small communities are often combined into a large community in order to obtain better modularity. On the other hand, most of the dynamic community detection methods need to set several parameters or thresholds, which require a certain degree of prior knowledge of networks. Moreover, existing dynamic community detection methods cannot identify important topological feature in communities(e.g. overlapping structure). In this paper, we propose a dynamic network community detection algorithm based on local modularity for addressing limitations above. This algorithm can find out dynamic communities with overlapping structures. The proposed algorithm for dynamic community detection based on an evolutionary clustering framework and local modularity adopts a strategy that is transforming the community detection in the whole network into the bottom-up cohesion problem. It is self-adaptive to the density of networks changing in size or uneven in structure. The algorithm calculates the random walk behavior characteristic of each node to enhance the resolution of un-weighted network. Additionally, we use cost embedding technique based on evolutionary clustering framework to balance topological characteristics and historical information, thus detecting dynamic patterns in community evolution. It is worth noting that only the balancing factor needs to be determined in the evolutionary cluster process, without prior knowledge of certain areas.We evaluate this algorithm using two real networks, including Drosophila melanogaster network and DBLP network. Experimental results show that the extended modularity (EQ) increases by 15% when comparing this algorithm with evolution and local-first based methods for the same problem, indicating that the detection result in the Drosophila melanogaster network has been improved significantly using our algorithm. Furthermore, the dynamic evolutionary process of scientific teams in the DBLP network can be effectively depicted. Therefore, our proposed algorithm can not only be applied to networks without prior knowledge of community structures, it can also detect certain meaningful small-scale communities and overlapping structures between them.