Luận án Tiến sĩ: Cực đại ảnh hưởng mạng xã hội với ưu tiên, chi phí - Vũ Chí Quang

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Ị. 10 CHƯƠNG I CƠ SỞ LÝ THUYẾT CỦA LUẬN ÁN VÀ CÁC NGHIÊN CỨU LIÊN QUAN .1 Giới thiệu về mạng xã hội .1 Các thành phần cơ bản của mạng xã hội .2 Một số đặc trưng chung của mạng xã hội .3 Lợi ích của mạng xã hội .4 Mặt trái của mạng xã hội .2 Các mô hình lan truyền thông tin trên mạng xã hội .1 Mô hình lan truyền thông tin rời rạc .2 Mô hình Ngưỡng tuyến tính (LT) .3 Mô hình Bậc độc lập (IC) .4 Mô hình cạnh trực tuyến (LE) .3 Một số bài toán lan truyền thông tin trên mạng xã hội .1 Cực đại ảnh hưởng (Influence Maximization - IM) .2 Phát hiện thông tin (Information Detection - ID) .3 Ngăn chặn ảnh hưởng (Influence Blocking - IB) .4 Một số bài toán khác trên mạng xã hội .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.1 Bài toán tối ưu tổ hợp .2 Phân loại các lớp bài toán trong tối ưu tổ hợp .3 Một số phương pháp giải bài toán tối ưu tổ hợp .1 Phương pháp xấp xỉ .2 Phương pháp Monte Carlo .3 Phương pháp Heuristic .4 Thuật toán luồng .5 Các nghiên cứu liên quan .1 Các nghiên cứu liên quan trong nước .2 Các nghiên cứu liên quan bài toán cực đại ảnh hưởng .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ủ đề.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 .2 Mô hình và Phát biểu bài toán .1 Mô hình mạng và mô hình IC .2 Phát biểu bài toán .3 Thuật toán tham lam tích hợp .4 Thuật toán lấy mẫu dựa trên tham lam tích hợp .1 Công cụ ước tính hàm ảnh hưởng .2 Mô tả thuật toán và phân tích lý thuyết .1 Mô tả thuật toán .2 Phân tích lý thuyết .5 Thực nghiệm và đánh giá kết quả .1 Cài đặt thực nghiệm .2 Kết quả thực nghiệm .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.3 Thuật toán luồng tất định khi β = 1 .1 Thuật toán luồng tất định với giá trị tối ưu đã biết .2 Thuật toán luồng tất định .4 Thuật toán luồng ngẫu nhiên cho trường hợp tổng quát .1 Thuật toán luồng ngẫu nhiên với giá trị tối ưu đã biết .2 Thuật toán luồng ngẫu nhiên .5 Thực nghiệm và đánh giá .1 Mục tiêu thực nghiệm .2 Thuật toán tham lam .3 Cực đại ảnh hưởng với k chủ đề bị hạn chế về chi phí .6 Kết luận chương. 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. Thống kê của bộ dữ liệu. 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. 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.

Ví dụ lan truyền thông tin cho mô hình LT. Ví dụ lan truyền thông tin cho mô hình IC. Nhóm bài toán lan truyền thông tin trên SN. Mô tả thuật toán luồng.

Ví dụ cho thấy sự khác biệt giữa IM và IMP. 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. 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. 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.

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. 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. 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. Kết quả về giá trị hàm ảnh hưởng của IMkB khi �=1.

Kết quả về số lời gọi hàm mục tiêu của IMkB khi �=1. Kết quả về thời gian chạy (s) của IMkB khi �=1. Kết quả giá trị hàm ảnh hưởng của IMkB trong trường hợp tổng quát .