Luận án Tiến sĩ Khoa học máy tính: Một số bài toán tối ưu ở trên mạng xã hội

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:172

Thêm vào BST

Báo xấu

8
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án "Một số bài toán tối ưu ở trên mạng xã hội" được hoàn thành với mục tiêu nhằm đề 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Khoa học máy tính: Một số bài toán tối ưu ở trên mạng xã hội

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Văn Cảnh MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN MẠNG XÃ HỘI LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Hà Nội – 2020
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Văn Cảnh MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN MẠNG XÃ HỘI Chuyên ngành: Khoa học máy tính Mã số: 62480101 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. GS. TS Thái Trà My 2. PGS. TS Hoàng Xuân Huấn Hà Nội – 2020
LỜI CAM ĐOAN Tôi xin cam đoan luận án này là kết quả nghiên cứu của tôi, được thực hiện dưới sự hướng dẫn của GS. TS Thái Trà My và PGS. TS Hoàng Xuân Huấn. Các kết quả và số liệu trình bày trong luận án là hoàn toàn trung thực và chưa từng được công bố trong bất kỳ công trình của ai khác. Các nội dung trích dẫn từ các nghiên cứu của các tác giả khác mà tôi trình bày trong luận án này đã được ghi rõ nguồn trong phần tài liệu tham khảo. Hà Nội, ngày tháng năm 2020 Người thực hiện Phạm Văn Cảnh i
LỜI CẢM ƠN Trước hết, tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc tới tập thể Thầy Cô hướng dẫn, GS. TS Thái Trà My và PGS. TS Hoàng Xuân Huấn. Tôi vô cùng biết ơn GS. TS Thái Trà My, mặc dù rất bận rộn nhưng luôn dành thời gian quan tâm và hướng dẫn tôi hoàn thành các nghiên cứu của mình. Cô luôn động viên và khích lệ tôi vượt qua những thử thách trong khoa học cũng như trong cuộc sống. Tôi vô cùng biết ơn sự giúp đỡ tận tình, quý báu của thầy PGS. TS Hoàng Xuân Huấn đã dành cho tôi trong suốt quá trình thực hiện luận án. Nhờ có những động viên, khích lệ, và những tài liệu quý báu mà thầy cung cấp, tôi mới có thể hoàn thành luận án của mình. Thầy đã cho tôi nhiều kinh nghiệm quý báu trong nghiên cứu và cuộc sống giúp tôi vững tin vượt qua những khó khăn trong suốt quá trình nghiên cứu. Tôi xin chân thành cảm ơn các Thầy Cô trong Khoa Công nghệ thông tin, và đặc biệt là các Thầy Cô trong Bộ môn Khoa học máy tính, trường Đại học Công nghệ - Đại học Quốc Gia Hà Nội, kiến thức mà thầy cô truyền dạy là hành trang quý báu để tôi hoàn thành các học phần và luận án của mình. Tôi xin gửi lời cảm ơn đến GS. TS Nguyễn Thanh Thủy, PGS. TS Hà Quang Thụy, TS Trần Quốc Long, TS Hà Minh Hoàng, TS Nguyễn Trung Thành và TS Đoàn Trung Sơn đã có những góp ý quý báu trong các buổi seminar để tôi có thể hoàn thành luận án. Tôi xin chân thành cảm ơn TS Sử Ngọc Anh, lãnh đạo Khoa công nghệ và An ninh thông tin - Học viện An ninh nhân dân đã tạo những điều kiện tốt nhất để tôi hoàn thành khóa học, tôi xin cảm ơn tất cả đồng nghiệp trong Khoa Công nghệ và An ninh thông tin, đặc biệt là Tổ Bộ môn Toán ứng dụng đã luôn hỗ trợ, giúp đỡ tôi trong suốt quá trình học tập tại Trường Đại học Công nghệ - Đại học Quốc Gia Hà Nội. Cuối cùng, luận án này sẽ không hoàn thành được nếu thiếu sự động viên về mọi mặt của gia đình. Từ tận đáy lòng, tôi xin gửi lời cảm ơn chân thành đến bố mẹ tôi, những người đã vất vả để tôi có được ngày hôm nay. Tôi xin gửi lời cảm ơn và biết ơn chân thành tới bố mẹ vợ của tôi, những người đã luôn ủng hộ, giúp đỡ và khích lệ tôi vượt qua những khó khăn trong học tập cũng như trong cuộc sống. Tôi xin cảm ơn tới vợ, con tôi, những người luôn là động lực về tinh thần giúp tôi vững bước trong quá trình học tập, nghiên cứu và mọi khó khăn trong cuộc cuộc sống. Tôi xin cảm ơn tất cả những người thân trong gia đình đã luôn ủng hộ, chia sẻ những khó khăn đối với tôi. Phạm Văn Cảnh ii
MỤC LỤC Lời cam đoan i Lời cảm ơn ii Danh sách hình vẽ vii Danh mục các từ viết tắt ix MỞ ĐẦU 1 Chương 1. Tổng quan về các bài toán lan truyền thông tin 6 1.1. Giới thiệu về mạng xã hội . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1. Những đặc điểm chung của MXHTT . . . . . . . . . . . . . . . . . . 7 1.1.2. Lợi ích của MXHTT . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.3. Những tác hại của MXHTT . . . . . . . . . . . . . . . . . . . . . . . 8 1.2. Các mô hình phát tán thông tin trên MXHTT . . . . . . . . . . . . . . . . . 9 1.2.1. Mô hình phát tán thông tin rời rạc . . . . . . . . . . . . . . . . . . . . 10 1.2.2. Mô hình Ngưỡng tuyến tính (LT) . . . . . . . . . . . . . . . . . . . . 11 1.2.3. Mô hình Bậc độc lập (IC) . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.4. Mô hình cạnh trực tuyến (live-edge) . . . . . . . . . . . . . . . . . . . 14 1.3. Một số bài toán lan truyền thông tin trên MXHTT . . . . . . . . . . . . . . 17 1.3.1. Tối đa ảnh hưởng (IM) . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.3.1.1. Các thuật toán cho bài toán IM . . . . . . . . . . . . . . . . . 18 1.3.1.2. Một số biến thể của bài toán cực đại ảnh hưởng . . . . . . . . 22 1.3.2. Ngăn chặn ảnh hưởng (IB) . . . . . . . . . . . . . . . . . . . . . . . . 24 1.3.2.1. Loại bỏ tập người dùng và liên kết . . . . . . . . . . . . . . . 25 1.3.2.2. Tẩy nhiễm thông tin . . . . . . . . . . . . . . . . . . . . . . . 26 1.4. Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Chương 2. 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 29 2.1. Bài toán TƯTH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2. Phân loại các lớp bài toán trong TƯTH . . . . . . . . . . . . . . . . . . . . 29 2.3. Một số phương pháp giải bài toán TƯTH . . . . . . . . . . . . . . . . . . . 34 2.3.1. Thuật toán xấp xỉ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.2. Phương pháp Mote-Carlo . . . . . . . . . . . . . . . . . . . . . . . . 37 2.3.2.1. Bài toán tìm giá trị cực đại . . . . . . . . . . . . . . . . . . . . 38 2.3.2.2. Bài toán uớc lượng kỳ vọng của một biến ngẫu nhiên . . . . . 39 iii
2.3.3. Thuật toán heuristic cấu trúc . . . . . . . . . . . . . . . . . . . . . . . 40 2.3.4. Thuật toán Metaheuristic . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.4. Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Chương 3. Tối đa ảnh hưởng cạnh tranh với ràng buộc về thời gian và ngân sách 42 3.1. Đặt vấn đề và phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . 42 3.1.1. Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.1.2. Phát biểu bài toán và mô hình đề xuất . . . . . . . . . . . . . . . . . . 45 3.1.2.1. Bài toán BCIM . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.1.2.2. Mô hình ảnh hưởng cạnh tranh . . . . . . . . . . . . . . . . . 46 3.2. Thuật toán xấp xỉ cho bài toán BCIM . . . . . . . . . . . . . . . . . . . . . . 53 3.2.1. Các hàm xấp xỉ trên và xấp xỉ dưới . . . . . . . . . . . . . . . . . . . 54 3.2.1.1. Hàm xấp xỉ trên . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.2.1.2. Hàm xấp xỉ dưới . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.2.2. Thuật toán PBA cho bài toán cực đại các hàm xấp xỉ . . . . . . . . . 59 3.2.2.1. Mô tả thuật toán PBA . . . . . . . . . . . . . . . . . . . . . . 60 3.2.2.2. Phân tích tỷ lệ xấp xỉ của thuật toán PBA . . . . . . . . . . . . 61 3.2.2.3. Phân tích độ phức tạp . . . . . . . . . . . . . . . . . . . . . . 65 3.2.3. Thuật toán SPBA cho bài toán BCIM . . . . . . . . . . . . . . . . . . . 65 3.3. Thực nghiệm và kết quả . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.3.1. Dữ liệu và tham số . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.3.2. Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.3.2.1. Trường hợp chi phí tổng quát . . . . . . . . . . . . . . . . . . 69 3.3.2.2. Trường hợp chi phí đồng nhất . . . . . . . . . . . . . . . . . . 70 3.3.2.3. So sánh thời gian chạy . . . . . . . . . . . . . . . . . . . . . . 70 3.3.2.4. Ảnh hưởng của bước thời gian τ . . . . . . . . . . . . . . . . 71 3.4. Bài toán tối đa ảnh hưởng cạnh tranh trên mô hình cạnh tranh ngưỡng tuyến tính xác định . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.4.1. Mô hình và định nghĩa bài toán . . . . . . . . . . . . . . . . . . . . . 73 3.4.2. Các thuật toán cho CIM trên mô hình DCLT . . . . . . . . . . . . . . . 75 3.4.3. Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.5. Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 iv
Chương 4. Ngăn chặn thông tin sai lệch với ràng buộc về ngân sách và thời gian 80 4.1. Đặt vấn đề và phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . 80 4.1.1. Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.1.2. Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.1.3. Mô hình ngưỡng tuyến tính ràng buộc thời gian (TLT) . . . . . . . . . 83 4.1.4. Hàm mục tiêu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.2. Độ khó của bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.3. Các thuật toán cho MMR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.3.1. Các thuật toán xấp xỉ . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.3.1.1. Thuật toán FPTAS trong trường hợp cây có gốc . . . . . . . . 88 4.3.1.2. Thuật toán xấp xỉ trong trường hợp tổng quát . . . . . . . . . 92 4.3.1.3. Thuật toán tham lam tăng tốc (SG) . . . . . . . . . . . . . . . 96 4.3.2. Thuật toán heuristic PR-DAG . . . . . . . . . . . . . . . . . . . . . . . 100 4.3.2.1. Xây dựng DAG từ đồ thị ban đầu . . . . . . . . . . . . . . . . 100 4.3.2.2. Ước lượng hàm mục tiêu dựa trên DAG . . . . . . . . . . . . . 102 4.3.2.3. Thuật toán PR-DAG . . . . . . . . . . . . . . . . . . . . . . . . 103 4.3.3. Thực nghiệm và kết quả . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.3.3.1. Dữ liệu và tham số . . . . . . . . . . . . . . . . . . . . . . . . 105 4.3.3.2. Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . 106 4.4. Ngăn chặn thông tin sai lệch trên mô hình ngưỡng tuyến tính xác định . . . 111 4.4.1. Định nghĩa bài toán và độ phức tạp . . . . . . . . . . . . . . . . . . . 111 4.4.2. Các thuật toán đề xuất cho MMRD . . . . . . . . . . . . . . . . . . . . 113 4.4.3. Kết quả thực nghiệm với MMRD . . . . . . . . . . . . . . . . . . . . . 116 4.5. Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Chương 5. Ngăn chặn thông tin sai lệch có chủ đích 122 5.1. Phát biểu bài toán và độ phức tạp của bài toán . . . . . . . . . . . . . . . . 123 5.2. Các thuật toán đề xuất cho TMB trên mô hình LT . . . . . . . . . . . . . . . 126 5.2.1. Thuật toán tham lam . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 5.2.2. Thuật toán STMB-LT . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 5.2.3. Thực nghiệm và kết quả . . . . . . . . . . . . . . . . . . . . . . . . . 130 5.2.3.1. Dữ liệu và thiết lập tham số . . . . . . . . . . . . . . . . . . . 131 5.2.3.2. Các kết quả . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 5.3. Thuật toán cho TMB trên mô hình IC . . . . . . . . . . . . . . . . . . . . . . 135 v
5.3.1. Xây dựng hệ quy hoạch tuyến tính . . . . . . . . . . . . . . . . . . . . 135 5.3.2. Thuật toán STMB-IC . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 5.3.3. Thực nghiệm và kết quả . . . . . . . . . . . . . . . . . . . . . . . . . 140 5.3.3.1. Dữ liệu và thiết lập tham số . . . . . . . . . . . . . . . . . . . 141 5.3.3.2. Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . 143 5.4. Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 KẾT LUẬN 146 DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN 148 Tài liệu tham khảo 149 vi
DANH SÁCH HÌNH VẼ 1.1 Ví dụ cho mô hình LT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2 Ví dụ cho mô hình IC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.1 Mô tả sự khác nhau giữa TB-WPP và luật TB-PP . . . . . . . . . . . . . . 49 3.2 Ví dụ về cho hàm mục tiêu không có tính chất submodular . . . . . . . . 53 3.3 Mô tả khái quát Thuật toán SPBA . . . . . . . . . . . . . . . . . . . . . . 54 3.4 Mô tả cho CU (g, v) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.5 Mô tả cho CL (g, v) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.6 So sánh các thuật toán trong trường hợp chi phí tổng quát với τ = 5. . . . 70 3.7 So sánh các thuật toán trong trường hợp chi phí đồng nhất . . . . . . . . . 71 3.8 So sánh thời gian thực hiện của các thuật toán . . . . . . . . . . . . . . . 72 3.9 So sánh các thuật toán khi τ thay đổi và L cố định . . . . . . . . . . . . . 73 3.10 So sánh các thuật toán khi k thay đổi . . . . . . . . . . . . . . . . . . . . . 78 3.11 So sánh các thuật toán khi d thay đổi . . . . . . . . . . . . . . . . . . . . . 78 4.1 Xây dựng phép dẫn từ Knapsack đến MMR. . . . . . . . . . . . . . . . . . 86 4.2 Phép dẫn từ I1 tới I2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.3 Các thuật toán đề xuất cho MMR . . . . . . . . . . . . . . . . . . . . . . . 88 4.4 Cây T (I, d) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.5 Sơ lược về thuật toán SG . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 4.6 Sinh một cây từ đồ thị đã trộn đỉnh nguồn với d = 2 . . . . . . . . . . . . 98 4.7 Cập nhật cây và hàm h sau khi loại bỏ đỉnh . . . . . . . . . . . . . . . . . 99 4.8 Ví dụ xây dựng DAG từ G . . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.9 Chất lượng lời giải của các thuật toán với chi phí tổng quát . . . . . . . . 107 4.10 Chất lượng lời giải của các thuật toán với chi phí đồng nhất . . . . . . . . 108 4.11 Thời gian chạy của PR-DAG và SG trên bộ Oregon với chi phí tổng quát . 110 4.12 Thời gian chạy của PR-DAG và SG trên bộ Oregon với chi phí đồng nhất. 110 4.13 So sánh chất lượng lời giải và thời gian chạy của các thuật toán khi θ thay đổi và k = 50, d = 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 4.14 So sánh chất lượng lời giải và thời gian chạy của các thuật toán khi k thay đổi, d = 5, θ = 0.5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 4.15 So sánh chất lượng lời giải và thời gian chạy của các thuật toán khi d thay đổi, k = 50, θ = 0.5 với bộ dữ liệu Gnutella . . . . . . . . . . . . . . 120 vii
5.1 Ví dụ cho bài toán TBM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 5.2 Phép dẫn từ bài toán s-t paths đến TMB. . . . . . . . . . . . . . . . . . . . 123 5.3 Ví dụ tạo ra một cây gốc I từ G trên mô hình LT . . . . . . . . . . . . . . 129 5.4 So sánh chất lượng lời giải của các thuật toán cho TMB trên mô hình LT . 133 5.5 So sánh thời gian chạy của các thuật toán cho TBM trên mô hình LT . . . 134 5.6 Ví dụ sinh cây có gốc I từ đồ thị G dưới mô hình IC . . . . . . . . . . . . 139 5.7 So sánh chất lượng lời giải của các thuật toán trên mô hình IC . . . . . . . 142 5.8 So sánh thời gian chạy của các thuật toán trên mô hình IC . . . . . . . . . 143 viii
DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Tiếng Anh Tiếng Việt BCIM Budgeted Competitive Influence Bài toán Tối đa ảnh hưởng cạnh Maximization problem tranh với ngân sách và thời gian giới hạn CIM Competitive Influence Maxi- Bài toán Tối đa ảnh hưởng cạnh mization problem tranh CLT Competitive Linear Threshold Ngưỡng tuyến tính cạnh tranh DCLT Deterministic Time constraint Ngưỡng tuyến tính cạnh tranh Competitive Linear Threshold xác định theo thời gian FPTAS Fully Polynomial Time Approxi- mation Schema IC Independent Cascade Bậc độc lập IM Influence Maximization Cực đại ảnh hưởng LT Linear Threshold Ngưỡng tuyến tính MXHTT Online Social Network Mạng xã hội trực tuyến MMR Maximizing Misinformation Re- Hạn chế tối đa thông tin sai lệch striction problem OPT Optimal Solution Lời giải tối ưu RIS Reverse Influence Sampling Mẫu ảnh hưởng ngược SA Sandwich Approximation Xấp xỉ Sandwich STMB Scalable Targeted Misinforma- Thuật toán mở rộng cho TBM tion Blocking SPBA Sandwich based PBA Thuật toán Sandwich dựa trên PBA TCLT Time constraint Competitive Ngưỡng tuyến tính cạnh tranh với Linear Threshold thời gian ràng buộc TƯTH Combinatorial Optimization Tối ưu tổ hợp TTSL Misinformation/Disinformation Thông tin sai lệch TMB Targeted Misinformation Block- Ngăn chặn thông tin sai lệch có ing chủ đích ix
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.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.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.. trên MXHTT. 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]. 2. 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. 2. 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. 3. Để 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.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. 2. Đề 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. 3. Đề 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. 2. 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. 3. Trong một kịch bản khác, để hạn chế sự phát tán của thông tin sai lệch đảm bảo số người không bị ảnh hưởng bởi thông tin sai lệch lớn hơn một ngưỡng γ xác định, tác giả đề xuất nghiên cứu bài toán Hạn chế thông tin sai lệch có chủ đích (Targeted Misinformation Blocking-TMB). Tác giả đề xuất mô hình cho bài toán TMB, chỉ ra độ khó của bài toán trên các mô hình lan truyền thông tin phổ biến là IC và LT và đề xuất các thuật toán hiệu quả đối với bài toán này trên hai mô hình IC và LT tương ứng là STMB-IC và STMB-LT. Các kết quả thực nghiệm trên các dữ liệu MXHTT thực chỉ ra hiệu quả của các thuật toán đề xuất, đặc biệt các thuật toán có thể áp dụng cho các mạng cỡ lớn hàng trăm nghìn đỉnh. Kết quả nghiên cứu này được công bố tại hội nghị 4
quốc tế Asian Conference on Intelligent Information and Database Systems (ACIIDS) năm 2018 và tạp chí Journal of Combinatorial Optimization (SCIE) năm 2019. Các nội dung và kết quả nghiên cứu trong luận án được trình bày trong 03 bài báo trên các tạp chí quốc tế chuyên ngành thuộc danh mục SCIE và 04 bài báo trên các kỷ yếu hội nghị quốc tế có phản biện thuộc danh mục SCOPUS. Ngoài phần mở đầu và kết luận, bố cục của luận án chia thành 05 chương như sau: Chương 1 trình bày các kiến thức cơ bản về cơ chế lan truyền thông tin trên MX- HTT. Chương này cũng trình bày các mô hình phát tán thông tin cơ bản được nghiên cứu rộng rãi và các nghiên cứu liên quan đến hai bài toán IM và IB và mục tiêu của luận án trong việc giải quyết những biến thể với bài toán này. Chương 2 trình bày kiến thức cơ bản về các bài toán tối ưu tổ hợp. Một số thuật toán xấp xỉ thường sử dụng trong việc giải các bài toán TƯTH thuộc lớp NP-Khó, NP-đầy đủ nói chung cũng như các bài toán lan truyền thông tin nói riêng. Chương 3 trình bày các kết quả nghiên cứu đối với bài toán tối đa ảnh hưởng cạnh tranh với ràng buộc về thời gian và ngân sách, bao gồm: các mô hình lan truyền thông tin được đề xuất cho bài toán, tính chất của bài toán, thuật toán đề xuất và kết quả thực nghiệm trên các bộ dữ liệu thực. Chương 4 trình bày các kết quả nghiên cứu đối với bài toán hạn chế tối đa ảnh hưởng của một tập nguồn phát tán thông tin sai lệch cho trước với ràng buộc về thời gian và ngân sách. Tác giả đưa ra các tính chất của bài toán trên các mô hình lan truyền thông tin. Các thuật toán đề xuất cho kết quả nổi trội trên các bộ dữ liệu thực. Chương 5 trình bày các kết quả nghiên cứu đối với bài toán Hạn chế thông tin sai lệch có chủ đích. Khác với mục tiêu ở Chương 4, yêu cầu của bài toán này là tìm tập đỉnh nhỏ nhất để loại bỏ ra khỏi mạng sao cho số đỉnh bị ảnh hưởng bởi thông tin sai lệch giảm đi với một ngưỡng γ cho trước. 5
CHƯƠNG 1 TỔNG QUAN VỀ CÁC BÀI TOÁN LAN TRUYỀN THÔNG TIN Chương này trình bày các kiến thức tổng quan về MXHTT, các mô hình phát tán thông tin thường được sử dụng để giải quyết các bài toán về lan truyền thông tin và các nghiên cứu tổng quan về hai bài toán lan truyền thông tin quan trong là Tối đa ảnh hưởng (IM), Ngăn chặn ảnh hưởng (IB) cũng như phân tích các bài toán biến thể của chúng. Trên cơ sở đó, chương này cũng trình bày động lực nghiên cứu các bài toán trong luận án. 1.1. Giới thiệu về mạng xã hội Theo từ điển Cambrige 1 , một mạng xã hội ( MXHTT) là một trang web hoặc chương trình máy tính cho phép mọi người giao tiếp và chia sẻ thông tin trên internet bằng máy tính hoặc thiết bị di động. Những người tham gia vào MXHTT còn được gọi là cư dân mạng. Người dùng trên mạng (gọi tắt là người dùng) có thể giao tiếp, trao đổi thông tin với nhau bất chấp khoảng cách địa lý. Họ cũng có thể chia sẻ thông tin, ý kiến, quan điểm, hoặc chia sẻ các bài viết của người khác v.v.. Có thể nói, mỗi người dùng là một “phóng viên” trên MXHTT. Đặc tính này giúp cho các thông tin không những được phát tán nhanh chóng trên MXHTT mà nội dung của chúng còn rất đa dạng và phong phú. Ngoài ra, các MXHTT còn là nền tảng cho việc phát triển các ứng dụng, nên người dùng còn có thể tiến hành nhiều hoạt động khác do MXHTT cung cấp. Với sự phát triển của MXHTT hiện nay, ngày càng có nhiều MXHTT mới được lập để khai thác các khía cạnh khác nhau đáp ứng toàn diện nhu cầu người dùng. Số người dùng trên các MXHTT trong những năm gần đây tăng lên nhanh chóng, hiện nay có khoảng 3 tỷ người dùng trên tất cả các MXHTT [86]. Theo một nghiên cứu vào năm 2015, 63% số người sử dụng Facebook hay Twitter ở Mỹ xem các mạng này là nguồn thông tin chính thức v.v.. Những số liệu này cho thấy ngày càng có nhiều người dùng sử dụng MXHTT và chúng đóng vai trò quan trọng trong nhu cầu giao tiếp, giải trí, thu nhận thông tin của con người trong thời đại hiện nay. Với số lượng người dùng đông đảo, MXHTT gây ra những ảnh hưởng lớn tới thế giới thực trong tất cả các lĩnh vực đặc biệt là chính trị và kinh tế. Ví dụ, thông tin được lan truyền trên các MXHTT Facebook và Twitter có ảnh hưởng đến kết quả bầu cử ở Mỹ năm 2016 [3]. MXHTT có ảnh hưởng tới phong trào biểu tình chống chính phủ ở Ả-rập 1 https://dictionary.cambridge.org 6
vào năm 2010. Theo đó, các cơ quan chính phủ đã dập tắt được các cuộc biểu tình nhờ các thông tin về tổ chức biểu tình trên các MXHTT [105]. Thông tin sai lệch về việc Tổng thống Mỹ Barack Obama bị thương tại Nhà Trắng gián tiếp gây ra thiệt tại 136.5 tỷ Đô la Mỹ tới thị trường tài chính [31] v.v.. Các ví dụ này cũng minh chứng cho những tác động mạnh mẽ của MXHTT. Con người cần tận dụng được xu hướng công nghệ này trong việc phát triển kinh tế toàn cầu cũng như có những chính sách hợp lý trong việc hạn chế những tác động tiêu cực của MXHTT. 1.1.1. Những đặc điểm chung của MXHTT Có thể coi một MXHTT giống như một xã hội ảo mà mỗi tài khoản là một cá nhân trong thế giới thực. Ngoài ra, các MXHTT có một số đặc điểm nổi bật như sau: Đặc trưng thế giới nhỏ. Người ta đã kiểm chứng được rằng, đối với các MXHTT lớn khoảng cách trung bình kết nối giữa hai người dùng bất kỳ nhỏ hơn 6. Đây được coi là đặc trưng “thế giới nhỏ” của MXHTT [90, 29]. Với đặc trưng này, thông tin có thể dễ dàng lan truyền giữa các người dùng nhờ tính kết nối nhanh chóng. Đặc trưng tập nhân. Mỗi MXHTT chịu ảnh hưởng lớn của một số các nút quan trọng. Các nút này thường là những nút có bậc cao. Ngoài ra sự phân bố các nút có bậc cao cũng có sự phân cấp, tức là bao quanh những nút có bậc cao là những nút có bậc thấp hơn và tiếp tục như vậy. Đặc tính này có nhiều ứng dụng trong truyền thông và đánh giá cấu trúc mạng. Phân bố lũy thừa. Các nhà khoa học cũng đã chứng minh được, thông thường các MXHTT có dạng mạng scale-free [26]. Trong mạng này, các đỉnh có phân bố bậc được mô tả bởi hàm P (k) là xác suất một đỉnh có bậc là k . Phân bố này có dạng: 1 P (k) = kγ trong đó 2 < γ < 3. Cấu trúc cộng đồng Trong các MXHTT, thường xuyên tồn tại các nhóm cộng đồng có quy mô khác nhau. Các cộng đồng có thể hiểu đơn giản là nơi tập trung cao mật độ các liên kết trong mạng. Ngoài ra, cũng có những cộng đồng người dùng có cùng đặc điểm (sở thích). Có hai loại cấu trúc cộng đồng là: cộng đồng tách rời và cộng đồng chồng chéo. Việc nghiên cứu tính chất về cộng đồng có nhiều ứng dụng trong khoa học và thực tiễn. 1.1.2. Lợi ích của MXHTT Các nhà cung cấp dịch vụ MXHTT đã tận dụng các tính năng của MXHTT để mang lại nhiều lợi ích cho người dùng, đóng góp rất đáng kể vào sự phát triển của nền 7
kinh tế toàn cầu. Ứng dụng trong hoạt động kinh doanh. Các MXHTT đóng một vai trò quan trọng trong hoạt động của các doanh nghiệp. Các hoạt động quảng bá sản phẩm, giao dịch với khách hàng, đối tác, khảo sát ý kiến người dùng v.v.. đều có thể thực hiện một cách dễ dàng và thuận lợi trên nền tảng các dịch vụ MXHTT. Điều này dẫn đến sự phát triển trong toàn bộ các khâu của tiến trình sản xuất hàng hóa. Có thể nói trong các hoạt động này, hoạt động quảng bá sản phẩm thông qua các MXHTT đạt được nhiều thành công và thu hút được sự quan tâm của giới nghiên cứu nhất. Nhờ có hoạt động này, thông tin và các tính năng của sản phẩm được đưa đến người dùng một cách nhanh chóng và toàn diện hơn. Tìm kiếm các mối quan hệ. Con người hiện đại có ít thời gian dành cho bản thân và mở rộng các mối quan hệ. Nhờ có MXHTT, người dùng có thể tìm kiếm các mối quan hệ mới cũng như duy trì các mối quan hệ hiện có. Có nhiều người chỉ cần sử dụng MXHTT để giữ liên lạc với bạn bè và đồng nghiệp của họ. Họ có thể nói chuyện với nhau, tương tác với nhau trên MXHTT thay vì gặp nhau trực tiếp. Ứng dụng đối với các hoạt động của chính phủ. Các MXHTT gần đây đã cho thấy một giá trị lớn trong các phong trào xã hội và chính trị. Ví dụ: Trong cuộc cách mạng Ai Cập năm 2011, Facebook và Twitter đều đóng vai trò then chốt trong việc kết nối các cá nhân và tổ chức nổi dậy. Các nhà hoạt động Ai Cập đã đưa các thông tin về kế hoạch hoạt động cho nhóm người của họ trên các mạng này. Họ cũng đưa ra những bằng chứng cho hàng ngàn người về sự tàn bạo của chính phủ qua các video. Ngoài ra, các MXHTT còn cho phép chính phủ các nước giám sát ý kiến của công chúng trong các hoạt động chính trị hoặc các hiệu ứng xã hội khác nhau. 1.1.3. Những tác hại của MXHTT Sự phát tán virus và thư rác. Các MXHTT cũng là môi trường rất thuận lợi cho sự phát tán virus, mã độc. Các virus là phần mềm độc hại được phát triển nhằm thực hiện mục đích của kẻ tấn công. Ví dụ như: thu thập thông tin của người dùng nhằm truy cập vào thông tin cá nhân, thực hiện các hành vi lừa đảo v.v.. Dưới một môi trường thuận lợi cho việc lây lan nhanh chóng, nguy cơ này càng bùng phát trong thời gian gần đây. Một nguy cơ nữa cũng bùng phát cùng với sự phát triển của MXHTT đó là thư rác. Nội dung của các thư này thường là các thông điệp quảng cáo hoặc chứa virus qua nhiều hình thức khác nhau như: gửi thông điệp, bình luận trên các trang được nhiều người theo dõi, đề cập, v.v. Lừa đảo qua MXHTT. Mục đích của các đối tượng sử dụng phương pháp này nhằm 8
lấy được những thông tin riêng tư, có giá trị của người dùng bằng cách giả mạo một người đáng tin cậy trên mạng. Hoặc kẻ lừa đảo có thể tìm cách tấn công vào tài khoản của người dùng và chiếm quyền đăng nhập vào tài khoản của họ sau đó tiến hành các hoạt động xấu như tống tiền, giả mạo thông tin, thu thập thông tin từ người thân của nạn nhân, vv.. Những khảo sát gần đây cho thấy rằng người có khả năng bị lừa đảo bởi hình thức này cao hơn do bản chất tương tác của MXHTT giống như một xã hội thực. Trong những năm gần đây, hoạt động này có xu hướng tăng mạnh. Theo báo cáo tình báo an ninh của Microsoft, 84, 5% tất cả các cuộc tấn công lừa đảo nhắm vào người sử dụng trên các trang MXHTT. Sự phát tán thông tin sai lệch và tin đồn. Thông tin sai lệch là những thông tin giả mạo, không chính xác [42]. Có thể nói đây là một trong những thách thức lớn nhất hiện nay đối với cộng đồng người dùng trên MXHTT và tất cả các quốc gia có sử dụng các dịch vụ MXHTT. Nó không những có thể ảnh hưởng trực tiếp đến từng cá nhân mà còn gây ra những tổn thất về chính trị, nhận thức của cộng đồng và đặc biệt là tổn thất về kinh tế. Ví dụ, thông tin sai lệch về sự bùng phát dịch bệnh Ebola trên diện rộng gây ra sự hoang mang cho công chúng [69], hay theo các điều tra gần đây, thông tin sai lệch gây ảnh hưởng tới cuộc bầu cử tổng thống ở Mỹ vào năm 2016 và ở Pháp vào năm 2017 [3]. Thông tin sai lệch cho rằng Tổng thống Obama bị thương sau vụ hỏa hoạn ở nhà trắng gián tiếp gây thiệt hại tới thị trường chứng khoán là 136 tỷ Đô la [31]. Để ngăn chặn sự phát tán và tác hại của thông tin sai lệch, nhiều quốc gia đã xây dựng hệ thống chống tin giả mạo. Một số nước cũng đã yêu cầu các tổ chức cung cấp dịch vụ MXHTT cam kết loại bỏ sự hiện diện của thông tin sai lệch. 1.2. Các mô hình phát tán thông tin trên MXHTT Theo Roger [83], sự phát tán, khuếch tán là một quá trình mà một sự đổi mới được truyền đạt qua các kênh nhất định theo thời gian giữa các thành viên của một hệ thống xã hội. Có ba yếu tố quan trọng trong quá trình này là: thành viên trong hệ thống xã hội, sự tương tác lẫn nhau và các kênh truyền thông. Việc nghiên cứu các quá trình phát tán trong mỗi hoàn cảnh cụ thể là nền tảng giúp con người có thể giải quyết các vấn đề liên quan đến sự phát tán trong thực tế như: sự phát tán của dịch bệnh (trong y học, dịch tễ học), sự phát tán các ý kiến, tư tưởng giữa các cá nhân trong một xã hội, sự phát tán của virus trên một mạng máy tính, sự phát tán thông tin trên các MXHTT v.v.. Trong các MXHTT, thông tin được phát tán từ người dùng này đến người dùng khác thông qua nhiều hoạt động tương tác giữa các người dùng như: đăng bài, chia sẻ, bình luận v.v.. Quá trình này diễn ra tương đối nhanh và có những đặc điểm khác với 9