ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ——————–o0o——————– NGUYỄN ĐÌNH HỊA NGĂN CHẶN THƠNG TIN SAI LỆCH TRÊN MẠNG XÃ HỘI Ở DIỆN RỘNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Hà Nội – 2019 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ——————–o0o——————– NGUYỄN ĐÌNH HỊA NGĂN CHẶN THƠNG TIN SAI LỆCH TRÊN MẠNG XÃ HỘI Ở DIỆN RỘNG Ngành: Khoa học máy tính Chuyên ngành: Khoa học máy tính Mã số: 8480101.01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS TS Hoàng Xuân Huấn Hà Nội – 2019 i LỜI CAM ĐOAN Tôi xin cam đoan, kiến thức trình bày luận văn tơi tìm hiểu, nghiên cứu trình bày lại Trong q trình làm luận văn tơi có tham khảo tài liệu có liên quan ghi rõ nguồn tài liệu tham khảo Những kết luận văn riêng nhóm tác giả khơng chép từ cơng trình khác Nếu có điều khơng trung thực, tơi xin hồn tồn chịu trách nhiệm Hà Nội, ngày tháng 11 năm 2019 Học viên Nguyễn Đình Hịa ii LỜI CẢM ƠN Trước hết, xin gửi lời cảm ơn sâu sắc tới PGS TS Hoàng Xuân Huấn giành nhiều thời gian để hướng dẫn, góp ý, động viên học tập nghiên cứu khoa học để tơi hồn thành luận văn Tơi xin bày tỏ lòng biết ơn tới thầy, cô Khoa Công nghệ thông tin, đặc biệt thầy, cô Bộ môn Khoa học máy tính, trường Đại học Cơng nghệ giảng dạy, tạo môi trường học tập, làm việc khoa học nghiêm túc, hiệu giúp tơi học hỏi, trau dồi kiến thức Tôi 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ệ An ninh thông tin đồng nghiệp tạo điều kiện thuận lợi cho tơi tham gia hồn thành khóa học Tơi xin cảm ơn tất người thân gia đình ln động viên, ủng hộ, khích lệ tơi vượt qua khó khăn nghiên cứu sống Hà Nội, ngày tháng 11 năm 2019 Học viên Nguyễn Đình Hịa iii MỤC LỤC LỜI CAM ĐOAN i LỜI CẢM ƠN ii DANH SÁCH HÌNH VẼ v DANH MỤC CÁC TỪ VIẾT TẮT vi MỞ ĐẦU CHƯƠNG GIỚI THIỆU VỀ MẠNG XÃ HỘI VÀ TÁC HẠI CỦA THÔNG TIN SAI LỆCH 1.1 Giới thiệu chung mạng xã hội 1.1.1 Đặc điểm MXH 1.1.2 Lợi ích tác động MXH 1.2 Tác hại thông tin sai lệch MXH 1.2.1 Định nghĩa thơng tin sai lệch tính chất thơng tin sai lệch 1.2.2 Tác hại thực trạng phát tán thông tin sai lệch MXH 11 CHƯƠNG MƠ HÌNH LAN TRUYỀN THƠNG TIN SAI LỆCH 16 2.1 Biểu diễn mạng xã hội 16 2.2 Mơ hình bậc độc lập - IC 17 2.3 Mơ hình ngưỡng tuyến tính - LT 20 iv CHƯƠNG NGĂN CHẶN THÔNG TIN SAI LỆCH TRÊN MẠNG XÃ HỘI Ở DIỆN RỘNG 22 3.1 Đặt vấn đề 22 3.2 Bài toán Ngăn chặn thông tin sai lệch với ngân sách giới hạn 24 3.3 Mơ hình định nghĩa tốn 25 3.3.1 Mơ hình đề xuất 25 3.3.2 Định nghĩa toán 28 3.4 Các thuật toán cho toán LSE 31 3.4.1 Thuật toán tham lam 31 3.4.2 Thuật toán FLE 32 3.5 Thực nghiệm 35 3.5.1 Mục đích thực nghiệm 35 3.5.2 Dữ liệu thiết lập tham số thực nghiệm 36 3.5.3 Kết thực nghiệm 36 KẾT LUẬN 41 DANH MỤC CƠNG TRÌNH ĐÃ CÔNG BỐ 42 TÀI LIỆU THAM KHẢO 43 v DANH SÁCH HÌNH VẼ 2.1 Ví dụ q trình lan truyền thơng tin mơ hình IC 19 2.2 Ví dụ q trình lan truyền thơng tin mơ hình LT 21 3.1 Phép dẫn đa thức từ toán SC toán LSE 30 3.2 So sánh chất lượng lời giải thời gian chạy thuật toán θ thay đổi k = 50, d = 37 3.3 So sánh chất lượng lời giải thời gian chạy thuật toán k thay đổi, d = 5, θ = 0.5 3.4 38 So sánh chất lượng lời giải thời gian chạy thuật toán d thay đổi, k = 50, θ = 0.5 với liệu Gnutella 39 vi DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Tiếng Anh FLE IC LSE LT MXH T-DLT Tiếng Việt Fast And Effective Limiting Epidemics Thuật toán nhanh hiệu để giới hạn lây nhiễm thông tin Independent Cascade Bậc độc lập Limiting the Spread of Epi- Hạn chế lây lan thông demics tin sai lệch Linear Threshold Ngưỡng tuyến tính Social Network Mạng xã hội Time Constraint Deterministic Mơ hình lan truyền thơng tin Linear Threshold Ngưỡng tuyến tính xác định với ràng buộc thời gian MỞ ĐẦU Sự phát triển mạng xã hội (MXH) hai thập niên trở lại mang lại cho người nhiều lợi ích kèm với nhiều nguy hiểm họa tới người dùng Một yếu tố mang lại nhiều tác hại cho cộng đồng người dùng phát tán thông tin sai lệch Các yếu tố gây tác hại lớn cộng đồng người sử dụng mạng xã hội Không Việt Nam, tác hại diễn phạm vi toàn giới Việc lan truyền thơng tin sai lệch gây tác động xã hội tiêu cực, chí tổn thất lớn kinh tế Chẳng hạn, tin đồn không hay sức khỏe tổng thống Mỹ ông Obama vào tháng năm 2013 dẫn đến bất ổn thị trường tài phố Wall Trước thềm Đại hội đại biểu toàn quốc lần thứ XII Đảng Cộng sản Việt Nam, có thơng tin gia đình tài sản Thủ tướng Nguyễn Xn Phúc lúc cịn Phó Thủ tướng Chính phủ, nhằm hạ uy tín gây lòng tin nhân dân Thủ tướng Trước thực trạng đó, ngăn chặn, phịng chống lây lan thông tin sai lệch trở thành mục tiêu hàng đầu quốc gia Với thực trạng đó, nhà khoa học nghiên cứu giải pháp hiệu để ngăn chặn thơng tin sai lệch Trong đó, việc mơ hình hóa q trình lan truyền thơng tin mạng tảng tiếp cận họ Các mơ hình lan truyền thơng tin, hay cịn gọi mơ hình khuếch tán thơng tin nhà khoa học đưa mơ hình hóa tốn học mơ tả cách tương đối xác mạng lưới q trình lan truyền thơng tin, lan truyền dịch bệnh mạng lưới Kempe cộng [11] lần đề xuất hai mô hình lan truyền thơng tin Ngưỡng tuyến tính (LT) Bậc độc lập (IC) Hai mơ hình sau sử dụng rộng rãi tốn lan truyền thơng tin nói chung [2, 4, 6, 7, 10, 18, 19] toán ngăn chặn thơng tin sai lệch nói riêng [20, 21, 22, 24, 25, 26] Các tốn ngăn chặn thơng tin sai lệch xây dựng mơ hình dạng toán tối ưu tổ hợp Tuy việc nghiên cứu vấn đề gặp phải thách thức tốn thường NP-Khó, NP-đầy đủ việc tính tốn hàm mục tiêu #P-Khó Do việc tìm giải pháp ngăn chặn thơng tin sai lệch diện rộng hạn chế Thúc đẩy tượng yêu cầu thiết việc giải ngăn chặn tác hại tin đồn mạng xã hội mang lại Tác giả luận văn mạnh dạn nghiên cứu đề tài “Ngăn chặn thông tin sai lệch mạng xã hội diện rộng ” với mục tiêu đưa giải pháp ngăn chặn thơng tin sai lệch mở rộng mạng diện rộng thông qua việc mơ hình hóa tốn dạng tối ưu tổ hợp khắc phục nhược điểm mơ hình trước Đồng thời đề xuất thuật toán nhanh hiệu để giải Các kết luận văn đạt sau: Luận văn đưa mơ hình lan truyền thơng tin với giới hạn thời gian lan truyền thông tin gọi mơ hình Ngưỡng tuyến tính với bước thời gian rời rạc (Time Constraint Deterministic Linear - Threshold) mở rộng từ mơ hình Ngưỡng tuyến tính (LT) [11] Trên mơ hình này, hàm mục tiêu tính tốn thời gian đa thức Sau đó, nhóm tác giả định nghĩa toán Hạn chế lây lan thông tin sai lệch (Limiting the Spread of Epidemics - LSE) với mục tiêu tìm kiếm tập đỉnh A có kích thước tối đa k để loại khỏi mạng xã hội cho trước cho số đỉnh cứu lớn Nhóm tác giả tốn tốn NP-Khó Với lời giải, nhóm tác giả đưa hai thuật tốn, bao gồm: Thuật toán tham lam (Greedy) thuật toán nhanh hiệu để giới hạn lây nhiễm thông tin (Fast And Effective Limiting Epidemics – FLE) Các thực nghiệm thực liệu thực tế lấy từ nguồn đáng tin cậy Gnutella, Wikipedia Vote, Amazon Google Web Thuật toán kiểm nghiệm cho thấy khả 33 sử dụng q trình đề xuất thuật tốn: • t(u): thời gian u chuyển từ đỉnh trạng thái kích hoạt sang khơng bị kích hoạt • At (I): tập đỉnh bị ảnh hưởng I bước t • a+ (v) = đỉnh v u∈At(u−1) ∩Nin (v) w(u, v): tổng trọng số ảnh hưởng đến • α(u): đánh giá ảnh hưởng từ u đến đỉnh khác • β(u): số lượng đỉnh cứu tức cho chúng chuyển từ bị kích hoạt thành khơng bị kích hoạt sau loại bỏ đỉnh u khỏi đồ thị Tham số β(u) ước lượng thay cho δ(A, u) Thuật toán FLE hoạt động sau: Ban đầu, tập khởi tạo A = ∅ U = Vd Điều làm giảm thời gian tính tốn khơng xét đỉnh khơng tính tốn đến Thuật tốn chọn đỉnh có hàm β() lớn vịng lặp Algorithm 3: Thuật tốn FLE Input: Graph G = (V, E, ∅), I , d, k , θ Output: Solution A S ← ∅; Calculate G ← Gd (I); U ← Vd for i = to k Calculate α(u), β(u) on G (Algorithm 5) umax ← ∅ if β(v) = 0, ∀v ∈ U then umax ← arg maxv∈U α(v) else umax ← arg maxv∈U β(v) 10 end 11 S ← S ∪ {umax }, U ← U \ {umax } 12 Remove umax and all edges that adjacent with umax from G 13 end 14 return S Chi tiết thuật tốn mơ tả Thuật tốn 3, thuật 34 tốn tính gần α() β() mô tả Thuật toán Thuật toán Algorithm 4: Thuật toán tính fd (I), a+ (), t() Input: Graph G = (V, E), I , d Output: Ad (I), a+ (u), t(u), ∀u ∈ G foreach u in G a+ (u) ← 0, t(u) ← 0, Ad (I) ← ∅ end For each s in I : t(s) ← Queue Q ← I while Q = ∅ u ← Q.pop(); Ad (I) ← u if t(u) < d then foreach v ∈ Nout (u) 10 if t(u) < t(v) then 11 a+ (v) = a+ (v) + w(u, v) 12 if a+ (v) ≥ θv and t(u) + < t(v) then 13 t(v) ← t(u) + 14 Q.push(v) 15 end 16 end 17 end 18 end 19 end Trong Thuật toán Thuật toán sử dụng hàng đợi Q để lưu trữ đỉnh xét, tư tưởng thuật toán giống với thuật toán DFS Q khởi tạo danh sách đỉnh I Với đỉnh u ∈ Q, ta xét đỉnh kề v với u cập nhật trọng số ảnh hưởng v (dòng 11) thời gian mà v kích hoạt (dịng 12, 13) Nếu v bị ảnh hưởng ta thêm v vào Q (dòng 14) Ad (I) (dòng 7) Trong Thuật tốn 5: thuật tốn tính hai giá trị α, β đỉnh dựa giá trị Ad (I), at (), t() thuật toán trước Với đỉnh i thuộc Ad (I), thuật toán xét đỉnh v hàng xóm kích hoạt sau đỉnh u (tức có thời gian kích hoạt lơn hơn), giá trị α(u) cập nhật cách cộng thêm trọng số ảnh hưởng đến đỉnh v (dòng 5) Nếu việc loại bỏ đỉnh u mà v chuyển từ trạng thái bị ảnh hưởng sang không bị ảnh hưởng 35 (điều kiện dịng 6) β(u) tăng lên Để đánh giá độ phức tạp thuật toán này, cần đánh giá trước độ phức tạp thuật toán 3, 4, Độ phức tạp Thuật tốn 4, dịng - 19) O(md +nd ) (Áp dụng BFS) Với bước tính tốn α(u) β(u) (Thuật tốn 5, dịng - 11), có độ phức tạp tương tự O(md + nd ) Do đó, độ phức tạp chung Thuật tốn FLE O(k(md + nd ) Tuy có độ phức tạp theo lý thuyết với Thuật toán tham lam, việc cập nhật nhanh tham số nên thực nghiệm, thuật tốn FLE có thời gian chạy nhanh Algorithm 5: Thuật tốn tính α(), β() Input: Graph G = (V, E, ∅), I , d, Ad (I), at (), t() Output: α(u), β(u), ∀u ∈ G foreach u in Ad (I) α(u) ← 0; β(u) ← foreach v in Nout (u) ∩ Ad (I) if t(u) < t(v) then α(u) ← α(u) + w(u, v) if a+ (v) − w(u, v) < θv then β(u) ← β(u) + end end 10 end 11 end 3.5 Thực nghiệm 3.5.1 Mục đích thực nghiệm So sánh hiệu quả, thời gian chạy thuật toán đề xuất bao gồm: thuật toán tham lam, thuật toán FLE với thuật toán phổ biến tốn lan truyền thơng tin (các thuật tốn sở) bao gồm: • Random: Thuật tốn chọn ngẫu nhiên k đỉnh Nd (I) • Degree : Thuật tốn heuristic chọn đỉnh có bậc cao tập Vd đủ k đỉnh Hai thuật toán dùng phổ biến nghiên cứu toán 36 tối đa ảnh hưởng [6, 11, 14] tốn ngăn chặn thơng tin sai lệch [22, 24, 29] 3.5.2 Dữ liệu thiết lập tham số thực nghiệm Nhóm tác giả tiến hành thực nghiệm thuật toán nhiều liệu chuẩn thường sử dụng toán lan truyền thông tin (Bảng 3.1) Bốn liệu chọn đại diện cho mạng với quy mô khác nhau, từ vài nghìn đến vài trăm nghìn đỉnh Việc lựa chọn liệu đảm bảo đa dạng kích thước miền liệu Bảng 3.1: Các liệu dùng thực nghiệm với toán LSE Mạng Số đỉnh Gnutella [13] 6,301 Wikipedia vote [13] 7,115 Amazon [19] 262,111 Google web [31] 875,713 Số cạnh Loại Bậc trung bình 20,777 Có hướng 3.29 103,689 Có hướng 14.57 1,234,877 Có hướng 4.71 5,105,039 Có hướng 5.83 Các tham số thiết lập sau • Trọng số cạnh: w(u, v) = [11, 7, 12] din (v) , với din (v) bậc vào đỉnh v • Ngưỡng lây nhiễm: {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9} • Thời gian giới hạn d = 2, 3, 4, • Tập nguồn S : liệu, nhóm tác giả lấy 1% số đỉnh làm tập đỉnh bị lây nhiễm ban đầu Môi trường thực nghiệm: Các thực nghiệm thực máy tính có cấu hình sau: Intel(R) Core(TM) i5-6200U CPU @ 2.30 GHz (up to 2.40 GHz), nhớ RAM 4GB, ngơn ngữ lập trình Python 2.7 Thời gian chạy giới hạn 12h 3.5.3 Kết thực nghiệm Thực nghiệm chia làm kịch bản, tương ứng với việc kiểm tra ảnh hưởng tham số k, θ, d, sau: 37 ngưỡng θ thay đổi, k = 50, d = (Hình 3.2) k thay đổi từ 10 đến 100, d = 5, θ = 0.5 (Hình 3.3) d thay đổi, k = 50, θ = 0.5 (Hình 3.4) FLE Greedy Random Maxdeg 5000 4000 3000 2000 1000 0 WIKI VOTE, k = 50, d = number of saved nodes h d (A) number of saved nodes h d (A) GNUTELLA, k = 50, d = 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 2000 FLE Greedy Random Maxdeg 1500 1000 500 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 theta theta GNUTELLA, k = 50, d = FLE Greedy Random Maxdeg 400000 300000 200000 100000 0 WIKI VOTE, k = 50, d = 1.6x10 RUNNING TIME (m.s) RUNNING TME (m.s) 500000 FLE Greedy Random Maxdeg 1.4x10 1.2x10 1x10 800000 600000 400000 200000 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 theta theta FLE Random Maxdeg 800 600 400 200 0 GOOGLE WEB, k = 50, d = number of saved nodes h d (A) number of saved nodes h d (A) AMAZON, k = 50, d = 1000 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 FLE Random Maxdeg 5000 4000 3000 2000 1000 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 theta theta AMAZON, k = 50, d = RUNNING TIME (m.s) 1500 RUNNING TIME (m.s) FLE Random Maxdeg 2000 1000 500 0 GOOGLE WEB, k = 50, d = 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 theta 18000 16000 14000 12000 10000 8000 6000 4000 2000 FLE Random Maxdeg 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 theta Hình 3.2: So sánh chất lượng lời giải thời gian chạy thuật toán θ thay đổi k = 50, d = 38 WIKI VOTE, d = 5, theta = 0.5 number of saved nodes h d (A) number of saved nodes h d (A) GNUTELLA, d = 5, theta = 0.5 500 FLE Greedy Random Maxdeg 400 300 200 100 0 20 40 60 80 100 100 FLE Greedy Random Maxdeg 80 60 40 20 0 20 40 k GNUTELLA, d = 5, theta = 0.5 FLE Greedy Random Maxdeg 70000 60000 50000 40000 30000 20000 10000 0 20 40 60 80 800000 600000 400000 200000 100 20 40 60 number of saved nodes h d (A) number of saved nodes h d (A) 200 150 100 50 0 20 40 60 80 100 4000 FLE Random Maxdeg 3500 3000 2500 2000 1500 1000 500 0 20 40 k RUNNING TIME (m.s) RUNNING TIME (m.s) 300 200 100 0 20 40 60 k 80 100 GOOGLE WEB, d = 5, theta = 0.5 8000 FLE Random Maxdeg 400 60 k AMAZON, d = 5, theta = 0.5 500 100 GOOGLE WEB, d = 5, theta = 0.5 FLE Random Maxdeg 250 80 k AMAZON, d = 5, theta = 0.5 300 100 FLE Greedy Random Maxdeg 1x10 k 350 80 WIKI VOTE, d = 5, theta = 0.5 1.2x10 RUNNING TIME (m.s) RUNNING TIME (m.s) 80000 60 k 80 100 FLE Random Maxdeg 7000 6000 5000 4000 3000 2000 1000 0 20 40 60 80 100 k Hình 3.3: So sánh chất lượng lời giải thời gian chạy thuật toán k thay đổi, d = 5, θ = 0.5 39 GNUTELLA, k = 50, theta = 0.5 FLE Greedy Random Maxdeg 250 200 150 100 50 0 FLE Greedy Random Maxdeg 60000 RUNNING TME (m.s) number of saved nodes h d (A) GNUTELLA, k = 50, theta = 0.5 300 d 50000 40000 30000 20000 10000 0 d Hình 3.4: So sánh chất lượng lời giải thời gian chạy thuật toán d thay đổi, k = 50, θ = 0.5 với liệu Gnutella - Kết lời giải: Trong trường hợp, FLE Greedy cho kết tốt so với thuật tốn cịn lại, cụ thể số lượng đỉnh cứu nhiều 48.5 lần so với thuật toán MaxDegree Random hai liệu Gnutella Wiki Vote Khi so sánh Greedy FLE, nhóm tác giả thấy Greedy có hiệu suất tốt từ 1.02 đến 1.05 lần so với FLE liệu mạng Gnutella Tuy nhiên, khoảng cách bị thu hẹp lại θ k tăng Đặc biệt k ≥ 50 θ ≥ 0.4, hiệu suất hai thuật toán tương đương Hình 3.2, 3.3, 3.4 cho thấy Greedy FLE có hiệu suất tương đương liệu mạng Wiki Vote Trong Greedy chạy thời gian cho phép Amazon Google Web, FLE đưa kết tốt nhiều so với hai thuật tốn cịn lại - Kết thời gian: Thời gian chạy thuật toán mơ tả Hình 3.2, 3.3, 3.4 Đúng dự đoán, thời gian chạy Greedy cao so với thuật tốn cịn lại, chiếm 4.5 phút cho liệu Gnutella 20.2 phút cho mạng Wiki Vote Thuật toán FLE nhanh từ 4820 đến 6789 lần so với Greedy mạng Gnutella nhanh từ 5839 đến 14490 lần so với Greedy mạng Wiki Vote Điều xảy Greedy có độ phức tạp thuật tốn lớn O(nd k(md + nd )), FLE có độ phức tạp nhỏ nhiều O(k(md + nd )) Trong liệu Amazon Google Web, 40 Greedy tìm thấy lời giải vịng 12 tiếng bị buộc dừng chạy, FLE 0.45 giây 7.8 giây tương ứng với liệu Điều cho thấy FLE chạy tốt với liệu lớn - Ảnh hưởng tham số d: Nhóm tác giả khám phá ảnh hưởng tham số d thuật toán khác Cho d thay đổi từ đến mạng Gnutella, kết thể Hình 3.4 Với Greedy FLE, số đỉnh cứu tăng giá trị d tăng Đăc biệt, số đỉnh cứu tăng mạnh với d = 2, tăng với d = 4, Điều chứng tỏ để ngăn chặn lây lan, ta phải loại bỏ đỉnh sớm tốt - Ảnh hưởng tham số θ: Nhóm tác giả xem xét ảnh hưởng tham số θ thuật toán cách cho θ thay đổi giữ nguyên d k Nhóm tác giả lựa chọn giá trị d = 5, k = 50 Đối với mạng Amazon Google Web, số đỉnh cứu giảm giá trị θ giảm Đối với mạng Gnutella Wiki Vote, số đỉnh cứu tăng θ tăng từ 0.1 đến 0.3 giảm θ tăng từ 0.3 đến 0.9 Tổng quát lại, ta thấy thự tế việc giá trị θ cao làm q trình lây gặp khó khăn Từ Hình 3.3, ta thấy Greedy FLE cho kết tốt nhiều so với hai thuật tốn cịn lại Điều lần cho thấy tính ưu việt thuật toán FLE 41 KẾT LUẬN Trong luận văn này, tác giả cộng đạt số kết sau: • Tìm hiểu tổng quan mạng xã hội, lây lan tác hại thông tin sai lệch mạng xã hội • Tìm hiểu chế lan truyền thơng tin đặc tính hai mơ hình lan truyền thơng tin: Mơ hình tầng độc lập (IC) mơ hình ngưỡng tuyến tính (LT) Tác giả tìm hiểu hướng nghiên cứu liên quan đến tốn ngăn chặn thơng tin sai lệch lan truyền mạng xã hội công bố • Đề xuất mơ hình lan truyền thơng tin ngưỡng tuyến tính với bước thời gian rời rạc xác định T-DLT; định nghĩa toán Hạn chế lây lan thông tin sai lệch LSE chứng minh tốn thuộc lớp NP-Khó; đồng thời đề xuất thuật toán tham lam thuật toán nhanh hiệu FLE cho toán LSE Kết thực nghiệm cho thấy ưu điểm trội hai thuật toán đề xuất so với thuật tốn thơng dụng khác thuật toán Max Degree thuật toán Random việc hạn chế thông tin sai lệch lan truyền MXH Mặc dù cố gắng nỗ lực hết mình, thời gian nghiên cứu trình độ thân có hạn nên luận văn khơng thể tránh khỏi thiếu sót hạn chế, tác giả mong nhận ý kiến đóng góp để luận văn đạt kết tốt Hướng phát triển: Trong thời gian tới, áp dụng kỹ thuật heuristic thuật toán tối ưu đàn kiến, di truyền để nâng cao chất lượng lời giải thuật toán dựa nguyên lý tham lam nên chất lượng lời giải hạn chế 42 DANH MỤC CƠNG TRÌNH ĐÃ CƠNG BỐ [1] Canh V Pham, Hoang M Dinh, Hoa D Nguyen, Huyen T Dang, Huan X Hoang Limiting the Spread of Epidemics within Time Constraint on Online Social Networks In: proceeding of the Eighth International Symposium on Information and Communication Technology (SoICT 2017), pp 262-269, Nha Trang, Vietnam, December 2017 (SCOPUS) 43 TÀI LIỆU THAM KHẢO [1] Twitter deletes 125,000 isis accounts and expands anti-terror teams [2] N Barbieri, F Bonchi, and G Manco Topic-aware social influence propagation models Knowledge and Information Systems, 37(3):555– 584, 2013 [3] W Chen, A Collins, R Cummings, T Ke, Z Liu, D Rincón, X Sun, Y Wang, W Wei, and Y Yuan Influence maximization in social networks when negative opinions may emerge and propagate In Proc SDM, pages 379–390, 2011 [4] W Chen, L V S Lakshmanan, and C Castillo Information and Influence Propagation in Social Networks Synthesis Lectures on Data Management Morgan & Claypool Publishers, 2013 [5] W Chen, W Lu, and N Zhang Time-critical influence maximization in social networks with time-delayed diffusion process In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada., 2012 [6] W Chen, C Wang, and Y Wang Scalable influence maximization for prevalent viral marketing in large-scale social networks In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, July 25-28, 2010, pages 1029–1038, 2010 [7] W Chen, Y Yuan, and L Zhang Scalable influence maximization in social networks under the linear threshold model In ICDM 2010, The 10th IEEE International Conference on Data Mining, Sydney, Australia, 14-17 December 2010, pages 88–97, 2010 44 [8] T N Dinh, H Zhang, D T Nguyen, and M T Thai Cost-effective viral marketing for time-critical campaigns in large-scale social networks IEEE/ACM Trans Netw., 22(6):2001–2011, 2014 [9] P Domm False rumor of explosion at white house causes stocks to briefly plunge; ap confirms its twitter feed was hacked In Available: https://www.cnbc.com/id/100646197, 2013 [10] A Goyal, W Lu, and L V S Lakshmanan SIMPATH: an efficient algorithm for influence maximization under the linear threshold model In 11th IEEE International Conference on Data Mining, ICDM 2011, Vancouver, BC, Canada, December 11-14, 2011, pages 211–220, 2011 [11] D Kempe, J M Kleinberg, and É Tardos Maximizing the spread of influence through a social network In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 24 - 27, 2003, pages 137–146, 2003 [12] E B Khalil, B N Dilkina, and L Song Scalable diffusion-aware optimization of network topology In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’14, New York, NY, USA - August 24 - 27, 2014, pages 1226–1235, 2014 [13] J Leskovec, L A Adamic, and B A Huberman The dynamics of viral marketing ACM Transactions on the Web (TWEB), 1(1):5, 2007 [14] J Leskovec, A Krause, C Guestrin, C Faloutsos, J M VanBriesen, and N S Glance Cost-effective outbreak detection in networks In Proc KDD, pages 420–429, 2007 [15] Z Lu, W Zhang, W Wu, J Kim, and B Fu The complexity of influence maximization problem in the deterministic linear threshold model J Comb Optim., 24(3):374–378, 2012 45 [16] V Luckerson Fear, misinformation, and social media complicate ebola fight In http://time.com/3479254/ebola-social-media/, 2014 [17] H T Nguyen, A Cano, T N Vu, and T N Dinh Blocking selfavoiding walks stops cyber-epidemics: A scalable gpu-based approach IEEE Transactions on Knowledge and Data Engineering, 2019 [18] H T Nguyen, M T Thai, and T N Dinh Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks In Proc SIGMOD, pages 695–710, 2016 [19] H T Nguyen, M T Thai, and T N Dinh A billion-scale approximation algorithm for maximizing benefit in viral marketing IEEE/ACM Transactions on Networking, 25(4):2419–2429, 2017 [20] N P Nguyen, G Yan, and M T Thai Analysis of misinformation containment in online social networks 57(10):2133–2146, 2013 Computer Networks, [21] C V Pham, H M Dinh, H D Nguyen, H T Dang, and H X Hoang Limiting the spread of epidemics within time constraint on online social networks In Proceedings of the Eighth International Symposium on Information and Communication Technology, Nha Trang City, Viet Nam, December 7-8, 2017, pages 262–269, 2017 [22] C V Pham, Q V Phu, and H X Hoang Targeted misinformation blocking on online social networks In Intelligent Information and Database Systems - 10th Asian Conference, ACIIDS 2018, Dong Hoi City, Vietnam, March 19-21, 2018, Proceedings, Part I, pages 107– 116, 2018 [23] C V Pham, Q V Phu, H X Hoang, J Pei, and M T Thai Minimum budget for misinformation blocking in online social networks J Comb Optim., 38(4):1101–1127, 2019 46 [24] C V Pham, M T Thai, H V Duong, B Q Bui, and H X Hoang Maximizing misinformation restriction within time and budget constraints J Comb Optim., 35(4):1202–1240, 2018 [25] C Song, W Hsu, and M Lee Node immunization over infectious period In Proceedings of the 24th ACM International Conference on Information and Knowledge Management, CIKM 2015, Melbourne, VIC, Australia, October 19 - 23, 2015, pages 831–840, 2015 [26] C Song, W Hsu, and M Lee Temporal influence blocking: Minimizing the effect of misinformation in social networks In 33rd IEEE International Conference on Data Engineering, ICDE 2017, San Diego, CA, USA, April 19-22, 2017, pages 847–858, 2017 [27] Y Tang, Y Shi, and X Xiao Influence maximization in near-linear time: A martingale approach In Proc SIGMOD, pages 1539–1554, 2015 [28] Y Tang, X Xiao, and Y Shi Influence maximization: near-optimal time complexity meets practical efficiency In Proc SIGMOD, pages 75–86, 2014 [29] H Zhang, M A Alim, X Li, M T Thai, and H T Nguyen Misinformation in online social networks: Detect them all with a limited budget ACM Transactions on Information Systems, 34(3):18:1–18:24, 2016 [30] Y Zhang, A Adiga, S Saha, A Vullikanti, and B A Prakash Nearoptimal algorithms for controlling propagation at group scale on networks IEEE Trans Knowl Data Eng., 28(12):3339–3352, 2016 [31] Y Zhang and B A Prakash Scalable vaccine distribution in large graphs given uncertain data In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, CIKM 2014, Shanghai, China, November 3-7, 2014, pages 1719–1728, 2014 47 [32] Y Zhang and B A Prakash Data-aware vaccine allocation over large networks ACM Transactions on Knowledge Discovery from Data, 10(2):20:1–20:32, 2015 ... CHƯƠNG NGĂN CHẶN THÔNG TIN SAI LỆCH TRÊN MẠNG XÃ HỘI Ở DIỆN RỘNG 22 3.1 Đặt vấn đề 22 3.2 Bài toán Ngăn chặn thông tin sai. .. Mở đầu, nội dung luận văn bố cục thành chương sau: Chương 1: Giới thiệu mạng xã hội tác hại thông tin sai lệch Chương 2: Mô hình lan truyền thơng tin sai lệch Chương 3: Ngăn chặn thông tin sai. .. để ngăn chặn tác hại lan truyền thông tin sai lệch mạng xã hội trình bày chương sau 16 CHƯƠNG MƠ HÌNH LAN TRUYỀN THƠNG TIN SAI LỆCH Bản chất lan truyền thông tin sai lệch lan truyền thơng tin