BỘ GIÁO DỤC
ĐÀO TẠO
VIỆN HÀN LÂM KHOA HỌC
CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC CÔNG NGHỆ
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 HỘI
VỚI RÀNG BUỘC ƯU TIÊN CHI PHÍ
LUẬN ÁN TIẾN HỆ THỐNG THÔNG TIN
Nội Năm 2024
BGIÁO DC
ĐÀO TO
VIỆN HÀN LÂM KHOA HC
CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC CÔNG NGHỆ
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 HỘI
VỚI RÀNG BUỘC ƯU TIÊN CHI PHÍ
LUẬN ÁN TIẾN HỆ THỐNG THÔNG TIN
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 họ tên)
Người hướng dẫn 2
(Ký, ghi họ tên)
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 hội với ràng buộc ưu tiên chi phí 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 các
thông tin trích dẫn được ghi nguồn gố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 hoàn toàn trung thực 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 ng nghệ, Viện Hàn lâm Khoa học Công nghệ Việt Nam.
Ni, ngày 30 tháng 05 năm 2024
Tác giả luận án
Chí Quang
LỜI CẢM ƠN
Tôi xin bày tỏ lòng biết ơn chân thành sâu sắc tới tập thể thầy giáo hướng
dẫn, TS Nguyễn Như Sơn 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 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 c thầy Học viện Khoa học Công
nghệ, Viện Công nghệ thông tin, Viện Hàn lâm Khoa học Công nghệ Việt Nam đã
tạo điều kiện, giúp đỡ tôi trong quá trình học tập 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ự đã 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 các đồng nghiệp của Khoa An ninh
mạng 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ổ độ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 của
vợ, con tôi, những người luôn độ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!
Ni, ngày 30 tháng 05 năm 2024
Tác giả luận án
Chí Quang
1
MỤC LỤC
MỤC LỤC ...................................................................................................................1
DANH MỤC CÁC 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 SỞ THUYẾT CỦA LUẬN ÁN CÁC NGHIÊN CỨU
LIÊN QUAN ............................................................................................................. 17
1.1 Giới thiệu về mạng hội........................................................................... 17
1.1.1 Các thành phần bản của mạng hội.....................................18
1.1.2 Một số đặc trưng chung của mạng hội....................................19
1.1.3 Lợi ích của mạng hội................................................................20
1.1.4 Mặt trái của mạng hội.............................................................. 21
1.2 Các hình lan truyền thông tin trên mạng hội...........................23
1.2.1 hình lan truyền thông tin rời rạc............................................24
1.2.2 hình Ngưỡng tuyến tính (LT) .................................................25
1.2.3 hình Bậc độc lập (IC)..............................................................27
1.2.4 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 hội ......................32
1.3.1 Cực đại ảnh ở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 hội........................................ 37
1.4 Bài toán ti ưu t hp và mt s phương pháp giải các bài toán
tối ưu t hp...........................................................................................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