Luận án: Nghiên cứu các bài toán tối ưu trên mạng xã hội trực tuyến và ứng dụng

MỞ ĐẦU Sự phát triển của các Mạng xã hội trực tuyến (MXHTT) trong những năm gần đây đã đưa chúng trở thành một trong những nền tảng mạnh mẽ trong truyền thông, đóng góp đáng kể đối với sự phát triển của nền kinh tế toàn cầu. Theo những khảo sát gần đây, có gần một nửa dân số thế giới, tức là hơn 3 tỷ người sử dụng các MXHTT [86], trong đó số người dùng coi MXHTT là nguồn thông tin chính thức của họ chiếm tỷ lệ lớn [110]. Người dùng trên các MXHTT có thể trao đổi thông tin với nhau một cách nhanh chóng bất chấp khoảng cách về địa lý và thời gian. Bên cạnh đó, MXHTT còn cung cấp cho người dùng rất nhiều ứng dụng hữu ích, làm cho cuộc sống của con người ngày càng trở nên thuận tiện hơn.

Trên mỗi MXHTT, người dùng có thể thể thu nhận được thông tin cần thiết và cũng có thể trở thành những “phóng viên” để đưa những thông tin trong thế giới thực cũng như chia sẻ quan điểm cá nhân của mình. Ngoài những đặc tính kế thừa của mạng lưới xã hội thực như: tương tác giữa người dùng, lan truyền thông tin, tạo ảnh hưởng trong cộng đồng, v. thì MXHTT còn mang nhiều đặc tính mới như: cập nhật thông tin thực lên MXHTT một cách nhanh chóng, thời gian lan truyền tin ngắn, sự bùng nổ thông tin với các nguồn tin tức khác nhau, v. Có thể nói, hiện nay MXHTT đang trở thành một công cụ hữu ích cho đời sống của con người và là một kho tri thức mới mà con người có thể dễ dàng tiếp cận.

Trong bối cảnh đó, các chủ đề nghiên cứu về MXHTT được rất nhiều nhà khoa học quan tâm trong những năm gần đây. Một trong các hướng nghiên cứu được quan tâm nhiều là nhóm các bài toán lan truyền thông tin (information diffusion problem) trên các MXHTT. Các bài toán này nảy sinh trong thực tiễn cần có những giải pháp hiệu quả trong việc quản lý những thông tin trên MXHTT, bao gồm các nhiệm vụ: phát tán thông tin cần thiết, ngăn chặn những thông tin xấu, các ảnh hưởng tiêu cực một cách hiệu quả. Việc giải quyết những bài toán này cũng góp phần nâng cao sự phục vụ, độ tin cậy của MXHTT đối với cộng đồng người dùng.

Xét theo khía cạnh trong khoa học máy tính, nhóm các bài toán này thường được xây dựng dưới dạng các bài toán tối ưu tổ hợp (TƯTH) trên các mô hình lan truyền thông tin (information diffusion model). Kempe và các cộng sự [43] lần đầu tiên đề xuất hai mô hình phát tán thông tin đầu tiên là Ngưỡng tuyến tính (Linear Threshold - LT) và Bậc độc lập (Independent Cascade - IC) dựa trên các quan sát về sự phát tán thông tin trên các MXHTT [30]. Sau đó, hai mô hình này và các biến thể của chúng được nhiều tác giả sử dụng rộng rãi trong việc nghiên cứu các bài toán lan truyền thông tin. Theo các nhiệm 1 vụ lớp bài toán này đặt ra, có thể phân loại chúng thành 02 nhóm bài toán quan trọng là: 1.

Tối đa hóa ảnh hưởng (Influence Maximization - IM) [43, 21, 22, 18, 75, 93]: Bài toán này yêu cầu chọn một tập hợp nhỏ người dùng (ngân sách giới hạn) để bắt đầu lan truyền thông tin sao cho số người bị ảnh hưởng bởi thông tin đó trên một MXHTT đạt cực đại. Nó nảy sinh từ các nhu cầu thực tiễn lan truyền tiếp thị sản phẩm, tối đa hóa lợi ích doanh nghiệp trong quảng bá sản phẩm, ngăn chặn dịch bệnh trên MXHTT, giám sát thông tin trên, phân tích ảnh hưởng vv. Ví dụ trong lan truyền tiếp thị sản phẩm, các doanh nghiệp thường chọn k người dùng để đưa các sản phẩm dùng thử sau đó yêu cầu những người dùng này đưa các thông tin về tính năng tốt lên các MXHTT để bắt đầu quá trình lan truyền thông tin về sản phẩm để số người dùng biết được thông tin và bị ảnh hưởng là lớn nhất. Ngoài ra, các biến thể có tính ứng dụng cao của bài toán này cũng được quan tâm nghiên cứu.

