Luận án Tiến sĩ Hệ thống thông tin: Nghiên cứu một số phương pháp giải bài toán cực đại ảnh hưởng trên mạng xã hội với ràng buộc ưu tiên và chi phí

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

Thêm vào BST

Báo xấu

3
lượt xem 1
download

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

Mục tiêu nghiên cứu của đề tài "Nghiên cứu một số phương pháp giải bài toán cực đại ảnh hưởng trên mạng xã hội với ràng buộc ưu tiên và chi phí" 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ần chú trọng nâng cao chất lượng lời giải cũng như khả năng ứng dụng đối với các mạng xã hội cỡ lớn hàng trăm nghìn, hàng triệu, thậm chí hàng tỷ cạnh hoặc nút.

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ĩ Hệ thống thông tin: Nghiên cứu một số phương pháp giải bài toán cực đại ảnh hưởng trên mạng xã hội với ràng buộc ưu tiên và chi phí

BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ Vũ Chí Quang NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN CỰC ĐẠI ẢNH HƯỞNG TRÊN MẠNG XÃ HỘI VỚI RÀNG BUỘC ƯU TIÊN VÀ CHI PHÍ LUẬN ÁN TIẾN SĨ HỆ THỐNG THÔNG TIN Hà Nội – Năm 2024
BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ Vũ Chí Quang NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN CỰC ĐẠI ẢNH HƯỞNG TRÊN MẠNG XÃ HỘI VỚI RÀNG BUỘC ƯU TIÊN VÀ CHI PHÍ LUẬN ÁN TIẾN SĨ HỆ THỐNG THÔNG TIN Mã số: 9 48 01 04 Xác nhận của Học viện Người hướng dẫn 1 Người hướng dẫn 2 Khoa học và Công nghệ (Ký, ghi rõ họ tên) (Ký, ghi rõ họ tên) Hà Nội – Năm 2024
LỜI CAM ĐOAN Tôi xin cam đoan luận án: “Nghiên cứu một số phương pháp giải bài toán cực đại ảnh hưởng trên mạng xã hội với ràng buộc ưu tiên và chi phí” là công trình nghiên cứu của chính mình dưới sự hướng dẫn khoa học của tập thể các thầy hướng dẫn. Luận án sử dụng thông tin trích dẫn từ nhiều nguồn tham khảo khác nhau và các thông tin trích dẫn được ghi rõ nguồn gốc. Các kết quả nghiên cứu của tôi được công bố chung với các tác giả khác đã được sự nhất trí của đồng tác giả khi đưa vào luận án. Các số liệu, kết quả được 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ỳ một công trình nào khác ngoài các công trình công bố của tác giả. Luận án được hoàn thành trong thời gian tôi làm nghiên cứu sinh tại Học viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Hà Nội, ngày 30 tháng 05 năm 2024 Tác giả luận án Vũ Chí Quang
LỜI CẢM ƠN 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 giáo hướng dẫn, TS Nguyễn Như Sơn và PGS.TS Ngô Quốc Dũng, các thầy đã giành nhiều thời gian, công sức để định hướng và hướng dẫn tôi hoàn thành các nghiên cứu của mình. Tôi xin chân thành cảm ơn Ban lãnh đạo và các thầy cô Học viện Khoa học và Công nghệ, Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã tạo điều kiện, giúp đỡ tôi trong quá trình học tập và nghiên cứu tại Học viện. Tôi xin gửi lời cảm ơn đến các nhà khoa học, các cộng sự đã có những góp ý quý báu giúp tôi hoàn thành các công bố cũng như hoàn thành luận án này. Tôi xin chân thành cảm ơn lãnh đạo và các đồng nghiệp của Khoa An ninh mạng và phòng chống tội phạm sử dụng công nghệ cao - Học viện An ninh nhân dân đã luôn hỗ trợ, giúp đỡ tôi trong suốt quá trình nghiên cứu. Xin cảm ơn những người thân, bạn bè đã cổ vũ động viên, chia sẻ những khó khăn cùng tôi trong thời gian qua. Cuối cùng, luận án này sẽ không thể hoàn thành được nếu thiếu sự động viên về mọi mặt của bố mẹ, anh chị em trong gia đình và của 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 nghiên cứu và trong cuộc sống. Xin trân trọng cảm ơn! Hà Nội, ngày 30 tháng 05 năm 2024 Tác giả luận án Vũ Chí Quang
1 MỤC LỤC MỤC LỤC ................................................................................................................... 1 DANH MỤC CÁC KÝ HIỆU ................................................................................... 4 DANH MỤC CÁC TỪ VIẾT TẮT ...........................................................................6 DANH MỤC CÁC BẢNG ......................................................................................... 8 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ...................................................................9 MỞ ĐẦU ................................................................................................................... 10 CHƯƠNG I CƠ SỞ LÝ THUYẾT CỦA LUẬN ÁN VÀ CÁC NGHIÊN CỨU LIÊN QUAN ............................................................................................................. 17 1.1 Giới thiệu về mạng xã hội ........................................................................... 17 1.1.1 Các thành phần cơ bản của mạng xã hội .....................................18 1.1.2 Một số đặc trưng chung của mạng xã hội ....................................19 1.1.3 Lợi ích của mạng xã hội ................................................................ 20 1.1.4 Mặt trái của mạng xã hội .............................................................. 21 1.2 Các mô hình lan truyền thông tin trên mạng xã hội ...........................23 1.2.1 Mô hình lan truyền thông tin rời rạc ............................................24 1.2.2 Mô hình Ngưỡng tuyến tính (LT) ................................................. 25 1.2.3 Mô hình Bậc độc lập (IC) ..............................................................27 1.2.4 Mô hình cạnh trực tuyến (LE) ...................................................... 29 1.3 Một số bài toán lan truyền thông tin trên mạng xã hội ...................... 32 1.3.1 Cực đại ảnh hưởng (Influence Maximization - IM) ................... 33 1.3.2 Phát hiện thông tin (Information Detection - ID) ....................... 34 1.3.3 Ngăn chặn ảnh hưởng (Influence Blocking - IB) ....................... 34 1.3.4 Một số bài toán khác trên mạng xã hội ........................................ 37 1.4 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. ..........................................................................................39 1.4.1 Bài toán tối ưu tổ hợp .................................................................... 39 1.4.2 Phân loại các lớp bài toán trong tối ưu tổ hợp ............................ 40 1.4.3 Một số phương pháp giải bài toán tối ưu tổ hợp ......................... 41 1.4.3.1 Phương pháp xấp xỉ ................................................................42 1.4.3.2 Phương pháp Monte Carlo .....................................................44
2 1.4.3.3 Phương pháp Heuristic ...........................................................44 1.4.3.4 Thuật toán luồng .....................................................................45 1.5 Các nghiên cứu liên quan .................................................................... 46 1.5.1 Các nghiên cứu liên quan trong nước ..........................................46 1.5.2 Các nghiên cứu liên quan bài toán cực đại ảnh hưởng ..............47 1.5.3 Các nghiên cứu liên quan bài toán cực đại ảnh hưởng lan truyền thông tin nhiều chủ đề. ...................................................................................... 50 1.6 Kết luận chương .................................................................................... 52 CHƯƠNG 2 CỰC ĐẠI ẢNH HƯỞNG VỚI RÀNG BUỘC ƯU TIÊN TRÊN MẠNG XÃ HỘI ........................................................................................................53 2.1 Đặt vấn đề ...............................................................................................54 2.2 Mô hình và Phát biểu bài toán ........................................................... 56 2.2.1 Mô hình mạng và mô hình IC .......................................................56 2.2.2 Phát biểu bài toán .......................................................................... 58 2.3 Thuật toán tham lam tích hợp ............................................................58 2.4 Thuật toán lấy mẫu dựa trên tham lam tích hợp ........................... 62 2.4.1 Công cụ ước tính hàm ảnh hưởng ................................................62 2.4.2 Mô tả thuật toán và phân tích lý thuyết ........................................65 2.4.2.1 Mô tả thuật toán ......................................................................65 2.4.2.2 Phân tích lý thuyết .................................................................. 66 2.5 Thực nghiệm và đánh giá kết quả ..................................................... 74 2.5.1 Cài đặt thực nghiệm .......................................................................74 2.5.2 Kết quả thực nghiệm ......................................................................75 2.6 Kết luận chương .................................................................................... 84 CHƯƠNG 3 CỰC ĐẠI ẢNH HƯỞNG BÀI TOÁN LAN TRUYỀN THÔNG TIN NHIỀU CHỦ ĐỀ VỚI CHI PHÍ GIỚI HẠN. ...............................................85 3.1 Đặt vấn đề ...............................................................................................85 3.2 Các ký hiệu ............................................................................................. 87 3.3 Thuật toán luồng tất định khi β = 1 .................................................. 89 3.3.1 Thuật toán luồng tất định với giá trị tối ưu đã biết ..................... 89
3 3.3.2 Thuật toán luồng tất định ..............................................................95 3.4 Thuật toán luồng ngẫu nhiên cho trường hợp tổng quát ..............99 3.4.1 Thuật toán luồng ngẫu nhiên với giá trị tối ưu đã biết ............... 99 3.4.2 Thuật toán luồng ngẫu nhiên ..................................................... 106 3.5 Thực nghiệm và đánh giá .................................................................. 108 3.5.1 Mục tiêu thực nghiệm ..................................................................108 3.5.2 Thuật toán tham lam ....................................................................109 3.5.3 Cực đại ảnh hưởng với k chủ đề bị hạn chế về chi phí ............. 111 3.6 Kết luận chương .................................................................................. 118 KẾT LUẬN ............................................................................................................. 119 DANH MỤC CÔNG TRÌNH CÔNG BỐ LIÊN QUAN ĐẾN LUẬN ÁN ....... 121 TÀI LIỆU THAM KHẢO ..................................................................................... 122
4 DANH MỤC CÁC KÝ HIỆU Ký hiệu Diễn giải �(�, �) Đồ thị biểu diễn mạng xã hội, gồm tập nút �, tập cạnh � �, � Số nút và số cạnh của đồ thị � �, � �� (�), �� (�) Tập nút vào và tập nút ra của nút � �� (�), �� (�) Bậc tương ứng vào và ra của nút v S Tập nguồn (Nguồn lan truyền thông tin) � � Hàm ảnh hưởng �� Ngưỡng kích hoạt nút u w(u, v) Trọng số cạnh (u, v) �(�, �) Xác suất ảnh hưởng dg(S, u) Khoảng cách từ S đến u trên đồ thị g � � Hàm ước lượng �~� Đồ thị mẫu sinh ra từ đồ thị � Ω Tập các ràng buộc OPT Lời giải tối ưu �� Ảnh hưởng độ lan truyền của S đến U R(g, SU) Ký hiệu tập hợp các nút trong U có thể tới từ S trong đồ thị g ��() Hàm trả về các đối số tại đó giá trị của hàm số đạt cực đại
5 Ký hiệu Diễn giải ℛ Tập các bộ mẫu �� Tập mẫu RR với nút nguồn u cho đồ thị mẫu g �� Tập mẫu TRR với nút nguồn u cho đồ thị mẫu g Xg(S) và �� (�) Biến ngẫu nhiên được xây dựng từ các mẫu RR và TRR �� (S2, ℛ 2, δ) Hàm tính cận dưới của � �2 Fu(S2, ℛ2, δ) Hàm tính cận trên của một giải pháp tối ưu Kỳ vọng
6 DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Tiếng Anh Tiếng Việt Bài toán cực đại ảnh hưởng lan Budgeted k-Influence BkIM truyền thông tin nhiều chủ đề với Maximization problem chi phí giới hạn Competitive Influence Bài toán Cực đại ảnh hưởng cạnh CIM Maximization problem tranh Competitive Linear Ngưỡng tuyến tính cạnh tranh CLT Threshold CO Combination Optimization Tối ưu tổ hợp IB Influences Blocking Ngăn chặn ảnh hưởng IC Independent Cascade Bậc độc lập ID Information Detection Phát hiện thông tin IG Integrated Greedy algorithm Thuật toán tham lam tích hợp Integrated Greedy - based Thuật toán lấy mẫu dựa trên tham IGS Sampling algorithm lam tích hợp IM Influence Maximization Cực đại ảnh hưởng Influence Maximization with Bài toán cực đại ảnh hưởng với k IMkB k topics subject to the budget chủ đề bị hạn chế về chi phí constraint problem Influences Maximization Bài toán cực đại ảnh hưởng với IMP with Priority problem ràng buộc ưu tiên
7 LE Live Edge Cạnh trực tuyến LT Linear Threshold Ngưỡng tuyến tính MC Monte Carlo Mô phỏng Monte Carlo MI MisInformation Thông tin sai lệch NCS Postgraduate Nghiên cứu sinh RR Reverse Reachable Tập mẫu ảnh hưởng ngược SI Spread Information Lan truyền thông tin SN Social Network Mạng xã hội Tập mẫu ảnh hưởng ngược có mục TRR Targeted Reverse Reachable tiêu
8 DANH MỤC CÁC BẢNG Tên và nội dung bảng Trang Bảng 2.1. Thống kê của bộ dữ liệu................................................................... 74 Bảng 2.2. So sánh về σ(S) và σU(S) giữa IGS và các thuật toán khác với k = 500, U = 1000 và T = 100 → 500..................................................................... 79 Bảng 2.3. So sánh mức sử dụng bộ nhớ (MB) giữa IGS và các thuật toán khác. ............................................................................................................................83
9 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Tên hình vẽ, đồ thị Trang Hình 1.1. Ví dụ lan truyền thông tin cho mô hình LT................................................27 Hình 1.2. Ví dụ lan truyền thông tin cho mô hình IC.................................................28 Hình 1.3. Nhóm bài toán lan truyền thông tin trên SN .............................................. 32 Hình 1.4. Mô tả thuật toán luồng ................................................................................46 Hình 2.1. Ví dụ cho thấy sự khác biệt giữa IM và IMP ............................................. 55 Hình 2.2. So sánh mức độ lan truyền ảnh hưởng trên cơ sở dữ liệu netHEPT với k=100 → 500, T=100 và U size =200. ....................................................................... 76 Hình 2.3. So sánh mức độ lan truyền ảnh hưởng trên cơ sở dữ liệu ENRON với k=100 → 500, T=100 và U size =200. ....................................................................... 76 Hình 2.4. So sánh mức độ lan truyền ảnh hưởng trên cơ sở dữ liệu netPHY với k=100 → 500, T=100 và U size =200. ....................................................................... 77 Hình 2.5. So sánh mức độ lan truyền ảnh hưởng trên cơ sở dữ liệu DBLP với k=100 → 500, T=100 và U size =200. ...................................................................................77 Hình 2.6. So sánh mức độ lan truyền ảnh hưởng trên cơ sở dữ liệu RETWEET với k=100 → 500, T=100 và U size =200. ....................................................................... 77 Hình 2.7. So sánh về thời gian chạy (s) với k thay đổi từ 150 đến 200 giữa IGS và Hình 3.1. Kết quả về giá trị hàm ảnh hưởng của IMkB khi �=1 ............................113 các thuật toán khác. .....................................................................................................81 Hình 3.2. Kết quả về số lời gọi hàm mục tiêu của IMkB khi �=1 ......................... 114 Hình 3.3. Kết quả về thời gian chạy (s) của IMkB khi �=1 ................................... 115 Hình 3.4. Kết quả giá trị hàm ảnh hưởng của IMkB trong trường hợp tổng quát ..116 Hình 3.5. Kết quả lời gọi hàm mục tiêu của IMkB trong trường hợp tổng quát .... 117 Hình 3.6. Kết quả về thời gian chạy (s) của IMkB trong trường hợp tổng quát ......118
10 MỞ ĐẦU 1. Lý do chọn đề tài - Về mặt thực tiễn: Trong những năm gần đây, cùng với sự phát triển của công nghệ thông tin, mạng máy tính và công nghệ Web đã mang lại nhiều nền tảng để kết nối toàn cầu, trong đó nổi bật nhất là mạng xã hội (Social Network - SN), trên SN mọi người cùng nhau kết nối, bất chấp không gian, thời gian để giải trí, học tập và kinh doanh. Khi sử dụng mạng xã hội người dùng có thể trở thành một phóng viên đưa tin và viết tin. Các vấn đề xã hội trên thế giới nói chung và ở Việt Nam nói riêng nhờ có mạng xã hội đã lan truyền thông tin đến được với nhiều người dùng hơn, nhanh hơn, từ đó giúp con người nâng cao nhận thức xã hội, giúp đưa ra các giải pháp hiệu quả và kịp thời cho những vấn đề cộng đồng quan tâm. Có thể nói mạng xã hội đã bùng nổ trong những năm gần đây, là môi trường lan truyền thông tin nhanh chóng và sâu rộng, làm ảnh hưởng sâu sắc và mạnh mẽ đến cuộc sống hàng ngày của con người. Ngày nay, mạng xã hội trở thành một công cụ hữu ích để lan truyền thông tin, quảng bá sản phẩm và là một kho tri thức mà mọi người có thể dễ dàng tiếp cận. Cùng với những lợi ích trên, thì mạng xã hội cũng mang lại nhiều rủi ro cho người dùng, như lây nhiễm mã độc, lộ lọt thông tin cá nhân, mất tài khoản, lừa đảo trên mạng, vv… Đặc biệt, với khoảng gần 5 tỷ1 người dùng trên khắp thế giới, SN đã và đang trở thành nơi chia sẻ và lan truyền thông tin với tốc độ nhanh hơn bất kỳ nền tảng nào khác. Theo các nghiên cứu gần đây, người dùng ngày càng thích trao đổi thông tin trên SN nhiều hơn là các tin tức truyền thống [1], [2]. Vì vậy cần nghiên cứu các giải pháp hiệu quả để thông tin lan truyền đến người dùng trên mạng xã hội nhanh nhất, hiệu quả nhất. 1 https://www.smartinsights.com/social-media-marketing/social-media-strategy.
11 - Về mặt khoa học: Nghiên cứu bài toán cực đại ảnh hưởng trên SN là hướng nghiên cứu được nhiều nhà khoa học quan tâm, bài toán này thuộc nhóm các bài toán lan truyền thông tin (Spread Information - SI), đòi hỏi kết hợp giữa các phương pháp, kỹ thuật từ nhiều lĩnh vực khác nhau như: khai phá dữ liệu đồ thị, học máy, học sâu, tính toán tối ưu, vv... Bên cạnh đó, SN có khối dữ liệu khổng lồ, phân tán và quá trình lan truyền thông tin ngẫu nhiên, cấu trúc mạng phức tạp, không đồng nhất và liên tục biến động. Do đó cần phải đưa ra các giải pháp hiệu quả về mặt thời gian và bộ nhớ. Mặc dù đã có nhiều nghiên cứu được công bố, nhưng các bài toán trên vẫn còn nhiều thách thức chưa được giải quyết như: xử lý các ràng buộc ưu tiên hay xử lý với chi phí giới hạn đối với các bài toán cực đại ảnh hưởng. Căn cứ vào những lý do trên, đề tài của luận án là: “Nghiên cứu một số phương pháp giải bài toán cực đại ảnh hưởng trên mạng xã hội với ràng buộc ưu tiên và chi phí” có tính cấp thiết và quan trọng cả về mặt thực tiễn và khoa học trong việc tìm ra các giải pháp hiệu quả để cực đại ảnh hưởng lan truyền thông tin trên SN, góp phần xây dựng hệ thống SN ngày càng hữu ích hơn với người dùng. Nội dung nghiên cứu của luận án bao gồm 02 bài toán như sau: a. Cực đại ảnh hưởng với ràng buộc ưu tiên (Influences Maximization with Priority - IMP) Mục tiêu của bài toán IMP là tìm tập nguồn S có kích thước k để bài toán có ảnh hưởng đến U ít nhất là T (U là tập ưu tiên, T là Ngưỡng đạt được trong tập ưu tiên) và tổng ảnh hưởng đến các nút trong mạng đạt cực đại. Đây là bài toán thuộc nhóm bài toán cực đại ảnh hưởng (Influences Maximization - IM) bài toán này đã và đang được nhiều nhà khoa học quan tâm nghiên cứu, điển hình là các công bố: [3] - [8], vv… Ngày nay, các biến thể có tính ứng dụng cao của bài toán IM đang được rất nhiều nhà khoa học quan tâm nghiên cứu.
12 - Biến thể theo thời gian [9], [10], theo chi phí [11] - [14], theo khoảng cách [15], theo chủ đề quan tâm [16]. - Trong trường hợp biến thể có các đối thủ cạnh tranh cần cực đại ảnh hưởng của một đối thủ khi lan truyền thông tin có sự cạnh tranh (bài toán cực đại ảnh hưởng cạnh tranh - CIM) [4], [17] - [22]. b. Cực đại ảnh hưởng lan truyền thông tin nhiều chủ đề với chi phí giới hạn (Budgeted k-Influence maximization - BkIM): Bài toán cực đại ảnh hưởng với nhiều chủ đề là một lớp bài toán thuộc nhóm bài toán cực đại ảnh hưởng (IM), trong đó mỗi người dùng trong mạng có thể được liên kết với nhiều chủ đề khác nhau. Ví dụ, trong SN một người dùng có thể quan tâm đến nhiều chủ đề khác nhau như thể thao, âm nhạc, du lịch, văn hóa, chính trị, vv... Bài toán cực đại ảnh hưởng với nhiều chủ đề sẽ giúp tìm ra tập người dùng trong SN có tác động lớn nhất đến mỗi chủ đề cụ thể. Bài toán cực đại ảnh hưởng với nhiều chủ đề có chi phí giới hạn là một biến thể của bài toán cực đại ảnh hưởng với nhiều chủ đề trên mạng xã hội, trong đó mỗi người dùng trong mạng có thể được liên kết với nhiều chủ đề khác nhau và việc tối đa hóa tác động của người dùng đến các chủ đề cụ thể có một chi phí tương ứng. Việc giải quyết bài toán không chỉ đơn thuần tìm được tập người dùng có ảnh hưởng lớn nhất mà còn phải thỏa mãn được tiêu chí không vượt quá chi phí đề ra. Hiện nay, đã có nhiều nghiên cứu giải quyết cho bài toán cực đại ảnh hưởng với nhiều loại ràng buộc khác nhau, điển hình là các công bố: [23] - [30], vv… 2. Một số thách thức Bài toán cực đại ảnh hưởng với ràng buộc ưu tiên (IMP) và bài toán cực đại ảnh hưởng lan truyền thông tin nhiều chủ đề với chi phí giới hạn (BkIM) đã và đang nhận được nhiều sự quan tâm nghiên cứu của các nhà khoa học theo nhiều bối cảnh khác nhau. Tuy nhiên, vẫn còn nhiều vấn đề chưa được
13 giải quyết hoặc có thể cải tiến thêm. Khi nghiên cứu các bài toán này, các nhà khoa học cũng như luận án phải đối mặt với một số thách thức, cụ thể như sau: - Các bài toán cực đại ảnh hưởng thường thuộc lớp bài toán tối ưu tổ hợp có độ phức tạp tính toán là NP-Khó. Bên cạnh đó, việc tính toán hàm mục tiêu có độ phức tạp tính toán là #P-Khó [5], [6]. Do đó, cần phải có những thuật toán hiệu quả để đưa ra lời giải tốt trong thời gian cho phép. - Với sự phát triển của các Mạng xã hội ngày nay (hàng triệu, hàng tỷ người dùng), cần đưa ra các thuật toán hoặc cách tiếp cận hiệu quả hơn cho những bài toán trên để chúng mang tính thực tiễn cao. - Để nâng cao tính ứng dụng của các bài toán, cần nghiên cứu các biến thể phù hợp với thực tế theo nhiều khía cạnh khác nhau như: ràng buộc ưu tiên, chi phí, thời gian, lợi ích, khoảng cách, tính cạnh tranh, vv... 3. Mục tiêu của luận án Để góp phần giải quyết các thách thức đối với các bài toán đề xuất, luận án đưa ra các mục tiêu như sau: - Nghiên cứu các bài toán cực đại ảnh hưởng trên các mô hình lan truyền thông tin. Từ đó đề xuất các biến thể mới của bài toán như cực đại ảnh hưởng với ràng buộc ưu tiên và cực đại ảnh hưởng lan truyền thông tin nhiều chủ đề với chi phí giới hạn để các bài toán này có thể ứng dụng được trong thực tiễn. - Đưa ra 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 đang được các nhà khoa họ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ần chú trọng nâng cao chất lượng lời giải cũng như khả năng ứng dụng đối với các mạng xã hội cỡ lớn hàng trăm nghìn, hàng triệu, thậm chí hàng tỷ cạnh hoặc nút.
14 Để đạt được các mục tiêu trên, luận án đã sử dụng các phương pháp nghiên cứu sau: - Nghiên cứu lý thuyết các bài toán tối ưu tổ hợp (Combination Optimization - CO), độ phức tạp tính toán 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 các lớp NP- Khó, NP-đầy đủ, #P-Khó. - Nghiên cứu và phân tích những công trình đã công bố liên quan đến cơ chế, mô hình và các bài toán về lan truyền thông tin. Từ đó, 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 chứng minh một cách chặt chẽ phù hợp cả về mặt lý thuyết lẫn thực nghiệm. - Các thuật toán đề xuất mới đều được phân tích đánh giá, chứng minh chặt chẽ thông qua phân tích lý thuyết dưới dạng các Bổ đề, Định lý. NCS kết hợp với các phương pháp thực nghiệm sử dụng các bộ dữ liệu khác nhau nhằm đảm bảo tính khách quan, tính hiệu quả của phương pháp đề xuất. 4. Các đóng góp của luận án Các nghiên cứu của luận án được công bố trên 02 tạp chí quốc tế thuộc danh mục SCIE/SCOPUS; 01 bài báo hội thảo quốc tế thuộc danh mục SCOPUS và 02 bài hội thảo trong nước. Trong đó, nội dung chính của luận án được thể hiện trong hai bài toán sau: - Bài toán 1: “Cực đại ảnh hưởng với ràng buộc ưu tiên", bài toán được đặt tên là IMP (Influence Maximization with Priority). Mục tiêu của bài toán IMP là chọn tập nguồn S có k nút có thể ảnh hưởng của tập hợp ưu tiên nhất định U lớn hơn ngưỡng T nhằm điều chỉnh ảnh hưởng của tập nguồn đến tập ưu tiên. Mặc dù hàm mục tiêu (hàm ảnh hưởng) vẫn là một hàm đơn điệu và hàm Submodular, nhưng khi xem xét ràng buộc ưu tiên, các thuật toán IM mới nhất không thể được áp dụng được. Để giải quyết thách thức này, luận án đề xuất hai thuật toán IG (Integrated Greedy) và IGS (Integrated Greedy - based Sampling) với các đảm bảo lý thuyết có thể chứng minh được, luận án chỉ ra
15 rằng IG là thuật toán tham lam tích hợp cung cấp một nghiệm gần đúng 1 − 1− 1 � � ; IGS là một thuật toán xấp xỉ ngẫu nhiên hiệu quả dựa trên phương pháp lấy mẫu trả về một nghiệm gần đúng 1 − 1 − k − � với xác suất ít 1 t nhất là 1 - δ với � > 0, δ ∈ (0, 1) làm tham số đầu vào của bài toán. Kết quả nghiên cứu được xuất bản trên tạp chí Algorithms 2020, tập 13, số 183; doi:10.3390/a13080183. - Bài toán 2: “Cực đại ảnh hưởng lan truyền thông tin nhiều chủ đề với chi phí giới hạn”, bài toán được đặt tên là BkIM (Budgeted k-Influence maximization). Luận án đề xuất hai thuật toán luồng duyệt dữ liệu một lần cung cấp giới hạn lý thuyết của bài toán BkIM. + Đối với trường hợp đặc biệt: một phần tử chỉ có một giá trị chi phí luồng tất định duyệt dữ liệu 1 lần, có độ phức tạp truy vấn là �( log �), độ khi được thêm vào phần tử thứ i bất kỳ, trước tiên luận án đề xuất thuật toán �� phức tạp không gian là �( � log �) và trả về một tỷ lệ gần đúng là − � khi � 1 4 f là đơn điệu và 5 − � khi f không đơn điệu đối với bất kỳ tham số đầu vào 1 nào � ∈ (0, 5 ). 1 nhiên duyệt dữ liệu 1 lần, có độ phức tạp truy vấn là �( log �), độ phức tạp + Đối với trường hợp tổng quát: luận án đề xuất thuật toán luồng ngẫu �� không gian là �( � log �) và trả về một tỷ lệ gần đúng là min { 2 , }− � ∝ 1−∝ � 1+� �−� � khi f là đơn điệu và min { 2 , } − � khi f không đơn điệu, ở đây ∝ 1−∝ � 1+2� �−2� � = ��∈�, �, � ∈ � , � ≠� �� và � ∈ (0, 1) là tham số đầu vào. Kết quả được � (�) � (�) đăng trên kỷ yếu hội nghị quốc tế “In: Mohaisen, D., Jin, R. (eds) Computational Data and Social Networks. CSoNet 2021. Lecture Notes in Computer Science(), vol 13116. Springer, Cham.” thuộc danh mục SCOPUS và xuất bản trên tạp chí Journal of Combinatorial Optimization tập 44, trang 723–751.
16 5. Bố cục của luận án Bố cục của luận án được chia làm 3 chương như sau: Chương 1: Cơ sở lý thuyết của luận án và các nghiên cứu liên quan Trong chương này, luận án giới thiệu về mạng xã hội, các thành phần cơ bản, một số đặc trưng, những lợi ích và mặt trái của mạng xã hội; Giới thiệu các mô hình và một số bài toán lan truyền thông tin phổ biến trên mạng xã hội; Một số kiến thức cơ bản sử dụng trong luận án; Đây là những kiến thức tổng quan, mang tính nền tảng cho các chương sau của luận án. Chương 2: Cực đại ảnh hưởng với ràng buộc ưu tiên trên mạng xã hội Nội dung của chương này, luận án đặt vấn đề và định nghĩa bài toán IMP trên mô hình lan truyền thông tin; đề xuất thuật toán tham lam tích hợp (IG) và thuật toán lấy mẫu dựa trên tham lam tích hợp (IGS) cho bài toán IMP; chứng minh hiệu suất thuật toán đạt xấp xỉ so với phương án tối ưu; Phân tích lý thuyết và đánh giá thuật toán dựa trên thực nghiệm với các bộ dữ liệu của mạng xã hội trong thực tế. Chương 3: Cực đại ảnh hưởng lan truyền thông tin nhiều chủ đề với chi phí giới hạn. Chương này luận án đề xuất mô hình mới cho bài toán cực đại ảnh hưởng lan truyền thông tin nhiều chủ đề, định nghĩa bài toán BkIM, đề xuất hai thuật toán luồng duyệt dữ liệu một lần cung cấp giới hạn lý thuyết của bài toán BkIM. Để xem xét hiệu suất của các thuật toán đề xuất trong thực tế, luận án tiến hành các thực nghiệm trên ứng dụng: Cực đại ảnh hưởng với k chủ đề trong điều kiện chi phí giới hạn.