A local dynamic method for tracking communities and their evolution in dynamic networks

摘要

The analysis of communities and their evolutionary behaviors in dynamic networks is a challenging topic. Although a growing body of work on this topic is emerging, there are few methods which can reveal and track meaningful communities over time and can also deal with large networks efficiently. In this paper, we propose a method to track dynamic communities and their evolutionary behaviors. The main idea behind our method is to discover dynamic communities by exploring the local views of nodes that change. Moreover, based on the discovered dynamic communities, the global community structure can be derived by updating the historical community structure and the evolutionary behaviors of communities can also be tracked. To discover the dynamic communities, we apply the technique of approximate personalized PageRank vector; to track the evolutionary behaviors of the communities, we introduce a partial evolutionary graph. We compare the proposed method with several existing methods by performing experiments on nine synthetic networks and one real network. The experimental results show that the proposed method performs well on discovering communities as well as tracking their evolution in dynamic networks, and spends much less running time than the existing methods.