Extracting Frequent Connected Subgraphs from Large Graph Sets

Mining frequent patterns from datasets is one of the key success of data mining research. Currently, most of the studies focus on the data sets in which the elements are independent, such as the items in the marketing basket. However, the objects in the real world often have close relationship with each other. How to extract frequent patterns from these relations is the objective of this paper. The authors use graphs to model the relations, and select a simple type for analysis. Combining the graph theory and algorithms to generate frequent patterns, a new algorithm called Topology, which can mine these graphs efficiently, has been proposed. The performance of the algorithm is evaluated by doing experiments with synthetic datasets and real data. The experimental results show that Topology can do the job well. At the end of this paper, the potential improvement is mentioned. This work was supported by the National Natural Science Foundation of China (Grant Nos.69933030 and 60303008) and the National High-Technology Development 863 Program of China (Grant No.2002AA4Z3430). Wei Wang received the B.S. degree in computer science in 1992 from Shandong University, the Ph.D. degree in computer science in 1998 from Fudan University, respectively. He is now a professor in Department of Computing and Information Technology, Fudan University. His research interests include database, data warehouse, data mining. Qing-Qing Yuan received the B.S., the M.S. degrees in computer science in 2000 from Fudan University, in 2003, respectively. Now she is a Ph.D. candidate in Department of Computer Science, University of California. Santa BarBara. Her research interests include database and data mining. Hao-Feng Zhou received the B.S. degree in computer science in 1997 from Shanghai University, the M.S. degree and the Ph.D. degree in computer science in 2000 and in 2003, from Fudan University, respectively. His research interests include database and data mining. Ming-Sheng Hong received the B.S. degree in computer science in 2002 from Fudan University. Now she is a Ph.D. candidate in Department of Computer Science, University of Connell. His research interests include database and data mining. Bai-Le Shi received the B.S. degree in mathematics in 1957 from Peking University. He is a professor in Department of Computing and Information Technology, Fudan University. He is also director of the Shanghai (International) Database Research Center. His research interests include database, data warehouse and digital library.