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í

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:

Hệ thống thông tin

Tóm tắt nội dung tài liệu:

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í" của Vũ Chí Quang tập trung giải quyết các thách thức trong việc tối đa hóa sự lan truyền thông tin trên các Mạng xã hội (SN) dưới các điều kiện ràng buộc thực tế.

Về mặt thực tiễn, mạng xã hội đã trở thành công cụ hữu ích và kho tri thức khổng lồ, mang lại lợi ích to lớn về chính trị và kinh tế, do đó cần nghiên cứu để tối đa hóa hiệu quả lan truyền thông tin. Về mặt khoa học, bài toán Cực đại ảnh hưởng trên SN là hướng nghiên cứu được nhiều nhà khoa học quan tâm, thuộc nhóm các bài toán lan truyền thông tin (Spread Information - SI). Tuy nhiên, SN có khối dữ liệu khổng lồ, phân tán, quá trình lan truyền ngẫu nhiên và cấu trúc mạng phức tạp, đòi hỏi các giải pháp hiệu quả về thời gian và bộ nhớ.

Mục tiêu của luận án là nghiên cứu các bài toán cực đại ảnh hưởng trên các mô hình lan truyền thông tin, từ đó đề xuất các biến thể mới có tính ứng dụng thực tiễn. Luận án cũng đề xuất các mô hình và thuật toán hiệu quả để giải quyết các bài toán này, tập trung vào việc nâng cao chất lượng lời giải và khả năng ứng dụng với các mạng cỡ lớn.

Luận án đã hoàn thành các mục tiêu nghiên cứu bằng cách đề xuất hai bài toán chính:

• **Bài toán Cực đại ảnh hưởng với ràng buộc ưu tiên (IMP):** Bài toán này yêu cầu tìm một tập hợp k nút trong SN để bắt đầu lan truyền ảnh hưởng sao cho số lượng nút bị ảnh hưởng là tối đa, đồng thời đảm bảo ảnh hưởng đến một tập người dùng ưu tiên U không nhỏ hơn một ngưỡng T. Luận án chỉ ra rằng IMP là bài toán NP-Khó và các thuật toán IM hiện có không thể áp dụng. Để giải quyết, luận án đề xuất hai thuật toán hiệu quả là 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), với các đảm bảo lý thuyết về tỷ lệ xấp xỉ. Các thực nghiệm trên 05 bộ dữ liệu SN thực tế cho thấy IGS vượt trội hơn các thuật toán hiện đại khác về giá trị hàm ảnh hưởng, thời gian chạy và hiệu quả sử dụng bộ nhớ.
• **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):** Đây là một tổng quát hóa của bài toán cực đại ảnh hưởng, xét đến trường hợp có nhiều chủ đề và chi phí giới hạn cho việc khởi tạo ảnh hưởng. Luận án đề xuất hai thuật toán luồng duyệt dữ liệu một lần: thuật toán luồng tất định (cho trường hợp chi phí đồng nhất) và thuật toán luồng ngẫu nhiên (cho trường hợp tổng quát với chi phí khác nhau), cả hai đều có đảm bảo lý thuyết về tỷ lệ gần đúng. Kết quả thực nghiệm trên mạng xã hội Facebook cho thấy các thuật toán đề xuất trả về giải pháp có chất lượng tốt và yêu cầu số lượng truy vấn nhỏ hơn đáng kể so với thuật toán tham lam tiên tiến nhất.

Các nghiên cứu này đã được công bố trên các kỷ yếu hội thảo và tạp chí uy tín thuộc chuyên ngành Tối ưu hóa, Công nghệ thông tin. Hướng nghiên cứu tiếp theo bao gồm việc phát triển các giải pháp hiệu quả hơn, ứng dụng rộng rãi trên SN và xử lý các mạng có quy mô lớn hơn.

Mục lục chi tiết:

• MỞ ĐẦU
  • 1. Tính cấp thiết của luận án
  • 2. Mục tiêu nghiên cứu của luận án
  • 3. Các nội dung nghiên cứu chính của luận án
• CHƯƠNG 1 CƠ SỞ LÝ THUYẾT CỦA LUẬN ÁN VÀ CÁC NGHIÊN CỨU LIÊN QUAN
  • 1.1 Giới thiệu về mạng xã hội
  • 1.2 Mô hình hóa lan truyền thông tin trên mạng xã hội
    • 1.2.1 Mô hình Ngưỡng tuyến tính (LT)
    • 1.2.2 Mô hình Bậc độc lập (IC)
  • 1.3 Một số bài toán lan truyền thông tin trên mạng xã hội
    • 1.3.1 Cực đại ảnh hưởng (Influence Maximization - IM)
    • 1.3.2 Phát hiện thông tin (Information Detection - ID)
    • 1.3.3 Ngăn chặn ảnh hưởng (Influence Blocking - IB)
  • 1.4 Bài toán tối ưu tổ hợp và một số phương pháp giải các bài toán tối ưu tổ hợp.
  • 1.5 Các nghiên cứu liên quan
  • 1.6 Kết luận chương
• CHƯƠNG 2 CỰC ĐẠI ẢNH HƯỞNG VỚI RÀNG BUỘC ƯU TIÊN TRÊN MẠNG XÃ HỘI
  • 2.1 Phát biểu bài toán IMP
  • 2.2 Đề xuất thuật toán
    • 2.2.1 Thuật toán tham lam tích hợp IG
    • 2.2.2 Thuật toán lấy mẫu dựa trên tham lam tích hợp IGS
  • 2.3 Thực nghiệm và đánh giá kết quả
    • 2.3.1 Thực nghiệm
    • 2.4.2 Đánh giá kết quả
  • 2.6 Kết luận chương
• CHƯƠNG 3 CỰC ĐẠI ẢNH HƯỞNG LAN TRUYỀN THÔNG TIN NHIỀU CHỦ ĐỀ VỚI CHI PHÍ GIỚI HẠN
  • 3.1 Đặt vấn đề
  • 3.2 Đề xuất thuật toán
    • 3.2.1 Thuật toán luồng tất định
    • 3.2.2 Thuật toán luồng ngẫu nhiên
  • 3.3 Thực nghiệm và đánh giá kết quả
  • 3.4 Kết luận chương
• KẾT LUẬN
• DANH MỤC CÁC BÀI BÁO ĐÃ XUẤT BẢN LIÊN QUAN ĐẾN LUẬN ÁN