Xem mẫu
LỜI CAM ĐOAN
Tôi xin cam đoan, những kiến thức trình bày trong luận văn là do tôi tìm
hiểu, nghiên cứu và trình bày dưới sự hướng dẫn của PGS.TS Hoàng Xuân
Huấn. Trong quá trình làm luận văn, tôi đã tham khảo các tài liệu có liên quan
và đều trích dẫn nguồn đầy đủ, rõ ràng. Những kết quả mới trong luận văn là
của riêng tôi, không sao chép từ bất kỳ một công trình nào khác. Nếu có điều gì
không trung thực, tôi xin hoàn toàn chịu trách nhiệm.
Học viên
Vũ Minh Mạnh
LỜI CẢM ƠN
Trước hết, tôi xin gửi lời cảm ơn sâu sắc đến PGS.TS Hoàng Xuân Huấn,
người thầy đã giành nhiều thời gian để hướng dẫn, góp ý giúp tôi hoàn thành
luận văn này. Thầy luôn truyền cho tôi cảm hứng, nhiệt huyết nghiên cứu khoa
học, động viên và cho tôi nhiều lời khuyên quý báu.
Tôi cũng xin bày tỏ lòng biết ơn chân thành tới các thầy, cô giáo đã giảng dạy
tôi trong suốt 2 năm học tại Trường Đại học Công nghệ - Đại học Quốc gia Hà
Nội. Mỗi thầy cô đều cho tôi những bài giảng thật hay và bổ ích.
Tôi cũng xin gửi lời cảm ơn tới Ban giám đốc Học viện An ninh nhân dân,
Lãnh đạo Khoa Công nghệ và An ninh thông tin cùng các anh chị đồng nghiệp
đã tạo mọi điều kiện thuận lợi giúp tôi tham gia và hoàn thành khóa học.
Cuối cùng, tôi xin gửi lời biết ơn đến bố mẹ, anh chị trong gia đình, bạn bè,
người thân đã luôn ủng hộ, động viên tôi vượt qua những khó khăn trong cuộc
sống, để tôi có thể theo đuổi ước mơ và hoài bão của mình.
Học viên
Vũ Minh Mạnh
Mục lục
MỞ ĐẦU
1
1 GIỚI THIỆU VỀ MẠNG XÃ HỘI
5
1.1
1.2
1.3
Giới thiệu chung về mạng xã hội . . . . . . . . . . . . . . . . . . .
5
1.1.1
Lịch sử phát triển của mạng xã hội . . . . . . . . . . . . . .
7
1.1.2
Những tính năng của mạng xã hội . . . . . . . . . . . . . .
9
Các đặc trưng cơ bản của mạng xã hội . . . . . . . . . . . . . . . .
10
1.2.1
Đặc trưng thế giới nhỏ . . . . . . . . . . . . . . . . . . . . .
10
1.2.2
Đặc trưng tập nhân . . . . . . . . . . . . . . . . . . . . . . .
11
1.2.3
Phân bố luật lũy thừa . . . . . . . . . . . . . . . . . . . . .
11
1.2.4
Đặc trưng cấu trúc cộng đồng . . . . . . . . . . . . . . . . .
12
1.2.5
Các đặc trưng khác của mạng xã hội . . . . . . . . . . . . .
13
Một số chủ đề được nghiên cứu trên mạng xã hội . . . . . . . . . .
14
1.3.1
Phát hiện cấu trúc cộng đồng trên mạng xã hội . . . . . .
14
1.3.2
Dự đoán liên kết trên mạng xã hội . . . . . . . . . . . . . .
15
1.3.3
Tính riêng tư trên mạng xã hội . . . . . . . . . . . . . . . .
16
1.3.4
Tiến hóa động trên mạng xã hội . . . . . . . . . . . . . . .
16
1.3.5
Khai phá dữ liệu trên mạng xã hội . . . . . . . . . . . . . .
17
1.3.6
Tối đa hóa ảnh hưởng trên mạng xã hội . . . . . . . . . . .
18
1.3.7
Phát hiện, giám sát và ngăn ngừa thông tin sai lệch trên
mạng xã hội . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2 THÔNG TIN SAI LỆCH VÀ CÁC MÔ HÌNH LAN TRUYỀN
THÔNG TIN SAI LỆCH
20
2.1
Định nghĩa thông tin sai lệch . . . . . . . . . . . . . . . . . . . . .
20
2.2
Mô hình lan truyền thông tin sai lệch . . . . . . . . . . . . . . . .
24
2.2.1
Mô hình tầng độc lập . . . . . . . . . . . . . . . . . . . . .
25
2.2.2
Mô hình ngưỡng tuyến tính . . . . . . . . . . . . . . . . . .
26
2.3
Một số hướng nghiên cứu liên quan đến bài toán hạn chế lan
truyền thông tin sai lệch trên mạng xã hội trực tuyến . . . . . . .
29
3 GIẢI PHÁP GIẢM THIỂU TỐI ĐA THIỆT HẠI DO THÔNG
TIN SAI LỆCH GÂY RA TRÊN MẠNG XÃ HỘI TRỰC TUYẾN 34
3.1
Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
3.2
Độ khó của bài toán . . . . . . . . . . . . . . . . . . . . . . . . . .
39
3.3
Các thuật toán đề xuất giải quyết bài toán MDM . . . . . . . . .
41
3.3.1
Thuật toán tham lam dựa trên hàm f (I) . . . . . . . . . .
41
3.3.2
Thuật toán tham lam dựa trên hàm α(v) . . . . . . . . . .
43
4 THỰC NGHIỆM
45
4.1
Mục đích thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . .
45
4.2
Dữ liệu tiến hành thực nghiệm . . . . . . . . . . . . . . . . . . . .
45
4.3
Cài đặt thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . .
46
4.4
Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . .
47
4.5
Kết luận và nhận xét . . . . . . . . . . . . . . . . . . . . . . . . . .
51
KẾT LUẬN
52
DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ
54
PHỤ LỤC
62
Danh mục các từ viết tắt
Từ viết tắt Thuật ngữ tiếng Anh
IC
Independent Cascade
LT
Linear Threshold
MDM
Minimize Damage of Misinformation
MXH
Social Network
Thuật ngữ tiếng Việt
Mô hình tầng độc lập
Mô hình ngưỡng tuyến tính
Bài toán cực tiểu hóa thiệt hại do
thông tin sai lệch gây ra
Mạng xã hội
nguon tai.lieu . vn
Tôi xin cam đoan, những kiến thức trình bày trong luận văn là do tôi tìm
hiểu, nghiên cứu và trình bày dưới sự hướng dẫn của PGS.TS Hoàng Xuân
Huấn. Trong quá trình làm luận văn, tôi đã tham khảo các tài liệu có liên quan
và đều trích dẫn nguồn đầy đủ, rõ ràng. Những kết quả mới trong luận văn là
của riêng tôi, không sao chép từ bất kỳ một công trình nào khác. Nếu có điều gì
không trung thực, tôi xin hoàn toàn chịu trách nhiệm.
Học viên
Vũ Minh Mạnh
LỜI CẢM ƠN
Trước hết, tôi xin gửi lời cảm ơn sâu sắc đến PGS.TS Hoàng Xuân Huấn,
người thầy đã giành nhiều thời gian để hướng dẫn, góp ý giúp tôi hoàn thành
luận văn này. Thầy luôn truyền cho tôi cảm hứng, nhiệt huyết nghiên cứu khoa
học, động viên và cho tôi nhiều lời khuyên quý báu.
Tôi cũng xin bày tỏ lòng biết ơn chân thành tới các thầy, cô giáo đã giảng dạy
tôi trong suốt 2 năm học tại Trường Đại học Công nghệ - Đại học Quốc gia Hà
Nội. Mỗi thầy cô đều cho tôi những bài giảng thật hay và bổ ích.
Tôi cũng xin gửi lời cảm ơn tới Ban giám đốc Học viện An ninh nhân dân,
Lãnh đạo Khoa Công nghệ và An ninh thông tin cùng các anh chị đồng nghiệp
đã tạo mọi điều kiện thuận lợi giúp tôi tham gia và hoàn thành khóa học.
Cuối cùng, tôi xin gửi lời biết ơn đến bố mẹ, anh chị trong gia đình, bạn bè,
người thân đã luôn ủng hộ, động viên tôi vượt qua những khó khăn trong cuộc
sống, để tôi có thể theo đuổi ước mơ và hoài bão của mình.
Học viên
Vũ Minh Mạnh
Mục lục
MỞ ĐẦU
1
1 GIỚI THIỆU VỀ MẠNG XÃ HỘI
5
1.1
1.2
1.3
Giới thiệu chung về mạng xã hội . . . . . . . . . . . . . . . . . . .
5
1.1.1
Lịch sử phát triển của mạng xã hội . . . . . . . . . . . . . .
7
1.1.2
Những tính năng của mạng xã hội . . . . . . . . . . . . . .
9
Các đặc trưng cơ bản của mạng xã hội . . . . . . . . . . . . . . . .
10
1.2.1
Đặc trưng thế giới nhỏ . . . . . . . . . . . . . . . . . . . . .
10
1.2.2
Đặc trưng tập nhân . . . . . . . . . . . . . . . . . . . . . . .
11
1.2.3
Phân bố luật lũy thừa . . . . . . . . . . . . . . . . . . . . .
11
1.2.4
Đặc trưng cấu trúc cộng đồng . . . . . . . . . . . . . . . . .
12
1.2.5
Các đặc trưng khác của mạng xã hội . . . . . . . . . . . . .
13
Một số chủ đề được nghiên cứu trên mạng xã hội . . . . . . . . . .
14
1.3.1
Phát hiện cấu trúc cộng đồng trên mạng xã hội . . . . . .
14
1.3.2
Dự đoán liên kết trên mạng xã hội . . . . . . . . . . . . . .
15
1.3.3
Tính riêng tư trên mạng xã hội . . . . . . . . . . . . . . . .
16
1.3.4
Tiến hóa động trên mạng xã hội . . . . . . . . . . . . . . .
16
1.3.5
Khai phá dữ liệu trên mạng xã hội . . . . . . . . . . . . . .
17
1.3.6
Tối đa hóa ảnh hưởng trên mạng xã hội . . . . . . . . . . .
18
1.3.7
Phát hiện, giám sát và ngăn ngừa thông tin sai lệch trên
mạng xã hội . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2 THÔNG TIN SAI LỆCH VÀ CÁC MÔ HÌNH LAN TRUYỀN
THÔNG TIN SAI LỆCH
20
2.1
Định nghĩa thông tin sai lệch . . . . . . . . . . . . . . . . . . . . .
20
2.2
Mô hình lan truyền thông tin sai lệch . . . . . . . . . . . . . . . .
24
2.2.1
Mô hình tầng độc lập . . . . . . . . . . . . . . . . . . . . .
25
2.2.2
Mô hình ngưỡng tuyến tính . . . . . . . . . . . . . . . . . .
26
2.3
Một số hướng nghiên cứu liên quan đến bài toán hạn chế lan
truyền thông tin sai lệch trên mạng xã hội trực tuyến . . . . . . .
29
3 GIẢI PHÁP GIẢM THIỂU TỐI ĐA THIỆT HẠI DO THÔNG
TIN SAI LỆCH GÂY RA TRÊN MẠNG XÃ HỘI TRỰC TUYẾN 34
3.1
Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
3.2
Độ khó của bài toán . . . . . . . . . . . . . . . . . . . . . . . . . .
39
3.3
Các thuật toán đề xuất giải quyết bài toán MDM . . . . . . . . .
41
3.3.1
Thuật toán tham lam dựa trên hàm f (I) . . . . . . . . . .
41
3.3.2
Thuật toán tham lam dựa trên hàm α(v) . . . . . . . . . .
43
4 THỰC NGHIỆM
45
4.1
Mục đích thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . .
45
4.2
Dữ liệu tiến hành thực nghiệm . . . . . . . . . . . . . . . . . . . .
45
4.3
Cài đặt thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . .
46
4.4
Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . .
47
4.5
Kết luận và nhận xét . . . . . . . . . . . . . . . . . . . . . . . . . .
51
KẾT LUẬN
52
DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ
54
PHỤ LỤC
62
Danh mục các từ viết tắt
Từ viết tắt Thuật ngữ tiếng Anh
IC
Independent Cascade
LT
Linear Threshold
MDM
Minimize Damage of Misinformation
MXH
Social Network
Thuật ngữ tiếng Việt
Mô hình tầng độc lập
Mô hình ngưỡng tuyến tính
Bài toán cực tiểu hóa thiệt hại do
thông tin sai lệch gây ra
Mạng xã hội