- Biến thể theo thời gian [20, 91], chi phí [72, 62, 76, 60], khoảng cách [101], chủ đề quan tâm [17]. - Biến thể theo trường hợp có nhiều đối thủ cạnh tranh. Trong trường hợp này cần tối đa hóa ảnh hưởng của một đối thủ trong trường hợp lan truyền thông tin có sự cạnh tranh (bài toán tối đa hóa ảnh hưởng cạnh tranh) [10, 39, 66, 18, 65, 64, 102]. Ngăn chặn ảnh hưởng (Influence Blocking - IB) [39, 45, 117, 13, 116, 115, 39, 87, 89, 110]: Mục tiêu của bài toán này là tìm một tập người dùng để loại bỏ, hoặc cách ly, hoặc bắt đầu lan truyền thông tin tốt sao cho ảnh hưởng của thông tin xấu (hoặc thông tin đối lập) đạt giá trị cực tiểu.

Có thể hiểu đây là bài toán có mục tiêu ngược so với IM. Bài toán này nảy sinh từ nhu cầu thực tiễn cần có những giải pháp tối ưu trong việc ngăn chặn sự lan truyền của những yếu tố xấu như: thông tin sai lệch, virus, tin đồn, vv. trên các MXHTT trực tuyến. Có hai hướng tiếp cận cho nhóm bài toán này là: - Lan truyền thông tin tốt để hạn chế các thông tin xấu (tẩy nhiễm thông tin) [39, 13, 77, 89, 113].

- Loại bỏ tập các đỉnh hoặc cạnh đóng vai trò quan trọng để hạn chế ảnh hưởng của một nguồn phát tán thông tin cho trước [39, 45, 117, 116, 115, 87, 110]. Trong bối cảnh hiện nay khi số người dùng trên MXHTT ngày càng tăng thì các thông tin trên MXHTT ngày càng tác động mạnh mẽ đến cộng đồng người dùng qua đó gián tiếp ảnh hướng đến công chúng trong thế giới thực. Do đó các bài toán trên được chú trọng và được nghiên cứu ngày càng rộng rãi [61]. Tuy vậy, việc giải quyết và áp dụng hai nhóm bài toán trên trong thực tiễn gặp một số thách thức chính là: 2 1.

Lớp bài toán này thường thuộc lớp bài toán tối ưu tổ hợp NP-Khó. Thêm vào đó, việc tính toán hàm mục tiêu thường là #P-Khó [21, 22]. Do vậy, cần những thuật toán hiệu quả để tìm lời giải tốt trong thời gian cho phép. Với sự mở rộng của quy mô các MXHTT (hàng triệu, tỷ người dùng), cần có những thuật toán hoặc cách tiếp cận hiệu quả hơn nữa cho những bài toán trên để nâng cao tính thực tiễn của chúng.

Để nâng cao hơn nữa tính ứng dụng của mỗi bài toán, cần nghiên cứu những biến thể phù hợp với thực tế theo các khía cạnh khác nhau như: thời gian, khoảng cách, chi phí, lợi ích, tính cạnh tranh v. Để tìm cách giải quyết các thách thức trên, tác giả cùng các cộng sự đã chọn chủ đề nghiên cứu “Một số bài toán tối ưu trên mạng xã hội” với mục tiêu như sau: 1. Nghiên cứu bài toán IM, IB trên các mô hình phát tán truyền thông tin. Qua đó đề xuất nghiên cứu các bài toán biến thể mới có tính ứng dụng trong thực tiễn.

