Một số bài toán tối ưu trên mạng xã hội

ĐẠI HỌC MEDUSA 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 – 2024 ĐẠI HỌC MEDUSA 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. TS Kiều Mai Chi 2. TS Giang Thanh Ảnh Hà Nội – 2024 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 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. Giới thiệu về mạng xã hội. Những đặc điểm chung của MXHTT. Lợi ích của MXHTT.

Những tác hại của MXHTT. Các mô hình phát tán thông tin trên MXHTT. Mô hình phát tán thông tin rời rạc. Mô hình Ngưỡng tuyến tính (LT).

Mô hình Bậc độc lập (IC). Mô hình cạnh trực tuyến (live-edge). Một số bài toán lan truyền thông tin trên MXHTT. Tối đa ảnh hưởng (IM).

Các thuật toán cho bài toán IM. Một số biến thể của bài toán cực đại ảnh hưởng. Ngăn chặn ảnh hưởng (IB). Loại bỏ tập người dùng và liên kết.

Tẩy nhiễm thông tin. Kết luận chương. 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. Bài toán TƯTH.

Phân loại các lớp bài toán trong TƯTH. Một số phương pháp giải bài toán TƯTH. Thuật toán xấp xỉ. Phương pháp Mote-Carlo.

Bài toán tìm giá trị cực đại. Bài toán uớc lượng kỳ vọng của một biến ngẫu nhiên. Thuật toán heuristic cấu trúc. Thuật toán Metaheuristic.

Kết luận chương. 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. Đặt vấn đề và phát biểu bài toán. Phát biểu bài toán và mô hình đề xuất.

Bài toán BCIM. Mô hình ảnh hưởng cạnh tranh. Thuật toán xấp xỉ cho bài toán BCIM. Các hàm xấp xỉ trên và xấp xỉ dưới.

Hàm xấp xỉ trên. Hàm xấp xỉ dưới. Thuật toán PBA cho bài toán cực đại các hàm xấp xỉ. Mô tả thuật toán PBA.

Phân tích tỷ lệ xấp xỉ của thuật toán PBA. Phân tích độ phức tạp. Thuật toán SPBA cho bài toán BCIM. Thực nghiệm và kết quả.

Dữ liệu và tham số. Kết quả thực nghiệm. Trường hợp chi phí tổng quát. Trường hợp chi phí đồng nhất.

So sánh thời gian chạy. Ảnh hưởng của bước thời gian τ. 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. Mô hình và định nghĩa bài toán.

Các thuật toán cho CIM trên mô hình DCLT. 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.

Đặt vấn đề và phát biểu bài toán. Phát biểu bài toán. Mô hình ngưỡng tuyến tính ràng buộc thời gian (TLT). Hàm mục tiêu.

Độ khó của bài toán. Các thuật toán cho MMR. Các thuật toán xấp xỉ. Thuật toán FPTAS trong trường hợp cây có gốc.

Thuật toán xấp xỉ trong trường hợp tổng quát. Thuật toán tham lam tăng tốc (SG). Thuật toán heuristic PR-DAG. Xây dựng DAG từ đồ thị ban đầu.

Ước lượng hàm mục tiêu dựa trên DAG. Thuật toán PR-DAG. Thực nghiệm và kết quả. Dữ liệu và tham số.

Kết quả thực nghiệm. Ngăn chặn thông tin sai lệch trên mô hình ngưỡng tuyến tính xác định. Định nghĩa bài toán và độ phức tạp. Các thuật toán đề xuất cho MMRD.

Kết quả thực nghiệm với MMRD. Kết luận chương. Ngăn chặn thông tin sai lệch có chủ đích 122 5. Phát biểu bài toán và độ phức tạp của bài toán.

Các thuật toán đề xuất cho TMB trên mô hình LT. Thuật toán tham lam. Thuật toán STMB-LT. Thực nghiệm và kết quả.

Dữ liệu và thiết lập tham số. Thuật toán cho TMB trên mô hình IC. Xây dựng hệ quy hoạch tuyến tính. Thuật toán STMB-IC.

Thực nghiệm và kết quả. Dữ liệu và thiết lập tham số. Kết quả thực nghiệm. 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 .2 Ví dụ cho mô hình IC .1 Mô tả sự khác nhau giữa TB-WPP và luật TB-PP .2 Ví dụ về cho hàm mục tiêu không có tính chất submodular .3 Mô tả khái quát Thuật toán SPBA .4 Mô tả cho CU (g, v) .5 Mô tả cho CL (g, v) .6 So sánh các thuật toán trong trường hợp chi phí tổng quát với τ = 5.7 So sánh các thuật toán trong trường hợp chi phí đồng nhất .8 So sánh thời gian thực hiện của các thuật toán .9 So sánh các thuật toán khi τ thay đổi và L cố định .10 So sánh các thuật toán khi k thay đổi .11 So sánh các thuật toán khi d thay đổi .1 Xây dựng phép dẫn từ Knapsack đến MMR.2 Phép dẫn từ I1 tới I2 .3 Các thuật toán đề xuất cho MMR .5 Sơ lược về thuật toán SG .6 Sinh một cây từ đồ thị đã trộn đỉnh nguồn với d = 2 .7 Cập nhật cây và hàm h sau khi loại bỏ đỉnh .8 Ví dụ xây dựng DAG từ G .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 .10 Chất lượng lời giải của các thuật toán với chi phí đồng nhất .11 Thời gian chạy của PR-DAG và SG trên bộ Oregon với chi phí tổng quát .12 Thời gian chạy của PR-DAG và SG trên bộ Oregon với chi phí đồng nhất.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.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.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 .1 Ví dụ cho bài toán TBM .2 Phép dẫn từ bài toán s-t paths đến TMB.3 Ví dụ tạo ra một cây gốc I từ G trên mô hình LT .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 .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 .6 Ví dụ sinh cây có gốc I từ đồ thị G0 dưới mô hình IC .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 .8 So sánh thời gian chạy của các thuật toán trên mô hình IC .