Một thuật toán khai phá đồ thị con phổ biến trong dữ liệu đồ thị

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@hnue.edu.vn 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ố lần xuất hiện trong một CSDLĐT lớn hơn một ngưỡng cho trước. Hầu hết các thuật toán tìm đồ thị con phổ biến đều phải đối mặt với hai thách thức về tính toán: (1) đồ thị con đẳng cấu: xác định một đồ thị con 17 Giang Thành Trung và Trần Đăng Hưng của một đồ thị xuất hiện trong các đồ thị khác; (2) liệt kê một cách hiệu quả tất cả các đồ thị con phổ biến: vì số lượng các đồ thị con sẽ tăng lên theo kích thước của chính nó và kích thước của CSDLĐT, do vậy để làm việc được với các CSDLĐT lớn và có cấu trúc phức tạp cần phải có các thuật toán khai phá mẫu phổ biến hiệu quả. Nhìn chung, có thể chia các thuật toán khai phá đồ thị con phổ biến thành hai nhóm. Nhóm 1, gồm các thuật toán sử dụng chiến lược tìm kiếm theo chiều rộng theo kiểu thuật toán Apriori [4] để liệt kê các đồ thị con. Hai trong số các thuật toán này là AGM [5] và FSG [6]. AGM được đưa ra bởi Inokuchi và đồng nghiệp, FSG được đưa ra bởi Kuramochi và đồng nghiệp. Các thuật toán này đều dựa trên các đồ thị con phổ biến hiện có, rồi “sinh” ra các ứng viên tiếp theo bằng cách thêm cạnh hoặc đỉnh mới. Tại thời điểm xuất phát, thuật toán coi đồ thị con chỉ có 1 đỉnh hoặc 1 cạnh. Điểm khác nhau giữa các thuật toán này là phương thức “sinh” ra các ứng viên (candidate) mới từ các đồ thị con phổ biến hiện thời. Trong khi AGM sử dụng phương thức tạo ứng viên dựa trên các đỉnh và gia tăng kích thước của đồ thị con bằng cách thêm 1 đỉnh mới. FSG lựa chọn chiến lược tạo ứng viên dựa trên các cạnh để gia tăng kích thước của đồ thị con bằng cách thêm mới một cạnh. Chi tiết của các thuật toán này sẽ được chúng tôi trình bày trong các phần tiếp theo. Nhóm 2, gồm các thuật toán sử dụng chiến lược tìm kiếm theo chiều sâu để tìm các ứng viên đồ thị con phổ biến. Hai thuật toán tiêu biểu cho nhóm này là gSpan [7] và thuật toán của Borgelt [8]. Các thuật toán này đều tìm các đồ thị con liên thông phổ biến trong CSDLĐT nhưng khác nhau ở cách sinh ra các đồ thị con ứng viên. Trong gSpan [7], một đồ thị con phổ biến G được sử dụng để sinh ra các đồ thị con ứng viên G′ bằng cách chọn một đỉnh v thuộc G và thêm vào cạnh (v, w), trong đó w thuộc G hoặc không thuộc G. Ngược lại, thuật toán trình bày trong [8] không sinh ra các ứng viên mà thay vào đó là lưu giữ tất cả các đẳng cấu có thể có của đồ thị con phổ biến hiện thời. Trong bài báo này, chúng tôi đã tìm hiểu và trình bày một thuật toán hiệu quả của nhóm 1, thuật toán FSG [6]. Sau đó cài đặt và tiến hành thử nghiệm trên cơ sở dữ liệu đồ thị tự tạo, mỗi file dữ liệu mô tả một tập các đồ thị. Chương trình được chúng tôi cài đặt theo kỹ thuật lập trình hướng đối tượng với ngôn ngữ Java và có thể chạy được trên cả nền Windows và Linux. 2. Nội dung nghiên cứu 2.1. Một số khái niệm Để thuận lợi cho việc theo dõi các khái niệm về sau, trong phần này chúng tôi cung cấp một số khái niệm cơ bản, được dùng nhiều lần trong bài báo. Định nghĩa 2.1. Một đồ thị có nhãn G là một bộ gồm 5 phần tử G = (V,E,LV , LE , l) trong đó V là tập các đỉnh, E là tập các cạnh vô hướng, LV và LE là tập nhãn của các đỉnh và các cạnh, các ánh xạ l : V → LV và l : E → LE. 18 Một thuật toán khai phá đồ thị con phổ biến trong dữ liệu đồ thị Định nghĩa 2.2. Đồ thị có nhãn G = (V,E,LV , LE, l) là đồ thị con của đồ thị G′ = (V ′, E′, L′V , L ′ E, l ′) nếu và chỉ nếu: ◦V ⊆ V ′ ◦∀u ∈ V, (l(u) = l′(u)), ◦E ⊆ E′, ◦∀(u, v) ∈ E, (l(u, v) = l′(u, v)) Định nghĩa 2.3. Đồ thị có nhãn G = (V,E,LV , LE, l) là đẳng cấu với đồ thị G′ = (V ′, E′, L′V , L ′ E, l ′) khi và chỉ khi tồn tại một song ánh f : V → V ′ thỏa mãn: ◦∀u ∈ V, (l(u) = l′(f(u))), ◦∀u, v ∈ V, ((u, v) ∈ E ⇔ (f(u), f(v)) ∈ E′), ◦∀(u, v) ∈ E, (l(u, v) = l′(f(u), f(v))) Chúng ta nói rằng G đẳng cấu với G′ và ngược lại. Định nghĩa 2.4. Đồ thị có nhãn G là một đồ thị con đẳng cấu của đồ thị G′, kí hiệu G ⊆ G′ nếu và chỉ nếu tồn tại một đồ thị con G′′ của G′ mà G đẳng cấu với G′′. Định nghĩa 2.5. Cho tập các đồ thị D và một ngưỡng σ (0 < σ ≤ 1), độ hỗ trợ (support) của đồ thị G kí hiệu supG là tỉ số của số lượng đồ thị G′(G′ ∈ D) mà G đồ thị con đẳng cấu của G′ trên số lượng đồ thị có trong D: supG = |{G ′∈D|G′⊆G}| D Đồ thị G được gọi là đồ thị con phổ biến nếu và chỉ nếu supG ≥ σ Định nghĩa 2.6. Bài toán khai phá đồ thị con phổ biến là bài toán cho trước CSDLĐT D và ngưỡng hỗ trợ σ(0 < σ ≤ 1), tìm tất cả các đồ thị con phổ biến trong D. 2.2. Thuật toán FSG Thuật toán 2.1: fsg(D, σ) (Phát hiện các đồ thị con phổ biến) (1) F 1 ← xác định tất cả các đồ thị con phổ biến 1 cạnh trong D (2) F 2 ← xác định tất cả các đồ thị con phổ biến 2 cạnh trong D (3) k ← 3 (4) while F (k−1) 6= ∅ do (5) Ck ← fsg − gen(F (k−1)) (6) for each ứng viên Gk ∈ Ck do (7) Gk.count← 0 (8) for each giao dịch T ∈ D do (9) if ứng viên Gk nằm trong giao dịch T then (10) Gk.count← Gk.count+ 1 (11) F k ← Gk ∈ Ck|Gk.count ≥ σ|D| (12) k ← k + 1 (13) return F 1, F 2, . . . , F (k−2) Thuật toán FSG được trình bày trong Thuật toán 2.1. Hoạt động của thuật toán như sau: Đầu tiên thuật toán sẽ khởi tạo bằng cách liệt kê tất cả các đồ thị 1 và 2 cạnh phổ biến. Sau đó, dựa vào 2 bộ này, nó sẽ bắt đầu lặp việc tính toán 19 Giang Thành Trung và Trần Đăng Hưng chính. Trong mỗi lần lặp, đầu tiên nó tạo ra các đồ thị con ứng viên có kích thước lớn hơn các đồ thị ở bước trước 1 cạnh (dòng 5), điều này có nghĩa là thuật toán sẽ tăng kích thước của các đồ thị con phổ biến bằng cách thêm vào một cạnh tại một thời điểm. Tiếp theo, nó đếm tần suất của mỗi ứng viên đó (từ dòng 8-10) và chỉ giữ lại các ứng viên đáp ứng được độ hỗ trợ σ (dòng 11). Thuật toán chỉ dừng lại khi số lượng ứng viên được phát hiện bằng 0, nghĩa là không có đồ thị con phổ biến kích thước lớn hơn tại thời điểm đó. Để thực hiện Thuật toán 2.1 chúng ta cần xây dựng một số mô-đun hỗ trợ. Chúng tôi trình bày các mô-đun này trong các phần dưới đây. Thuật toán sinh ứng viên (fsg-gen) Sinh ứng viên là một mô-đun quan trọng trong thuật toán FSG, giúp xác định được các đồ thị con có kích thước lớn hơn từ các đồ thị con phổ biến được xác định từ bước trước trước đó. Từ tập ứng viên vừa tạo thuật toán tiếp tục loại bớt các ứng viên không phổ biến (có tần suất xuất hiện < σ|D|) và chỉ giữ lại những ứng viên phổ biến. Trong pha sinh ứng viên thuật toán sẽ tạo một tập các đồ thị con ứng viên kích thước k+1 từ các đồ thị con phổ biến kích thước k, các đồ thị con ứng viên kích thước k + 1 được tạo ra bằng cách ghép 2 đồ thị con phổ biến kích thước k. Hai đồ thị con đủ điều kiện để ghép chỉ khi chúng có cùng đồ thị con kích thước k–1 và 2 đồ thị con này được gọi là “nhân”. Các bước chính trong việc tạo ứng viên đó là: - Xác định nhân: Nhân giữa cặp đồ thị Gki và Gkj có thể xác định bằng cách tạo ra tất cả các đồ thị con kích thước k–1 của Gki bằng cách bỏ đi các cạnh và kiểm tra xem nó có phải đồ thị con của Gkj không. Nếu là đồ thị con của Gkj thì sẽ là nhân chung giữa 2 đồ thị. Lưu ý là giữa 2 đồ thị có thể có nhiều hơn 1 nhân. - Ghép nối : Tiến hành tạo tất cả các tự đẳng cấu có thể của nhân được lựa chọn rồi thực hiện nối 2 đồ thị Gki , Gkj để tạo ra đồ thị ứng viên kích thước k + 1 bằng cách từ nhân và các tự đẳng cấu của nhân ta ghép vào đó 2 cạnh, một của Gki và một của Gkj mà không nằm trong nhân. - Lược bớt : Sử dụng thuộc tính chặn dưới đóng của điều kiện hỗ trợ để loại bỏ một vài các ứng viên đã được tạo ra. Để làm được điều này, với mỗi ứng viên kích thước k+1, thuật toán sẽ đưa ra các đồ thị con kích thước k bằng cách bỏ bớt một cạnh của đồ thị ứng viên, sau đó kiểm tra xem các đồ thị con đó đã tồn tại trong F k hay chưa. Thuật toán tạo các ứng viên được thể hiện trong Thuật toán 2.2 gồm các bước dưới đây: - Bước 1: Với mỗi cặp đồ thị con phổ biến, thuật toán fsg-gen đi xác định tất cả các nhân chung giữa chúng. - Bước 2: Sau đó với mỗi nhân chung và cặp đồ thị con sẽ gọi đến thuật toán fsg-join để tạo ra tất cả các ứng viên kích thước k + 1 có thể. - Bước 3: Với mỗi ứng viên được tạo ra, đầu tiên thuật toán sẽ kiểm tra ứng 20 Một thuật toán khai phá đồ thị con phổ biến trong dữ liệu đồ thị viên đó đã có trong C(k+1) hay chưa. + Nếu chưa thì fsg-gen xác minh tất cả các đồ thị con k cạnh của nó xem có là đồ thị phổ biến hay không. + Nếu phổ biến, fsg-join sẽ chèn ứng viên được tạo ra vào C(k+1) + Nếu không nó sẽ loại bỏ ứng viên đó + Nếu đã có thì nó bỏ qua ứng viên đó. Thuật toán 2.2: fsg-gen(F k) (Thuật toán tạo ứng viên) (1) C(k+1) ← ∅ (2) for each cặp Gki , Gkj ∈ F k, i ≤ j mà cl(Gki ≤ Gkj ) do (3) H(k−1) ←H(k−1)| một nhân H(k−1) chung giữa Gki và Gkj (4) for each H(k−1) ∈ H(k−1) do (5) {B(k+1) là một tập các ứng viên dự kiến} (6) B(k+1) ← fsg − join(Gki , G k j ,H (k−1)) (7) for each G(k+1)j ∈ B(k+1) do (8) {kiểm tra thuộc tính chặn dưới đóng} (9) flag ← true (10) for each cạnh el ∈ G (k+1) j do (11) Hkl ← G (k+1) j − el (12) if Hkl liên thông và Hk 6∈ F k then (13) flag ← false (14) break (15) if flag = true then (16) C(k+1) ← C(k+1)∪G(k+1)j (17) return C(k+1) Trong thuật toán khởi tạo các đồ thị ứng viên có một bước quan trọng đó là ghép nối 2 đồ thị có chung nhân. Không giống như việc ghép nối các tập mục phổ biến, 2 tập mục phổ biến kích thước k khi được ghép nối sẽ chỉ dẫn đến duy nhất một tập mục kích thước k+1 thì việc ghép nối 2 đồ thị con kích thước k sẽ dẫn tới nhiều đồ thị con kích thước k + 1 bởi các nguyên nhân sau: - Đầu tiên đó là trường hợp sự khác nhau giữa các lõi chung và 2 đồ thị con có thể là một đỉnh có nhãn giống nhau trong cả 2 đồ thị con kích thước k. Khi đó nếu ghép nối nó sẽ tạo ra 2 đồ thị con kích thước k+1 khác nhau. Ví dụ trong Hình 2.1 là khi đồ thị G4a và G4b kết nối sẽ tạo ra 2 đồ thị G5a và G5b tương ứng. Hình 2.1. Khi kết nối bởi các nhãn đỉnh - Thứ hai đó là có thể nhân của mỗi đồ thị con kích thước k có nhiều tự đẳng cấu, 21 Giang Thành Trung và Trần Đăng Hưng và mỗi tự đẳng cấu sẽ tạo ra một ứng viên k + 1 khác nhau. Trong trường hợp xấu nhất nếu nhân là một đồ thị clique không được gán nhãn thì số lượng tự đẳng cấu là k!. Ví dụ trong Hình 2.2, nhân là hình vuông có 4 đỉnh được gán nhãn sẽ có 4 tự đẳng cấu thể hiện trong 3 ứng viên kích thước 6. Hình 2.2. Kết nối khi có đa đẳng cấu của nhân - Thứ ba là khi 2 đồ thị con phổ biến có chung nhiều nhân. Ví dụ như trong Hình 2.3. Hình 2.3. Kết nối khi có đa nhân Thuật toán ghép nối các đồ thị con kích thước k được thể hiện trong Thuật toán 2.3. Cho 1 cặp đồ thị con kích thước k, Gk1 và Gk2 và một nhân kích thước k-1. Kết quả trả ra của thuật toán là một tập các đồ thị ứng viên kích thước k+1. Hoạt động cụ thể của thuật toán như sau: - Bước 1: fsg-join tiến hành xác định 2 cạnh, 1 trong Gk1 và 1 trong Gk2 sao cho chúng không nằm trong nhân. - Bước 2: fsg-join tạo ra tất cả các tự đẳng cấu của nhân. - Bước 3: với mỗi tập 2 cạnh, nhân và tự đẳng cấu, fsg-join tích hợp 2 đồ thị con Gk1 và Gk2 vào một ứng viên kích thước k + 1. 22 Một thuật toán khai phá đồ thị con phổ biến trong dữ liệu đồ thị Thuật toán 2.3: fsg-join(Gk1, Gk2, H(k−1)) (Thuật toán ghép nối 2 đồ thị) (1) e1 ← cạnh chỉ xuất hiện trong Gk1,nhưng không có trong H(k−1) (2) e2 ← cạnh chỉ xuất hiện trong Gk2,nhưng không có trong H(k−1) (3) M ← tạo tất cả các tự đẳng cấu của H(k−1) (4) B(k+1) = ∅ (5) for each tự đẳng cấu ϕ ∈ M do (6) B(k+1) ← B(k+1)∪ tất cả các đồ thị ứng viên k+1 được tạo ra từ một tập của e1, e2, H(k−1) và ϕ (7) return B(k+1) Để giảm thiểu thời gian xác định nhân giữa 2 đồ thị con phổ biến chúng ta lưu giữ lại một số thông tin từ tập các đồ thị con phổ biến. Cụ thể, đối với mỗi đồ thị con phổ biến kích thước k chúng ta lưu trữ các nhãn định danh của đồ thị con phổ biến kích thước k-1 của nó, khi đó việc xác định nhân bằng cách xác định giao của các nhãn định danh. Độ phức tạp của phương pháp này là bình phương số lượng các đồ thị con phổ biến kích thước k. 2.3. Cài đặt và thử nghiệm thuật toán FSG Thuật toán được cài đặt hướng đối tượng bằng ngôn ngữ Java dựa trên việc xây dựng các lớp. Vì giới hạn của bài báo, nên phần này chúng tôi chỉ cung cấp một số thông tin về nội dung các lớp. Tổ chức dữ liệu vào/ra - Dữ liệu vào được lưu trong tệp tin văn bản và có cách tổ chức như sau: Loại dòng Định dạng Giải thích ý nghĩa Chú thích # Ký hiệu báo hiệu chú thích, chương trình sẽ bỏ qua những dòng có ký hiệu này ở đầu Số đỉnh vn Chứa số đỉnh có trong đồ thị Đỉnh v Mã của đỉnh và nhãn của đỉnh đó (mã là số nguyên không âm, nhãn là chuỗi ký tự không dấu) Giao dịch t Bắt đầu 1 giao dịch, là số cạnh trong giao dịch đó Cạnh u Mã của đỉnh đầu và đỉnh cuối của cạnh và nhãn của cạnh đó Ví dụ: Cho đồ thị được biểu diễn như hình bên trái, thì dữ liệu vào sẽ được biểu diễn như hình bên phải dưới đây 23 Giang Thành Trung và Trần Đăng Hưng Đồ thị mẫu Ví dụ về cách biểu diễn dữ liệu đồ thị - Tệp dữ liệu chứa kết quả thu được sau khi chạy thuật toán được lưu trong tệp tin văn bản và có cách tổ chức như sau: Loại dòng Định dạng Giải thích ý nghĩa Chú thích # Ký hiệu báo hiệu chú thích, chương trình sẽ bỏ qua những dòng có ký hiệu này ở đầu Kích thước size Kích thước của đồ thị con phổ biến tìm được Giao dịch sg - - *- - *. . . Bắt đầu 1 đồ thị con phổ biến bao gồm các mã đỉnh đầu, cuối và nhãn cạnh. Các cạnh được phân biệt nhau bởi dấu * Ví dụ về tệp biểu diễn danh sách các đồ thị con phổ biến tìm được 24 Một thuật toán khai phá đồ thị con phổ biến trong dữ liệu đồ thị Thiết kế các lớp chính - Gói Graph bao gồm các lớp để biểu diễn các đối tượng đồi thị. Gói này gồm các lớp VertexLabel, EgdeLabel, Graph và CandidateGraph. + Lớp VertexLabel : sử dụng để biểu diễn đối tượng đỉnh Các thuộc tính/phương thức Ý nghĩa - int ID Biểu diễn mã của đỉnh - String Label Biểu diễn nhãn của đỉnh + void setID(String pID) Phương thức thiết lập mã đỉnh + void setLabel(String pLabel) Phương thức thiết lập nhãn đỉnh + int getID() Phương thức đọc mã đỉnh + string getLabel() Phương thức đọc nhãn đỉnh + Lớp EdgeLabel : sử dụng để biểu diễn đối tượng cạnh Các thuộc tính/phương thức Ý nghĩa - int firstVertex Biểu diễn mã đỉnh thứ nhất - int lastVertex Biểu diễn mã đỉnh thứ hai - String Label Biểu diễn nhãn của cạnh + void setFirstVertex(int pFV) Phương thức thiết lập mã đỉnhthứ nhất + void setLastVertex(int pLV) Phương thức thiết lập mã đỉnhthứ hai + void setLabel(String pLabel) Phương thức thiết lập nhãn cạnh + int getFirstVertex() Phương thức đọc mã đỉnh thứnhất + int getLastVertex() Phương thức đọc mã đỉnh thứ hai + String getLabel() Phương thức đọc nhãn cạnh + Lớp Graph: sử dụng để biểu diễn các đối tượng đồ thị Các thuộc tính/phương thức Ý nghĩa - Int numOfVer Biểu diễn số đỉnh của đồ thị - Int numOfEdge Số cạnh của đồ thị - VertexLabel[] lV = new Ver- texLabel[1000] Danh sách các nhãn đỉnh 25 Giang Thành Trung và Trần Đăng Hưng - EdgeLabel[] lE = new EdgeLa- bel[1000] Danh sách các nhãn cạnh - boolean[] fV = new boolean[1000] Biến đánh dấu khi hoán vị các đỉnh - String[][] Matrix = new String[100][100] Ma trận kề tương ứng của đồ thị - String code Mã của đồ thị (hỗ trợ việc tạoCanonical Label) - String cL Nhãn tiêu chuẩn của đồ thị + Graph() Phương thức khởi tạo đối tượng + Graph(int pNumOfVertex, int pNumOfEdge) Phương thức khởi tạo đối tượng với 2 tham số + void GenerateAdjacencyMa- trix() Phương thức tạo ma trận kề + void SetCode() Phương thức sinh mã của đồ thị + void SetCanonicalLabel() Phương thức sinh Canonical La-bel của đồ thị + Lớp CandidateGraph: kế thừa từ lớp Graph và được sử dụng để biểu diễn các đối tượng đồ thị ứng viên được sinh ra đồng thời biểu diễn các đồ thị phổ biến được xác định Các thuộc tính/phương thức Ý nghĩa - String cL1 Biểu diễn nhãn tiêu chuẩn của đồ thị con thứ nhất sinh ra đồ thị hiện tại - String cL2 Biểu diễn nhãn tiêu chuẩn của đồ thị con thứ hai sinh ra đồ thị hiện tại + void setCL1(String pCL1) Phương thức thiết lập cL1 + void setCL2(String pCL2) Phương thức thiết lập cL2 + String getCL1() Phương thức đọc giá trị của cL1 + String getCL2() Phương thức đọc giá trị của cL2 - Gói Process bao gồm các lớp xử lý đồ thị: + Lớp GetInput : đọc dữ liệu trong tệp tin ở bộ nhớ ngoài 26 Một thuật toán khai phá đồ thị con phổ biến trong dữ liệu đồ thị Các thuộc tính/phương thức Ý nghĩa - String fileName Biểu diễn đường dẫn của tệp tinchứa dữ liệu vào + void setfileName(String pFN) Phương thức thiết lập đường dẫncho tệp tin vào + void ReadFile(String File- Name, Graph graph[], int[] tnum) Phương thức đọc dữ liệu trong tệp tin và biểu diễn vào mảng các đồ thị + Lớp ProcessGraph: đọc dữ liệu trong tệp tin ở bộ nhớ ngoài Các thuộc tính/phương thức Ý nghĩa + boolean isomorphism(Graph g1, Graph g2) Xác định tính đẳng cấu của 2 đồ thị + string compareCode(String paraCode1, String paraCode2) So sánh 2 đoạn mã để xác định mã có thứ tự từ điển lớn hơn + void PermuteIdentifier() Xác định các hoán vị đỉnh có thể của của 1 đồ thị để sinh ra mã tương ứng - Gói Main bao gồm các lớp sau: + Lớp FSG : bao gồm các phương thức cài đặt thuật toán FSG Các thuộc tính/phương thức Ý nghĩa - Graph[] graph Biểu diễn các đồ thị đọc được từtệp tin vào - int[] tn Biểu diễn tổng số giao dịch - CandidateGraph[][] canGraph Biểu diễn các tập đồ thị ứng viênđược sinh ra - CandidateGraph[][] fre- quentSubgraph Biểu diễn các tập đồ thị phổ biến được xác định + void Input() Phương thức đọc dữ liệu từ tệptin đầu vào + void FSG() Phương thức chạy thuật toánFSG 27 Giang Thành Trung và Trần Đăng Hưng + void GenerateFirstCandidate() Phương thức khởi tạo tập ứngviên 1, 2 cạnh + void FSG_Gen(int k) Phương thức khởi tạo tập ứngviên kích thước k ≥ 3 + graph[] coreIdentifier(Graph g1, Graph g2) Phương thức xác định nhân của 2 đồ thị + void FSG_Join(Graph g1, Graph g2, Graph gcore) Phương thức kết nối 2 đồ thị để tạo ra 1 ứng viên Kết quả thực nghiệm Chúng tôi đã cài đặt hoàn chỉnh chương trình và thử nghiệm tr