Đề xuất các mô hình giải quyết các bài toán trên, nghiên cứu độ phức tạp của chúng trên các mô hình lan truyền thông tin được sử dụng rộng rãi. Đề xuất các thuật toán hiệu quả để giải quyết các bài toán trên, trong đó đặc biệt chú trọng tới việc nâng cao chất lượng lời giải cũng như khả năng ứng dụng với các mạng cỡ lớn hàng trăm nghìn cho tới hàng triệu, tỷ cạnh hoặc đỉnh. Với các mục tiêu trên, nghiên cứu sinh đã sử dụng các phương pháp nghiên cứu sau: Nghiên cứu lý thuyết về các bài toán tối ưu tổ hợp, độ phức tạp của các thuật toán. Nghiên cứu lý thuyết thiết kế các thuật toán cho các bài toán tối ưu tổ hợp thuộc lớp NP-Khó, NP-đầy đủ, #P-Khó.

Khảo sát, phân tích các công trình đã công bố liên quan đến cơ chế và mô hình lan truyền thông tin, các bài toán về lan truyền thông tin. Trên cơ sở đó, luận án đề xuất các bài toán mới có tính ứng dụng cao trong thực tiễn. Các bài toán này được giải luận một cách chặt chẽ phù hợp với thực tiễn. Các đề xuất mới đều được phân tích đánh giá, chứng minh chặt chẽ thông qua các phân tích lý thuyết được phát biểu dưới dạng các Bổ đề, Định lý, Hệ quả.

Nghiên cứu sinh kết hợp với các phương pháp thực nghiệm với máy tính trên các bộ dữ liệu khác nhau nhằm đảm bảo tính khách quan về hiệu quả của phương pháp đề xuất. Trong thời gian qua, cùng với cán bộ hướng dẫn khoa học và các cộng sự, tác giả luận án đã có những đóng góp sau: 3 1. Nghiên cứu bài toán Tối đa ảnh hưởng cạnh tranh tổng quát (Budgeted Com- petitive Influence Maximization - BCIM) là một biến thể của IM với mục tiêu tối đa hóa ảnh hưởng trong trường hợp có sự cạnh tranh trên một số mô hình lan truyền thông tin cạnh tranh với ngân sách và thời gian hạn chế. Trước hết luận án đề xuất mô hình ngưỡng tuyến tính cạnh tranh ràng buộc thời gian TCLT để mô hình quá trình lan truyền có sự cạnh tranh của các đối thủ.

Luận án xây dựng bài toán BCIM trên mô hình TCLT, chỉ ra tính chất của bài toán trên mô hình này. Luận án đề xuất một thuật toán xấp xỉ hiệu quả SPBA cho bài toán BCIM. Thực nghiệm cho thấy thuật toán đề xuất cho kết quả tốt và có thể thực hiện với MXHTT cỡ hàng triệu đỉnh và cạnh. Ngoài ra, luận án cũng mở rộng nghiên cứu bài toán BCIM trên mô hình Ngưỡng tuyến tính cạnh tranh xác định.

Các kết quả được công bố tại hội nghị quốc tế Computational Data & Social Networks (CSoNet) năm 2018, hội nghị IEEE-RIVF International Conference on Computing and Communication Technolo- gies (RIVF) năm 2019 và tạp chí Applied Sciences (SCIE) năm 2019. Nghiên cứu bài toán Hạn chế tối đa thông tin sai lệch (Maximizing Misinfor- mation Restriction-MMR) là một biến thể của bài toán IB, trong đó có xem xét ngân sách và thời gian hạn chế trên một số mô hình lan truyền thông tin. Tác giả đề xuất mô hình giải quyết bài toán MMR trên mô hình ngưỡng tuyến tính mở rộng. Tác giả chỉ ra độ phức tạp của bài toán này và đề xuất các thuật toán hiệu quả cho bài toán bao gồm các thuật toán xấp xỉ: FPTAS, IGA, SG và thuật toán heuristic PR-DAG.

Ngoài ra, luận án cũng mở rộng kết quả nghiên cứu bài toán này trong trường hợp mô hình ngưỡng tuyến tính xác định. Các kết quả nghiên cứu này được công bố trên hội nghị quốc tế Symposium on Information and Communication Technology (SoICT) năm 2017 và tạp chí Journal of Combinatorial Optimization (SCIE) năm 2018.