Mining evolving patterns of connection subgraphs over evolving graphs

This paper investigates into the problem of mining evolving graphs, i.e. graphs changing over time. It focuses on mining evolving pattern set of connection subgraphs between given vertices in an evolving graph. A similarity function of connection subgraphs and the algorithm to compute it have been presented. Based on this similarity function, a dynamic programming algorithm with polynomial time complexity is proposed to find evolving pattern set. The experimental results on synthetic datasets show that the proposed algorithm has low error rate and high efficiency. The mining results on real datasets illustrate that the mining results have practical significance in real applications.