ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ' oơo - 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Ệ ' oơo - 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 Hồng Xuân Huấn Hà Nôi — 2019 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 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 tơi 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 LỜI CẢM ƠN Trước hết, tơi 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 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ỪVIET 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 .6 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 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 tố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 toá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 DANH SÁCH HÌNH VẼ 2.1 Ví dụ q trình lan truyền thơng tin mơ hình 2.2 Ví dụ q trình lan truyền thơng tin mơ hình IC LT 19 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 = 0.5 38 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 = 0.5 với liệu Gnutella 39 DANH MỤC CÁC TỪ VIET TÁT Từ viết tắt Tiếng Anh Tiếng Việt FLE Fast And Effective Limiting Epidemics Thuật toán nhanh hiệu đe giới hạn lây nhiễm thông tin IC Independent Cascade Limiting the Spread of Epidemics Bậc độc lập Hạn chế lây lan thông tin sai lệch Linear Threshold Ngưỡng tuyến tính Social Network Time Constraint Deterministic Linear Threshold Mạng xã hội LSE LT MXH T-DLT Mơ hình lan truyền thơng tin Ngưỡng tuyến tính xác đinh với ràng buộc thời gian 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ả - 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 • A (I): tập đỉnh bị ảnh hưởng I bước t t ã ô+(v) = nh v EA( _, nNj (v) w(u,v): tổng trọng số ảnh hưởng đến n • a(u): đánh giá ảnh hưởng từ u đến đỉnh khác • fì(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ố fì(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 fì() lớn vịng lặp Algorithm 3: Thuật tốn FLE - Input: Graph G = (V, E, 0), I, d, k, ỡ - Output: Solution A S '; Calculate G' ^ Gd(I); U ^ Vd -for i =1 to k Calculate 14 return Sa(u), p(u) on G (Algorithm 5) u max ^ = 0,8v U then if £(v) Chi tiết thuật toán mơ tả Thuật tốn 3, thuật u I max ^ arg max a(v) v2U else I umax ^ arg 10 11 end 12 S S f u ^ [ maxg, U ^ U 13 max p (v) v2U \ f umaxg Remove u and all edges that adjacent with u from G max end max - tốn tính gần a() fì() mơ tả Thuật tốn Thuật tốn - Algorithm 4: Thuật tốn tính fd(I);ữ+();t() - Input: Graph G = (V; E), I, d - Output: A (I); a+(u); t(u); ¥u G foreach u in G I ữ+(u) — 0; t(u) — 0; Ad(l) — ; d end For each s in I: t(s) — -4 - -6 10 11 12 13 14 15 16 17 18 Queue Q — I while Q = ; - u — Q.pơp(); Ad(I) — u - if t(u) < d then foreach v N (u) - if t(u) < t(v) then a+(v) = a+(v) + w(u;V) - if a+(v) > ỡ and t(u) + < t(v) then t(v) — t(u) + - Q.push(v) out v end - end end - 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) A (I) (dòng 7) - Trong Thuật tốn 5: thuật tốn tính hai giá trị O; J đỉnh dựa giá trị A (I);ữ ();t() thuật toán trước Với đỉnh i thuộc A (I), thuật tố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ị a(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 d d d t - (điều kiện dịng 6) fì(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(m +n ) (Áp dụng BFS) Với bước tính tốn a(u) fì(u) (Thuật tốn 5, dịng - 11), có độ phức tạp tương tự O(m + n ) Do đó, độ phức tạp chung Thuật tốn FLE O(k(m + n ) 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 d d d d - -1 - - d Algorithm 5: Thuật tốn tính n , V() Input: Graph G = (V; E; 0), I, d, A (I),a ();t() Output: a(u);fi(u); 8u G foreach u in A (I) «(u) —— 0; p(u) —— foreach v in Nout(u) \ A (I) -if t(u) < t(v) then - a(u) — a(u) + w(u, v) - if a+(v) — w(u,v) < ỡ then - I fì (u) — fì (u) + d t d - - d d v - 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 V đủ k đỉnh d - Hai thuật toán dùng phổ biến nghiên cứu toán - 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 Số Lo Bậc trung - ố đỉnh6, - cạnh 20 - ại Có bìnhGnutella [13] 3.29 Wikipedia vote - 301 7, - ,777 10 -hướng Có 14.57 [13] 115 3,689 hướng 1, Có Amazon [19] 4.71 62,111 234,877 hướng Google web 5, Có 5.83 [31] 75,713 105,039 hướng - Các tham số thiết lập sau • Trọng số cạnh: w(u,v) = d 1(v), với d (v) bậc vào đỉnh v in [11, 7,12] • 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: 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) WIKI VOTE, k = 50, d = GNUTELLA, k = 50, d = theta theta theta theta GOOGLE WEB, k = 50, d = 18000 16000 14000 12000 10000 8000 6000 4000 2000 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 - - theta 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 = - - 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 = 0.5 - - - 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 = 5)0,0 = 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 tố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(n k(md + n )), FLE có độ phức tạp nhỏ nhiều O(k(md + n )) Trong liệu Amazon Google Web, d d d - Greedy khơng thể 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 - 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 toá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 toán thơng dụng khác thuật tốn Max Degree thuật tố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ế - 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) - 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):555584, 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 [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 E 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 [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 Computer Networks, 57(10):2133-2146, 2013 [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 107116, 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 [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 ofthe 23rd ACM International Conference on Conference on Information and Knowledge Management, CIKM 2014, Shanghai, China, November 3-7, 2014, pages 1719-1728, 2014 [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 94 Chương trình bày giải pháp ngăn chặn thơng tin sai lệch mạng xã hội diện rộng bao gồm: (1) đề xuất mơ hình lan truyền thơng tin, ... cứu tốn ngăn chặn thơng tin sai lệch chương sau 69 Để đưa giải pháp hiệu việc ngăn chặn lan truyền thông tin sai lệch, trước tiên phải hiểu chế thông tin sai lệch lan truyền MXH 70 Thông tin phát... 3.2 Bài tốn Ngăn chặn thông tin sai lệch với ngân sách giới hạn 101 Bài toán đề xuất nghiên cứu sau xem xét thực tế trình lan truyền thông tin sai lệch mạng xã hội Thông tin sai lệch số người