Mining Frequent Patterns Based on Graph Theory

Mining the frequent pattern from data set is one of the key success stories of data mining research. Currently, most of the efforts are focused on the independent data such as the items in the marketing basket. However, the objects in the real world often have close relationship with each other. How to gain the frequent pattern from these relations is the objective of this paper. Graphs are used to model the relations, and a simple type is selected for analysis. Combining the graph-theory and algorithms to generate frequent patterns, two new algorithms are proposed. The first algorithm, named AMGM, is based on the Aproiri idea and makes use of matrix. For the second algorithm, a new structure SFP-tree and an algorithm, which can mine these simple graphs more efficiently, have been proposed. The performance of the algorithms is evaluated by experiments with synthetic datasets. The empirical results show that they both can do the job well, while SFP performs better than AMGM. Such algorithms are also applied in mining of the authoritative pages and communities on Web, which is useful for Web mining. At the end of the paper, the potential improvement is mentioned.