Khai thác đồ thị con trên đồ thị có trọng số - NCS. Lê Thị Ngọc Thảo

Tên đề tài luận án: Khai thác đồ thị con trên đồ thị có trọng số
Ngành: Khoa học máy tính
Mã số ngành: 62480101
Họ tên nghiên cứu sinh: Lê Thị Ngọc Thảo
Khóa đào tạo: 2015
Người hướng dẫn khoa học: GS.TS. Lê Hoài Bắc và PGS.TS. Võ Đình Bảy
Cơ sở đào tạo: Trường Đại học Khoa học Tự nhiên - ĐHQG.HCM
1. Tóm tắt nội dung luận án
Trên cơ sở phân tích và đánh giá những ưu nhược điểm của các phương pháp trước đây thường được dùng để giải bài toán khai thác đồ thị con phổ biến trên đồ thị có trọng số, mục tiêu của luận án là nghiên cứu và đề xuất những kết quả lý thuyết, phương pháp tiếp cận và thuật toán mới nhằm giải quyết hiệu quả bài toán khai thác tập đồ thị con phổ biến trên một đồ thị có trọng số đỉnh.
Để đạt được mục tiêu, luận án đề xuất một phương pháp tiếp cận dựa trên việc kế thừa thuật toán GraMi được đề xuất bởi Elseidy và các đồng sự. Phương pháp tiếp cận được đưa ra dựa trên ý tưởng sử dụng mô hình CSP (Constraint Satisfaction Problem) để biểu diễn dữ liệu đồ thị và sử dụng lại thuật toán GraMi để giải quyết bài toán khai thác đồ thị con phổ biến trên một đồ thị, dựa trên cơ sở bổ sung thêm yếu tố về trọng số vào mô hình này.
2. Những kết quả mới của luận án
Thuật toán WeGraMi và OWGraMi sử dụng độ đo MaxMin thỏa tính chất DCP (Downward Closure Property) để tính trọng số của đồ thị con và áp dụng chiến lược cắt tỉa không gian tìm kiếm dựa trên ngưỡng trọng số để khai thác hiệu quả các đồ thị con phổ biến có trọng số.
Các chiến lược hiệu quả đã được đề xuất để tỉa sớm các cạnh không thể đạt đến ngưỡng trọng số đã cho và tái sử dụng lại trọng số của các đồ thị con đã tính nhằm tăng tốc khai thác đồ thị con phổ biến có trọng số trong thuật toán OWGraMi.
Để mở rộng phương pháp giải bài toán khai thác đồ thị con phổ biến có trọng số với hướng tiếp cận sử dụng một độ đo khác với độ đo MaxMin, luận án đã đề xuất thuật toán AWeGraMi sử dụng độ đo trung bình (AveMin) để tính trọng số của đồ thị con. Vì độ đo AveMin không thỏa tính chất DCP, luận án đồng thời sử dụng MaxMin làm chặn trên (upper bound) nhằm tỉa sớm các đồ thị con phổ biến không thỏa ngưỡng trọng số.
3. Các ứng dụng/ khả năng ứng dụng trong thực tiễn hay những vấn đề còn bỏ ngỏ cần tiếp tục nghiên cứu
Phát triển các phương pháp khai thác đồ thị con có trọng số phổ biến bằng cách sử dụng các phương pháp tiếp cận khác cũng như nghiên cứu sử dụng các độ đo khác để tính trọng số của đồ thị con sao cho đảm bảo tính chất DCP nhằm phục vụ cho mục tiêu cắt tỉa sớm không gian tìm kiếm khi khai thác đồ thị con phổ biến.
Mở rộng đối tượng nghiên cứu trọng số của đồ thị sang trọng số trên cạnh hoặc kết hợp giữa trọng số cạnh và trọng số đỉnh hoặc phát triển mô hình đồ thị đa trọng số nhằm phục vụ cho mô phỏng việc thể hiện các dữ liệu trọng số đa dạng trong thực tiễn.
Hướng đến phát triển các phiên bản song song của các thuật toán đã được luận án đề xuất, sử dụng các hệ thống tính toán hiệu năng cao để triển khai trên môi trường phân tán nhằm áp dụng hiệu quả cho việc khai thác dữ liệu lớn.