Mạng Xã Hội Và Bài Toán Tối Ưu Tổ Hợp

ĐẠ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

Hà Nội – 2020

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

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ị G0 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

Maximization problem

Bài toán Tối đa ảnh hưởng cạnh

tranh với ngân sách và thời gian

giới hạn

CIM Competitive Influence Maxi￾mization problem

Bài toán Tối đa ảnh hưởng cạnh

tranh

CLT Competitive Linear Threshold Ngưỡng tuyến tính cạnh tranh

DCLT Deterministic Time constraint

Competitive Linear Threshold

Ngưỡng tuyến tính cạnh tranh

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￾striction problem

Hạn chế tối đa thông tin sai lệch

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￾tion Blocking

Thuật toán mở rộng cho TBM

SPBA Sandwich based PBA Thuật toán Sandwich dựa trên

PBA

TCLT Time constraint Competitive

Linear Threshold

Ngưỡng tuyến tính cạnh tranh với

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￾ing

Ngăn chặn thông tin sai lệch có

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