Evolution pattern discovery in dynamic networks

摘要

The majority of recent graph mining approaches have focused on analyzing static interaction networks, neglecting the fact that most real-world networks are dynamic in nature. In this paper, we define a framework to find evolution patterns which are regular in dynamic networks. These patterns can be used to characterize the local properties of dynamic networks, and predict future behavior. In our framework, different snapshots of the dynamic network are transformed to a summary graph, and then occurrence rules are discovered for searching for evolution patterns. We also take noise into account by finding quasi-patterns instead of only precise ones. We analyze the time- and space-complexity of the approach. Experiments on synthetic dynamic networks and real-world dynamic networks show that our approach is efficient, so it can be used to find patterns in large scale networks with many snapshots. Furthermore, we obtain meaningful and interesting evolution patterns from social dynamic networks.