NHỮNG ĐÓNG GÓP MỚI CỦA LUẬN ÁN
Tên luận án: Nghiên cứu một số phương pháp giải bài toán cực đại ảnh hưởng trên mạng xã hội với ràng buộc ưu tiên và chi phí.
Ngành đào tạo: Hệ thống thông tin Mã số: 9.48.01.04
Họ và tên nghiên cứu sinh: Vũ Chí Quang
Chức danh, học vị, họ và tên người hướng dẫn: TS. Nguyễn Như Sơn; PGS. TS. Ngô Quốc Dũng
Cơ sở đào tạo: Học viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam
Nội dung: Luận án có 02 đóng góp chính, bao gồm:
Đề xuất 02 thuật toán: Thuật toán tham lam tích hợp – IG và thuật toán lấy mẫu dựa trên tham lam tích hợp – IGS cho bài toán cực đại ảnh hưởng với ràng buộc ưu tiên (IMP). Luận án đã chứng minh IG cung cấp một nghiệm gần đúng 1-(1-1/k)^t ; IGS là một thuật toán xấp xỉ ngẫu nhiên dựa trên phương pháp lấy mẫu trả về một nghiệm gần đúng (1-(1-1/k)^t-ϵ) với xác suất ít nhất là 1 – δ với ϵ > 0, δ ∈ (0, 1).
Đề xuất 01 mô hình cho bài toán cực đại ảnh hưởng lan truyền thông tin nhiều chủ đề với chi phí giới hạn – BkIM (Budgeted k-Influence maximization) và đề xuất 02 thuật toán luồng duyệt dữ liệu một lần (Thuật toán luồng tất định và thuật toán luồng ngẫu nhiên) với độ phức tạp O(kn/ log n) để giải bài toán BkIM.
