Trong bài báo này, các tác giả giới thiệu một thuật toán hiệu quả cho việc tìm kiếm các đồ thị con trong một cơ sở dữ liệu đồ thị, thuật toán FSG. Thuật toán này dựa trên tư tưởng của thuật toán Apriori nhưng pha sinh ứng viên đã được cải tiến để phù hợp với dữ liệu đồ thị. Chúng tôi đã cài đặt thuật toán này theo kỹ thuật lập trình hướng đối tượng bằng ngôn ngữ Java. | JOURNAL OF SCIENCE OF HNUE Natural Sci. 2012 Vol. 57 No. 3 pp. 17-30 MỘT THUẬT TOÁN KHAI PHÁ ĐỒ THỊ CON PHỔ BIẾN TRONG DỮ LIỆU ĐỒ THỊ Giang Thành Trung Trường Đại học Tây Bắc Trần Đăng Hưng Trường Đại học Sư phạm Hà Nội E-mail hungtd@ Tóm tắt. Bài toán tìm các cấu trúc con lặp lại nhiều lần trong dữ liệu có cấu trúc được ứng dụng trong rất nhiều lĩnh vực. Nhiều thuật toán khác nhau đã được đề xuất. Tuy nhiên do sự phức tạp của dữ liệu có cấu trúc nên các thuật toán thường gặp phải các thách thức về tính toán. Trong bài báo này chúng tôi giới thiệu một thuật toán hiệu quả cho việc tìm kiếm các đồ thị con trong một cơ sở dữ liệu đồ thị thuật toán FSG. Thuật toán này dựa trên tư tưởng của thuật toán Apriori nhưng pha sinh ứng viên đã được cải tiến để phù hợp với dữ liệu đồ thị. Chúng tôi đã cài đặt thuật toán này theo kỹ thuật lập trình hướng đối tượng bằng ngôn ngữ Java. Từ khóa Khai phá dữ liệu đồ thị con phổ biến Apriori FSG. 1. Mở đầu Khai phá các mẫu hình pattern lặp lại nhiều lần trong dữ liệu có cấu trúc như đồ thị cây thu hút được nhiều sự chú ý của các nhà nghiên cứu vì được ứng dụng trong nhiều lĩnh vực khác nhau 1-3 . Các mẫu hình lặp lại nhiều lần có thể giúp chúng ta hiểu sâu sắc hơn về mối quan hệ giữa các phần tử được mô hình hóa và đồng thời đây cũng là điểm khởi đầu cho các thuật toán khai phá dữ liệu cơ bản như phân cụm và phân lớp. Trong số các loại dữ liệu có cấu trúc đồ thị được sử dụng trong nhiều lĩnh vực nhất. Chẳng hạn trong sinh học đồ thị được dùng để mô tả mối quan hệ giữa các phần tử cơ bản protein gene RNA . Trong hóa học phân tích đồ thị được dùng để mô tả cấu trúc ba chiều của các phân tử. Ngoài ra đồ thị còn được dùng để biểu diễn dữ liệu web dữ liệu text vv. Cho đến nay có khá nhiều các thuật toán được đề xuất cho việc khai phá các đồ thị con phổ biến từ một cơ sở dữ liệu đồ thị CSDLĐT . Đồ thị con là một đồ thị thu được từ đồ thị ban đầu bằng cách loại bỏ một số đỉnh và một số cạnh. Đồ thị con phổ biến là đồ thị con có số
