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í

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ Vũ Chí Quang NGHIÊN CỨUMỘ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 VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ Vũ Chí Quang NGHIÊN CỨUMỘ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 Khoa học và Công nghệ Người hướng dẫn 1 (Ký, ghi rõ họ tên) Người hướng dẫn 2 (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 1MỤ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 21.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 33.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 4DANH 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 5Ký 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 6DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Tiếng Anh Tiếng Việt BkIM Budgeted k-Influence Maximization problem 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 CIM Competitive Influence Maximization problem Bài toán Cực đại ảnh hưởng cạnh tranh CLT Competitive Linear Threshold Ngưỡng tuyến tính cạnh tranh 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 IGS Integrated Greedy - based Sampling algorithm Thuật toán lấy mẫu dựa trên tham lam tích hợp IM Influence Maximization Cực đại ảnh hưởng IMkB Influence Maximization with k topics subject to the budget constraint problem Bài toán cực đại ảnh hưởng với k chủ đề bị hạn chế về chi phí IMP Influences Maximization with Priority problem Bài toán cực đại ảnh hưởng với ràng buộc ưu tiên 7LE 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 TRR Targeted Reverse Reachable Tập mẫu ảnh hưởng ngược có mục tiêu 8DANHMỤ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 9DANHMỤ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à các thuật toán khác. .....................................................................................................81 Hình 3.1. Kết quả về giá trị hàm ảnh hưởng của IMkB khi �=1 ............................113 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ôn