Frequent Subgraph Mining Algorithm On Historical Graph Data

Historical graph is an emerging data model for representing the evolving process of a dynamic graph.A historical graph can be regarded as a sequence of snapshots within a time interval.A historical graph evolves gradually,so graph snapshots with closer time intervals are usually highly similar to each other.A historical graph is changing with time,and it will produce graph snapshot continuously,so historical graph data is also a kind of streaming data.Frequent subgraph pattern mining is a widely studied problem in graph data mining.Its basic assumption is that frequent patterns are important.Frequent subgraph patterns contain many valuable information.This paper studies the frequent subgraph pattern mining algorithms on historical graph data for two scenarios.One scenario is mining frequent subgraph patterns in the historical snapshot sequence.The existing frequent subgraph mining algorithms do not perform efficiently on historical graphs because they overlook the similarity among snapshots in consecutive time points.Our algorithm speeds up frequent subgraph mining by leveraging the similarity among consecutive snapshots.Experiments on real-world data show that our algorithm outperforms the baseline algorithm by more than 40-fold speedup.Another scenario is mining frequent subgraph patterns on the historical graph data stream in a sliding window.In this thesis,an incremental mining algorithm is proposed.When the window state changes,we can get the frequent subgraph pattern set of the next state based on that of the current window state,instead of calculating the new state's frequent subgraph pattern set from scratch.Experiments show that the incremental mining algorithm proposed in this paper has significant advantages compared to mining the frequent subgraph pattern set from scratch in each window state.