GIẢI BÀI TOÁN TỐI ĐA HÓA ẢNH HƯỞNG CỦA LAN TRUYỀN TIẾP THỊ TRÊN CÁC CỘNG ĐỒNG MẠNG XÃ HỘI DỰA TRÊN TỐI ƯU HÓA HÀM DR-SUBMODULAR TRONG LƯỚI NGUYÊN DƯƠNG

Tóm tắt

Trong bối cảnh xã hội phát triển ở rất nhiều lĩnh vực, con người phải đối mặt và giải quyết nhiều bài toán tối ưu hóa với hàm mục tiêu ngày càng phức tạp. Nổi bật trong số đó là họ các bài toán tối ưu hóa có hàm mục tiêu với tính chất lợi nhuận hiệu suất giảm dần, hay còn gọi là hàm DR-submodular (diminishing return submodular). Trong bài báo này, nhóm tác giả nghiên cứu một bài toán cụ thể thuộc họ bài toán trên, đó là tối đa hóa tầm ảnh hưởng cho việc lan truyền tiếp thị trên các cộng đồng của mạng xã hội. Nhóm tác giả áp dụng kỹ thuật duyệt dữ liệu theo luồng phát trực tiếp (streaming) để đề xuất thuật toán DR-SubOptStream cho bài toán và thu được kết quả khả quan cho cả dữ liệu lớn. Trong phần thực nghiệm, nhóm tác giả phải phân tích và tiền xử lý dữ liệu của mạng xã hội từ dạng đồ thị liên thông thông thường thành dạng dữ liệu đồ thị lưỡng cực. Sau đó, thuật toán DR-SubOptStream được chạy với một số bộ dữ liệu mạng xã hội dạng lưỡng cực đã được tiền xử lý. Kết quả thực nghiệm cho thấy thuật toán đề xuất có hàm mục tiêu đạt giá trị chấp nhận theo xấp xỉ và độ phức tạp tốt hơn thuật toán hiện có của dạng bài toán này.