Luận văn 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

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 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 1.2 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 1.3 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 Thuật ngữ tiếng Việt IC Independent Cascade Mô hình tầng độc lập LT Linear Threshold Mô hình ngưỡng tuyến tính MDM Minimize Damage of Misinforma- Bài toán cực tiểu hóa thiệt hại do tion thông tin sai lệch gây ra MXH Social Network Mạng xã hội Danh sách bảng 1.1 Một số mạng xã hội tiêu biểu cho phân bố luật lũy thừa . . . . . 12 4.1 Dữ liệu thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Danh sách hình vẽ 1.1 Bảng xếp hạng các mạng xã hội theo số lượng người dùng, tháng 1/2017 (đơn vị Triệu người dùng) . . . . . . . . . . . . . . . . . . . 6 1.2 Các trang mạng xã hội trên Internet . . . . . . . . . . . . . . . . . 8 1.3 Đặc trưng thế giới nhỏ của mạng xã hội . . . . . . . . . . . . . . . 11 1.4 Đặc trưng tập nhân của mạng xã hội . . . . . . . . . . . . . . . . . 12 1.5 Mạng đồng tác giả . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.6 Đường kính mạng xã hội Facebook . . . . . . . . . . . . . . . . . . 14 1.7 Mô hình câu lạc bộ karate của Zachary, một trong những mô hình chuẩn cho bài toán phát hiện cấu trúc cộng đồng . . . . . . . . . . 14 1.8 Sự tiến hóa của mạng lưới những nhà phát minh làm việc cho Apple trong 6 năm . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1 Một ví dụ quá trình lan truyền thông tin trên mô hình IC . . . . 26 2.2 Một ví dụ quá trình lan truyền thông tin trên mô hình LT . . . . 28 3.1 Phép dẫn từ bài toán Tập phủ dạng 0 − 1 đến bài toán MDM . . . 40 4.1 Tổng thiệt hại khi ngân sách B thay đổi, d = 6, |S| = 10 . . . . . . 48 4.2 Tổng thiệt hại khi ngân sách B thay đổi, d = 6, |S| = 20 . . . . . . 49 4.3 Độ giảm thiệt hại khi kích thước nguồn S thay đổi, d = 5, B = 25 50 1 MỞ ĐẦU Ngày nay, các mạng xã hội trực tuyến đã trở thành một phần không thể thiếu trong cuộc sống của con người, cho phép mỗi chúng ta có thể tạo, chia sẻ và trao đổi thông tin, ý tưởng một cách nhanh chóng và dễ dàng hơn bao giờ hết. Đối với nhiều người dùng, các trang mạng xã hội trực tuyến như Facebook, Twitter, Google+ được coi là những kênh tin tức chính. Trong nhiều trường hợp, các trang mạng xã hội này còn đưa những tin tức quan trọng trước cả một số phương tiện truyền thông đại chúng khác như phát thanh, truyền hình vv.. Ví dụ, tin tức về trùm khủng bố Bin Laden bị tiêu diệt lan truyền trên Twitter trước khi Tổng thống Mỹ chính thức thông báo trên các phương tiện truyền thông công cộng [52] hoặc câu chuyện về cái chết của ca sĩ Whitney Houston lan rộng trên Twitter, trước 27 phút so với hãng tin AP (Associated Press) [53]. Có thể nói rằng, các trang mạng xã hội ngày nay là một trong những nguồn cung cấp thông tin phong phú, đa chiều và là "nơi khám phá tin tức" của nhiều độc giả, đặc biệt là những độc giả trẻ và phụ nữ, chiếm số đông nhất trong nhóm chọn mạng xã hội để cập nhật tin tức. Bên cạnh những thông tin tin cậy, chính xác thì những thông tin sai lệch cũng lan truyền rộng rãi trên mạng xã hội một cách dễ dàng. Một nhóm nghiên cứu đến từ Đại học Columbia (New York, Mỹ) [23] đã chỉ ra rằng tốc độ lan truyền của thông tin sai lệch ngang bằng so với những tin tức chính thống. Chính những điều này đã gây ra những thiệt hại to lớn cho các cá nhân, tổ chức không những về kinh tế, chính trị mà còn tác động đến tâm lý, cuộc sống con người. Gần đây, diễn đàn Kinh tế thế giới (World Economic Forum, 2014) đã coi sự gia tăng nhanh chóng của thông tin sai lệch trên các phương tiện xã hội trực tuyến là một trong mười xu hướng hàng đầu mà thế giới phải đối mặt. Trước những thách thức nêu trên, làm thể nào để có thể hạn chế sự lan truyền của thông tin sai lệch trên mạng xã hội một cách kịp thời và hiệu quả? là một câu hỏi đang nhận được sự quan tâm nghiên cứu của nhiều nhà khoa học trong thời gian gần đây. Một số nghiên cứu tập trung vào việc nhận dạng thông tin sai lệch và tin đồn (Rumor) như nghiên cứu của Qazvinian, 2011, [6] và Kwwon, 2013, [7]. Một số khác, nghiên cứu vấn đề xác định tập đỉnh là nguồn phát thông tin sai 2 lệch ban đầu. Chẳng hạn, Dung T. Nguyen và các cộng sự, 2012, [65] đã nghiên cứu bài toán xác định k nguồn phát tán thông tin sai lệch khả nghi nhất từ tập người dùng bị kích hoạt bởi thông tin sai lệch cho trước. Bên cạnh đó, một số tác giả đề xuất giải pháp hạn chế sự lan truyền thông tin sai lệch trên mạng xã hội bằng cách chọn ra một số đỉnh ban đầu để tiêm thông tin tốt, từ đó lan truyền những thông tin này trên cùng mạng nhằm thuyết phục những người dùng khác tin theo, trong đó sử dụng các mô hình lan truyền thông tin khác nhau [2–4]. Budak và các cộng sự, 2011, [2], đã đưa ra mô hình tầng độc lập đa chiến dịch (Multi-Campaign Independent Cascade Model), gồm chiến dịch phổ biến thông tin tốt và chiến dịch phổ biến thông tin sai lệch cùng cạnh tranh với nhau. H. Zhang và các cộng sự, 2015, [3], đã nghiên cứu bài toán hạn chế sự lan truyền thông tin sai lệch dưới mô hình kích hoạt cạnh tranh (Competitive Activation Model). Hay như trong nghiên cứu của N. P. Nguyen và các cộng sự, 2013, [4], đã nghiên cứu bài toán hạn chế thông tin sai lệch dưới hai mô hình tầng độc lập (Independent Cascade) và ngưỡng tuyến tính (Linear Threshold), đồng thời đề xuất thuật toán xác định một tập nhỏ nhất các đỉnh có ảnh hưởng lớn nhất, từ đó lan truyền những thông tin tốt nhằm hạn chế ảnh hưởng của thông tin sai lệch. Đặc biệt, ngoài những hướng nghiên cứu kể trên còn một cách tiếp cận khác trong việc ngăn chặn thông tin sai lệch lan truyền trên mạng xã hội được trình bày trong công trình nghiên cứu của H. Zhang và các cộng sự, 2016, [1], bằng cách đặt giám sát (Monitor Placement) trên một số đỉnh của đồ thị mạng nhằm ngăn chặn thông tin sai lệch lây lan đến những đỉnh khác trong cùng mạng. Đặt giám sát là phương pháp sử dụng các bộ lọc nội dung nhằm phát hiện thông tin sai lệch ở người dùng (đỉnh) được cài đặt và ngăn chặn sự chia sẻ, lan truyền thông tin sai lệch từ đỉnh này; hoặc trong ngữ cảnh khác có thể hiểu là việc thuyết phục người dùng (đỉnh) không tin theo và lan truyền thông tin sai lệch. Một số công trình nghiên cứu khác gọi phương pháp này với tên gọi đó là phương pháp tạo miễn dịch (Immunize) cho các đỉnh trong đồ thị mạng xã hội. Đứng trước những nguy cơ mất an toàn, an ninh thông tin trên mạng xã hội do thông tin sai lệch gây ra, đồng thời thúc đẩy bởi những công trình nghiên cứu đã nêu ở trên, đặc biệt là nghiên cứu của H. Zhang, 2016, [1] đã tạo động lực cho tác giả lựa chọn đề tài "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" làm đề tài luận văn của mình. 3 Đóng góp chính của luận văn bao gồm: - Thứ nhất, đề xuất một mô hình ngưỡng tuyến tính cho bài toán Cực tiểu hóa thiệt hại do thông tin sai lệch gây ra, đồng thời chứng mình bài toán này thuộc lớp bài toán NP-khó. - Thứ hai, đề xuất hai thuật toán tham lam nhằm giải quyết bài toán đặt ra. - Thứ ba, kết quả thực nghiệm cho thấy ưu điểm nổi trội của hai thuật toán đề xuất so với các thuật toán thông dụng khác như thuật toán bậc cực đại (Max Degree) và thuật toán ngẫu nhiên (Random) trong việc hạn chế thông tin sai lệch lan truyền trên mạng. Ngoài phần mở đầu và kết luận, bố cục chính của luận văn gồm bốn chương như sau: Chương 1: Giới thiệu về mạng xã hội Chương này giới thiệu tổng quan về mạng xã hội gồm: Định nghĩa mạng xã hội, lịch sử hình thành, phát triển và những đặc trưng cơ bản của mạng xã hội. Đặc biệt, trong chương này trình bày tổng quan một số chủ đề nổi bật liên quan đến mạng xã hội, đã và đang nhận được sự quan tâm nghiên cứu của nhiều học giả trong thời gian gần đây. Chương 2: Thông tin sai lệch và các mô hình lan truyền thông tin sai lệch Chương này tác giả trình bày định nghĩa thông tin sai lệch, những nguy cơ và hậu quả do thông tin sai lệch gây ra đối với các cá nhân, tổ chức. Đồng thời, phân tích cơ chế lan truyền thông tin và những đặc tính của hai mô hình lan truyền thông tin đang được sử dụng rộng rãi bao gồm: Mô hình tầng độc lập và mô hình ngưỡng tuyến tính. Ngoài ra, ở Chương 2 tổng quan 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. Chương 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 Từ thực trạng đã nêu trong Chương 2 và xuất phát từ những công trình nghiên cứu liên quan trước đó, tác giả phát biểu bài toán Cực tiểu hó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, chứng minh bài toán này thuộc lớp bài toán NP-khó, đồng thời đề xuất thuật toán nhằm giải quyết bài toán này. 4 Chương 4: Thực nghiệm Mô tả các bước tiến hành và kết quả thực nghiệm nhằm đánh giá hiệu quả của thuật toán đề xuất trong việc ngăn chặn sự lan truyền của thông tin sai lệch. Thực nghiệm tiến hành dựa trên ba bộ dữ liệu là các mạng xã hội thực, bao gồm: Gnutella, CollegeMsg và Email. Kết quả thực nghiêm cho thấy, thuật toán do tác giả đề xuất tốt hơn các thuật toán thông dụng khác như thuật toán bậc cực đại (Max Degree) và thuật toán ngẫu nhiên (Random). 5 Chương 1 GIỚI THIỆU VỀ MẠNG XÃ HỘI Chương này giới thiệu tổng quan về mạng xã hội bao gồm: Định nghĩa mạng xã hội, lịch sử hình thành, phát triển và những đặc trưng cơ bản của mạng xã hội. Đặc biệt, trong chương này trình bày tổng quan một số chủ đề nổi bật liên quan đến mạng xã hội, đã và đang nhận được sự quan tâm nghiên cứu của nhiều học giả trong thời gian gần đây. 1.1 Giới thiệu chung về mạng xã hội Trong những năm gần đây, cùng với sự phát triển của Web 2.0, các mạng xã hội trực tuyến như Facebook1, Twitter2, Instagram3 ngày càng trở lên phổ biến và có sự phát triển nhanh chưa từng thấy. Theo số liệu thống kê công bố trên trang Statista4, tính đến tháng 1/2017, Facebook vẫn là mạng xã hội có lượng người dùng lớn nhất thế giới với hơn 1.87 tỉ người sử dụng, Twitter với 317 triệu người dùng đứng ở vị trí thứ 9 trong bảng xếp hạng. Theo Marin và Wellman [30], mạng xã hội (MXH) là một tập hợp các tác nhân có yếu tố xã hội được kết nối với nhau bởi một hoặc nhiều các quan hệ xã hội. Ngoài ra, MXH còn có những định nghĩa khác: MXH là một cấu trúc xã hội được tạo thành từ các nút và các cung mà mỗi nút được liên kết bởi một hoặc nhiều cung khác nhau, thể hiện một mối quan hệ cụ thể [31]. Mỗi nút thường được gọi là tác nhân, đại diện cho một đối tượng trong mạng xã hội, có thể là một người, một nhóm người, một tài liệu, một tổ chức hay một quốc gia vv.. Mỗi cung là một liên kết giữa các nút, biểu diễn mối quan hệ giữa các đối tượng. Liên kết này có thể là mối quan hệ họ hàng, người quen, bạn bè, đồng nghiệp, cũng có thể là các giao dịch, trao đổi tài chính vv.. Nếu mối quan hệ giữa các đối tượng là quan hệ qua lại thì có thể biểu diễn bằng một liên kết vô hướng, chẳng hạn nếu người A là đồng nghiệp của người B thì ngược lại người B cũng 1https://www.facebook.com 2https://www.twitter.com 3https://www.instagram.com 4 6 là đồng nghiệp của người A. Nếu mối quan hệ này là quan hệ một chiều thì có thể biểu diễn bằng một liên kết có hướng, ví dụ người A mua hàng của người B nhưng chưa chắc người B đã mua hàng của người A. Rõ ràng, khái niệm về MXH không chỉ giới hạn trong trường hợp cụ thể là những trang mạng xã hội (Social Network Sites) như WhatsApp, Instagram, Viber vv.. Các vấn đề của MXH đã được nghiên cứu thường xuyên trong lĩnh vực xã hội học, trước sự ra đời của máy tính và Internet. Khi MXH này được thiết lập và thi hành bằng các phương tiện truyền thông Internet, nó được hiểu là MXH trực tuyến (Online Soial Network). Nhìn từ nhiều phía, MXH trực tuyến là một đại diện tiêu biểu của Web 2.0 mô phỏng các quan hệ xã hội thực. MXH trực tuyến tạo ra một hệ thống trên nền Internet kết nối các thành viên cùng sở thích với nhiều mục đích khác nhau không phân biệt không gian và thời gian qua những tính năng như kết bạn, chat, e-mail, phim ảnh, voice chat, chia sẻ tập tin, blog và xã luận. Những người sử dụng MXH này được gọi là những cư dân mạng. Nhờ vào những ưu việt này mà MXH trực tuyến đang có tốc độ phát triển chóng mặt ở mọi lứa tuổi, đặc biệt là ở giới trẻ trên toàn thế giới. Hình 1.1: Bảng xếp hạng các mạng xã hội theo số lượng người dùng, tháng 1/2017 (đơn vị Triệu người dùng) 7 1.1.1 Lịch sử phát triển của mạng xã hội Lịch sử phát triển của MXH luôn đồng hành cùng với sự phát triển của Internet. Từ những email đầu tiên được gửi đi bởi các nhà nghiên cứu Thụy Sĩ vào năm 1971 đến những MXH hiện đại như Facebook, Twitter vv.. Internet và các nội dung chia sẻ luôn gắn liền với tính chất cộng đồng. Mục tiêu chính của Internet là tạo phương tiện để con người có thể kết nối, giao tiếp và tương tác với nhau. Tuy nhiên, từ lúc xuất hiện đến nay, mạng xã hội đã trải qua nhiều thay đổi nhanh chóng cả về nguyên lý làm việc lẫn giao diện đồ họa. Năm 1991, nhà khoa học Tim Berner-Lee thuộc Phòng thí nghiệm vật lý vi mô châu Âu (CERN) đã đề xuất một giao thức mới để phát tán thông tin. Giao thức đính kèm đường dẫn dưới dạng ký tự ẩn dưới những ký tự khác (Link). Cuối cùng hình thành nên giao thức kết nối Internet World Wide Web (WWW). Năm 1994 đánh dấu sự ra đời của Blog cá nhân đầu tiên. Justin Hall là sinh viên đại học Swarthmore đã phát triển website mang tên Justin’s Link from the Underground để kết nối với thế giới bên ngoài. Hall đã xây dựng trang web trong suốt 11 năm và anh được mệnh danh là "cha đẻ của trang blog cá nhân". Năm 1995 đánh dấu sự ra đời của trang Classmate5 với mục đích hỗ trợ những người di cư có thể tìm lại bạn bè đã thất lạc của họ. Đây là một dịch vụ cộng đồng được tạo ra để giúp tìm lại những bạn học từ thời tiểu học, trung học và đại học của người dùng. Năm 1997, một chương trình nhắn tin có quảng cáo AOL Instant Messenger6 (AIM) đã ra đời, cho phép hàng triệu người có thể trò chuyện thời gian thực với nhau. Trong khoảng thời gian này, trang MXH SixDegree7 được thành lập với mục đích giao lưu kết bạn dựa theo sở thích. Năm 2000, Jimmy Wales và Larry Sanger sáng lập nên Wikipedia8, bách khoa toàn thư nguồn mở, trực tuyến và có tính cộng tác đầu tiên trên thế giới. Năm 2001, sau vụ khủng bố trung tâm thương mại thế giới vào ngày 11/9/2001 đã gợi cảm hứng cho Scott Heiferman tìm cách tạo ra trang web Meetup9 nhằm giúp mọi người có thể kết nối với nhau và thậm chí không cần online. Meetup.com có mục đích duy nhất là tạo điều kiện cho những người có cùng suy nghĩ gặp gỡ, trò truyện, học tập và kết nối. Trang web hướng tới mục đích mang mọi người 5https://www.classmate.com 6https://www.aol.com 7https://www.sixgegrees.org 8https://www.wikipedia.org 9https://www.meetup.com 8 ra khỏi nhà, tham gia vào các mối quan hệ và giao tiếp cùng với những người khác. Hiện trang web đã được phổ biến rộng rãi, mỗi tháng có hơn 340.000 hội nhóm tổ chức gặp gỡ, giao tiếp, làm việc, ăn uống và cùng nhau học tập. Năm 2002, MXH Friendster10 ra đời và trở thành một trào lưu mới tại Hoa Kỳ với hàng triệu người dùng đăng ký. Friendster cho phép người dùng tạo thông tin cá nhân và kết nối ảo với những người khác. Đây là MXH đầu tiên đạt được hơn 1 triệu người dùng. Kế thừa các bước phát triển của các MXH đi trước, MXH MySpace11 được sáng lập và ra đời vào năm 2003 bởi Chris DeWolfe và Tom Andersonra. Với nhiều tính năng mới cho phép người dùng tải các hình ảnh, video do vậy chỉ 1 tháng sau khi ra mắt, MySpace nhanh chóng đạt hơn 1 triệu tài khoản đăng ký. Do nắm được các nhu cầu của người dùng, MySpace trở thành MXH đầu tiên có nhiều lượt xem vượt qua cả Google, tuy nhiên sự ra đời của Facebook đã khiến cho Myspace nhanh chóng trở thành dĩ vãng. Năm 2004, Mark Zuckerburg giới thiệu MXH Facebook, đánh dấu bước ngoặt mới cho hệ thống MXH trực tuyến. Với nền tảng Facebook Platform hỗ trợ mạnh mẽ cho các ứng dụng, người dùng có thể tạo ra những ứng dụng mới cho cá nhân mình cũng như các thành viên khác. Facebook nhanh chóng gặt hái được thành công vược bậc, mang lại hàng trăm tính năng mới và trung bình các thành viên bỏ ra 19 phút trên trang này mỗi ngày. Hình 1.2: Các trang mạng xã hội trên Internet 10https://www.friendster.org 11https://www.myspace.org 9 Năm 2005, MXH YouTube12 ra đời, cho phép người dùng tự do đăng tải và chia sẻ video với gia đình, bạn bè. Tiếp sau đó, năm 2006, MXH Twitter ra đời, cho phép mỗi cá nhân có thể truyền đạt thông tin một cách nhanh chóng và dễ dàng đến với một nhóm lớn. Năm 2011, MXH Google+ ra đời, đây là một MXH có đầy đủ tính năng của Google. Người dùng Google+ đánh giá cao khả năng nhóm các danh sách liên lạc vào các đoạn khác nhau (thường gọi là Vòng) và giao tiếp với nhau qua công cụ chat Video có tên Hangouts. Năm 2012, Pinterest13 là MXH hình ảnh đồ họa và đã vượt mức 10 triệu người dùng, phát triển nhanh hơn bất cứ trang web độc lập nào khác. Ngoài những MXH nổi tiếng nêu trên, còn có hàng trăm MXH khác trên toàn thế giới: Flickr, WeChat, Sina Weibo, Baidu Tieba vv.. Ở Việt Nam hiện nay có một số MXH như: Zing Me, YuMe, Tamtay cũng đã thu hút được nhiều người dùng nhiều với mục đích khác nhau. 1.1.2 Những tính năng của mạng xã hội - Tính liên kết cộng đồng: Đây là tính năng nổi bật của MXH trực tuyến cho phép mở rộng phạm vi kết nối giữa con người với con người trong một không gian đa dạng. Người sử dụng có thể trở thành bạn của nhau thông qua việc gửi lời mời kết bạn mà không cần gặp gỡ trực tiếp. Việc tạo ra các liên kết này hình thành một cộng đồng mạng với số lượng thành viên lớn. Những người chia sẻ cùng một mối quan tâm có thể tập hợp lại thành các nhóm trên MXH, thường xuyên giao lưu, chia sẻ trên mạng thông qua việc bình luận hay dẫn đến các liên kết trên trang chung của nhóm. - Tính đa phương tiện: Hoạt động theo nguyên lý của web 2.0, MXH có rất nhiều tiện ích nhờ sự kết hợp giữa các yêu tố văn bản, âm thanh, hình ảnh, hình ảnh động, video vv.. Sau khi đăng ký mở tài khoản, người dùng có thể tự do xây dựng một không gian riêng cho bản thân. Nhờ những tiện ích và dịch vụ mà MXH cung cấp, người dùng có thể chia sẻ đường dẫn, tệp âm thanh, hình ảnh, video vv.. Không những vậy, họ còn có thể tham gia vào các trò chơi trực tuyến, gửi tin nhắn, trò chuyện trực tuyến với bạn bè từ đó tạo dựng các mối quan hệ mới trong xã hội ảo. - Tính tương tác: Thể hiện không chỉ ở chỗ thông tin được truyền đi sau đó 12https://www.youtube.com 13https://www.pinterest.com 10 được phản hồi từ phía người nhận, mà còn phụ thuộc vào cách người dùng sử dụng ứng dụng của MXH. - Khả năng truyền tải và lưu trữ thông tin: Một tính năng quan trọng của MXH giúp thông tin được lan truyền rộng rãi trong một khoảng thời gian ngắn. Những thành viên trong MXH là một mắt xích để tạo ra mạng lưới truyền tải thông tin, họ có thể tương tác với nhau bất kể khoảng cách về địa lý, ngôn ngữ, giới tính, tôn giáo. Nếu như trong thế giới thực, chúng ta phải gặp nhau để trao đổi, trò chuyện, hay cùng hợp tác thì ngày nay việc đó thật đơn giản và thuận tiện hơn rất nhiều nhờ MXH. 1.2 Các đặc trưng cơ bản của mạng xã hội 1.2.1 Đặc trưng thế giới nhỏ Vấn đề nghiên cứu cấu trúc MXH đã gây được sự chú ý và quan tâm sâu sắc của các nhà nghiên cứu trong nhiều năm qua. Đầu tiên là thí nghiệm nổi tiếng có tên gọi "thí nghiệm thế giới nhỏ" (Small World Experiment) được thực hiện bởi Stanley Milgram, 1967, nhằm tính toán số bước cần thiết để hai người bất kỳ trong một dân số đã được xác định có thể biết nhau. Để thực hiện được điều nay, Milgram đã chọn ngẫu nhiên một số cá nhân ở các thành phố là điểm khởi đầu và điểm kết thúc. Mỗi cá nhân ở điểm khởi đầu được yêu cầu gửi một bức thư có nội dung là thông tin liên lạc của cá nhân cần tìm ở điểm kết thúc tới người mà họ biết. Người nhận được thư sẽ phải chuyển tiếp bức thư tới một người là bạn bè hoặc người thân của họ mà họ cho rằng người đó có khả năng cao nhất biết người cần tìm. Cứ như vậy cho đến khi bức thư đến được tay người cần tìm. Và kết quả là 64 trong 296 bức thư đã được chuyển đến đích với số bước trung bình khoảng 5.5 hoặc 6. Do đó, các nhà nghiên cứu kết luận rằng giữa hai người dân bất kỳ ở Hoa Kỳ có thể biết nhau thông qua trung bình khoảng 6 bước. Trên thực tế, người ta đã kiểm chứng được "hiện tượng thế giới nhỏ" (Small World Phenomenon) đúng với hầu hết các MXH nhỏ. Đối với các MXH lớn như Facebook, khoảng cách trung bình kết nối giữa hai người dùng bất kỳ trên thế giới là 5.28 bước vào năm 2008 và đến năm 2011 khoảng cách này rút ngắn xuống còn 4.74. 11 Hình 1.3: Đặc trưng thế giới nhỏ của mạng xã hội 1.2.2 Đặc trưng tập nhân Cấu trúc và sự vận động của MXH chịu tác động bởi các nút có số lượng lớn các cung kết nối hay các nút có bậc cao. Người ta gọi những nút này là nút trung tâm hay nút nhân. Phân tích cấu trúc MXH đã chỉ ra rằng, MXH luôn chứa một lượng lớn những nút có bậc cao [32]. Bao quanh các nút này là các nút có bậc thấp hơn, và quanh những nút có bậc thấp hơn này lại là các nút có bậc thấp hơn chúng, cứ như vậy tạo thành một hệ thống phân cấp. Các nút nhân có vai trò quan trọng trong việc kết nối luồng thông tin của toàn mạng. Nếu ta chọn một nút có số bậc lớn và đưa ra khỏi mạng, mạng sẽ phân chia thành các nhóm cô lập nhau. Một nút mới khi được thêm vào mạng thường có xu hướng kết nối đến những nút có bậc cao, đây gọi là hiện tượng "rich get richer" ("người giàu thường trở lên giàu hơn"). Điều này giải thích tại sao trong mạng những công trình khoa học, các bài báo được tham chiếu nhiều thì lại được nhiều người nghiên cứu và tham chiếu hay như trong các MXH trực tuyến chúng ta thường có xu hướng kết bạn với những người nổi tiếng vv.. 1.2.3 Phân bố luật lũy thừa Sự phân bố bậc của các nút trong mạng được mô tả bởi hàm P (k), hàm này cho biết xác suất của một nút có bậc là k. Phân bố bậc mô tả các các liên kết trong mạng phân bố như thế nào giữa các nút. 12 Hình 1.4: Đặc trưng tập nhân của mạng xã hội Phân bố bậc của một mạng là tuân theo luật lũy thừa nếu xác suất một nút có bậc là k tỉ lệ với k−α, với k lớn và α > 1. Hiện nay, hầu hết các MXH đều có phân bố bậc theo luật lũy thừa [33]. Bảng 1.1 liệt kê một số mạng với số mũ α. Tên mạng Số mũ α WWW 2.3/2.7 Film Actors 2.3 Telephone Call Graph 2.1 Email Networks 1.5/2.0 Sexual Contacts 3.2 Internet 2.5 Peer-To-Peer 2.1 Metabolic Network 2.2 Protein Interactions 2.4 Bảng 1.1: Một số mạng xã hội tiêu biểu cho phân bố luật lũy thừa 1.2.4 Đặc trưng cấu trúc cộng đồng Theo Simmel, 1995, thì cộng đồng là một tập các thực thể có những tính chất tương tự nhau và/hoặc cùng đóng một vai trò trong MXH. Trong xã hội ngày nay, tồn tại nhiều nhóm cộng đồng khác nhau, chẳng hạn như nhóm bạn bè có cùng sở thích, cộng đồng những nhà khoa học, các câu lạc bộ thể thao vv.. Sự phát triển của MXH trực tuyến cũng tạo ra nhiều nhóm ảo, hay còn gọi là các cộng đồng trực tuyến. MXH có một đặc trưng quan trọng đó là cấu trúc cộng đồng, trong mạng được phân chia thành các cộng đồng lớn nhỏ khác nhau; bên trong các cộng đồng lớn 13 có những cộng đồng con nhỏ hơn. Giữa các nút trong một cộng đồng có mật độ kết nối lớn hơn so với các nút bên ngoài. Hình 1.5: Mạng đồng tác giả Xét theo tiêu chí cấu trúc, cộng đồng được chia thành hai kiểu: cấu trúc cộng đồng tách rời và cấu trúc cộng đồng chồng chéo. Đối với cấu trúc cộng đồng chồng chéo, một nút có thể thuộc nhiều cộng đồng khác nhau. Ngược lại, trong cấu trúc cộng đồng tách rời, một nút chỉ thuộc duy nhất một cộng đồng. 1.2.5 Các đặc trưng khác của mạng xã hội Một mạng có đường kính d nếu mọi cặp nút trong mạng được kết nối với nhau bằng một đường chiều dài tối đa bằng d. Leskovec, 2005, [34] đã chỉ ra rằng MXH không chỉ có đường kính nhỏ (đặc trưng thế giới nhỏ) mà đường kính mạng còn co ngắn lại và sau đó giữ ổn định theo thời gian. MXH trực tuyến Facebook là một ví dụ điển hình cho đặc trưng này, năm 2008 đường kính của mạng Facebook là 5.28, đến năm 2011 đường kính của mạng rút ngắn xuống còn 4.74 và đến thời điểm hiện tại là 3.57. Ngoài ra, nghiên cứu của Leskovec cũng chỉ ra rằng, bậc trung bình của các nút trong mạng tăng theo thời gian do số lượng liên kết tăng "siêu" tuyến tính so với số lượng nút. 14 Hình 1.6: Đường kính mạng xã hội Facebook 1.3 Một số chủ đề được nghiên cứu trên mạng xã hội 1.3.1 Phát hiện cấu trúc cộng đồng trên mạng xã hội Một vấn đề quan trọng trong phân tích MXH đó là bài toán phát hiện cấu trúc cộng đồng (Community Structure). Mục tiêu của bài toán là từ các MXH cho trước, phát hiện được các cấu trúc cộng đồng nằm trong đó và tìm hiểu mối liên hệ bên trong các cộng đồng cũng như giữa các cộng đồng với nhau, mối liên hệ đó ảnh hưởng thế nào đến cấu trúc của toàn MXH. Hình 1.7: Mô hình câu lạc bộ karate của Zachary, một trong những mô hình chuẩn cho bài toán phát hiện cấu trúc cộng đồng Bài toán phát hiện cấu trúc cộng đồng có liên quan chặt chẽ với các bài toán phân cụm nhằm phát hiện những khu vực mạng có mật độ liên kết dày đặc [35]. Việc phát hiện cấu trúc cộng đồng có nhiều ứng dụng cụ thể. Chẳng hạn, 15 trong mạng lưới quan hệ giữa khách hàng và sản phẩm trên một website bán hàng trực tuyến như Amazon14, việc xác định các cụm khách hàng có chung sở thích giúp xây dựng hệ thống tư vấn bán hàng hiệu quả. Hay trong bài toán phân cụm các Web Client gần nhau về mặt địa lý và có sở thích, thói quen tương tự nhau giúp cải thiện hiệu suất cung cấp dịch vụ trên World Wide Web, trong đó mỗi cụm khách hàng được phục vụ bởi một máy chủ chuyên dụng. Phát hiện cộng đồng giúp chúng ta hiểu được người dùng và giúp đưa ra góc nhìn về sự tương tác của người dùng trong MXH. Các nghiên cứu về phát hiện cấu trúc cộng đồng điển hình có thể kể đến là nghiên cứu của Newman, 2006, [36], nghiên cứu của Fortunato, 2010, [22] trình bày họ thuật toán phân tách Girvan-Newman theo độ trung gian cạnh Girvan- Newman, nghiên cứu của Gregory, 2009, [37] trình bày thuật toán chia đỉnh CONGA, CONGO, gán nhãn COPRA. 1.3.2 Dự đoán liên kết trên mạng xã hội Dự đoán liên kết không chỉ là một nhiệm vụ quan trọng trong phân tích MXH ...ghiệm sản phẩm đó (bằng cách tặng quà hoặc các khoản thanh toán). Công ty muốn rằng những người sử dụng ban đầu sẽ thích ứng dụng đó và bắt đầu ảnh hưởng đến bạn bè của họ để cùng sử dụng nó, và bạn bè của họ cũng sẽ như vậy. Bài toán đặt ra là với nguồn ngân sách cho trước, xác định được ai là người sẽ trải nghiệm ứng dụng để giúp lan truyền đến nhiều người dùng nhất cùng sử dụng sản phẩm. Trong bài báo đã công bố [47], Kempe và các cộng sự tập trung nghiên cứu vấn đề tối ưu hóa ảnh hưởng trên hai mô hình lan truyền thông tin: Mô hình IC và mô hình LT. Trong bài toán tối ưu hóa ảnh hưởng, có hai nhiệm vụ tính toán cần thực hiện: Đầu tiên, là việc xác định tập hạt giống nhằm cực đại hóa giá trị hàm lan truyền ảnh hưởng như trong Định nghĩa 2.1. Thứ hai, là việc tính giá trị hàm lan truyền ảnh hưởng σ(S0), với S0 là tập hạt giống. Cả hai nhiệm vụ tính toán này đều đã được chứng minh là hai vấn đề #P-khó dưới cả hai mô hình IC và LT [60,61]. Dựa trên tính chất của hàm mục tiêu σ(S0) (tính đơn điệu và tính submodular), Kempe đã đề xuất thuật toán tham lam cho lời giải có tỉ lệ tối ưu (1 − 1/e) ≈ 63%. Tuy nhiên, thuật toán này đòi hỏi phải tính lại hàm lan 1Hàm argmax trả về các tập hạt giống tối ưu, S∗ là một tập trong số đó. 31 truyền ảnh hưởng σ(S0) nhiều lần, mà việc tính σ(S0) lại là vấn đề #P-khó. Để giải quyết vấn đề này, Wei Chen, 2014, [60] đã sử dụng phương pháp mô phỏng Monte Carlo quá trình lan truyền thông tin, từ đó ước lượng giá trị hàm lan truyền ảnh hưởng σ(S0). Với mỗi tập hạt giống S0, ta có thể mô phỏng quá trình lan truyền thông tin ngẫu nhiên R lần. Mỗi lần ta tính số đỉnh ở trạng thái kích hoạt khi quá trình lan truyền thông tin kết thúc, sau đó tính tổng trung bình trên R lần mô phỏng. Khi số lần mô phỏng R càng lớn thì ước lượng hàm σ(S0) có độ chính xác càng cao. Một nhược điểm của thuật toán tham lam (sử dụng phương pháp mô phỏng Monte Carlo) đó là không hiệu quả về mặt thời gian thực thi đối với những đồ thị có số đỉnh lớn. Để giải quyết vấn đề này, một loạt những nghiên cứu đã được tiến hành nhằm tìm ra thuật toán hiệu quả cho vấn đề tối ưu hóa ảnh hưởng, chẳng hạn như thuật toán CELF được đề xuất bởi Leskovec, 2007, [63], CELF++ được đề xuất bởi Goyal, 2011, [64], tiếp sau đó là SPM, SP1M, SIMPATH, BCT, SSA/D-SSA. Bên cạnh vấn đề lan truyền thông tin, lan truyền ảnh hưởng cũng có nhiều nghiên cứu tập trung giải quyết bài toán hạn chế thông tin sai lệch lan truyền trên các MXH trực tuyến. Một số nghiên cứu tập trung vào việc nhận dạng thông tin sai lệch và tin đồn (Rumor) dựa trên đặc trưng ngôn ngữ, cấu trúc, thời gian như nghiên cứu của Qazvinian, 2011, [6] và Kwwon, 2013, [7]. Một số khác, nghiên cứu vấn đề xác định tập đỉnh là nguồn phát thông tin sai lệch ban đầu. Chẳng hạn, Dung T. Nguyen và các cộng sự, 2012, [65] đã nghiên cứu bài toán xác định k nguồn phát tán thông tin sai lệch khả nghi nhất từ tập người dùng bị kích hoạt bởi thông tin sai lệch cho trước và chứng minh bài toán thuộc lớp NP-khó xét trên mô hình lan truyền IC, đồng thời tác giả đã đề xuất hai thuật toán dựa trên cách tiếp cận xếp hạng (Ranking) và cách tiếp cận xấp xỉ đạt tỉ lệ tối ưu (1 − 1/e − ). Bên cạnh đó, một số tác giả đề xuất giải pháp hạn chế sự lan truyền thông tin sai lệch trên mạng xã hội bằng cách chọn ra một số đỉnh ban đầu để tiêm thông tin tốt, từ đó lan truyền những thông tin này trên cùng mạng nhằm thuyết phục những người dùng khác tin theo, trong đó sử dụng các mô hình lan truyền thông tin khác nhau [2–4]. 32 Trong [2], Budak và các cộng sự, 2011, đã đưa ra mô hình tầng độc lập đa chiến dịch (Multi-Campaign Independent Cascade Model), gồm chiến dịch phổ biến thông tin sai lệch và chiến dịch phổ biến thông tin tốt cùng cạnh tranh với nhau. Budak giả sử rằng nếu cả thông tin sai lệch và thông tin tốt cùng kích hoạt một đỉnh thì đỉnh đó sẽ được ưu tiên kích hoạt bởi thông tin tốt. Bài toán đặt ra là với ngân sách giới hạn k cho trước, cần tìm tập đỉnh kích thước k để tiêm thông tin tốt, từ đó lan truyền thông tin này trên MXH nhằm cực tiểu hóa số đỉnh bị kích hoạt bởi thông tin sai lệch. Budak đã chứng minh bài toán thuộc lớp NP-khó và đề xuất thuật toán tham lam đạt tỉ lệ tối ưu 1 − 1/e dựa trên thuộc tính submodular của hàm mục tiêu. Trong [3], H. Zhang và các cộng sự, 2015, đã nghiên cứu bài toán hạn chế sự lan truyền thông tin sai lệch dưới mô hình kích hoạt cạnh tranh (Competitive Activation Model). Trong đó, mỗi đỉnh v ∈ V có thể phơi bày cả thông tin tốt và thông tin sai lệch, đồng thời v có hai ngưỡng kích hoạt thông tin tốt A và thông A B A B tin sai lệch B tương ứng là θv và θv . Gọi I0 và I0 tương ứng là tập đỉnh kích hoạt thông tin tốt và thông tin sai lệch ban đầu. Tại thời điểm t, đỉnh v bị kích hoạt P A A bởi thông tin tốt nếu A w ≥ θ hoặc bị kích hoạt bởi thông tin sai lệch u∈It−1 uv v P B B nếu B w ≥ θ . Nếu cả hai ngưỡng đều thỏa mãn, v được coi là bị kích hoạt u∈It−1 uv v A B i P i i bởi thông tin tốt nếu P ≥ P và ngược lại, trong đó P = ( in w )/θ , v v v u∈Na (v) uv v với i ∈ {A, B}. Sau khi đỉnh v bị kích hoạt, nó sẽ giữ nguyên trạng thái cho đến khi quá trình lan truyền thông tin kết thúc. Bài toán đặt ra là với tập các đỉnh B phát thông tin sai lệch I0 ban đầu và số kA cho trước, hãy xác định tập các đỉnh A A nguồn phát thông tin tốt I0 , với |I0 | = kA sao cho cực tiểu hóa số đỉnh bị kích hoạt bởi thông tin sai lệch và cực đại hóa số đỉnh bị kích hoạt bởi thông tin tốt. H. Zhang đã chứng minh đây là bài toán thuộc lớp NP-đầy đủ đồng thời đề xuất thuật toán hiệu quả dựa trên việc xác định những đỉnh quan trọng đóng vai trò là đỉnh nguồn phát thông tin tốt. Trong [4], N. P. Nguyen và các cộng sự, 2013, đã nghiên cứu bài toán hạn chế thông tin sai lệch dưới hai mô hình IC và mô hình LT, đồng thời đề xuất thuật toán xác định một tập nhỏ nhất các đỉnh có ảnh hưởng lớn nhất, từ đó lan truyền những thông tin tốt nhằm hạn chế ảnh hưởng của thông tin sai lệch. Điểm khác biệt trong nghiên cứu của N. P. Nguyen so với nghiên cứu của Budak [3] đó là: Budak đã giới hạn kích thước của tập các đỉnh được lựa chọn để phổ biến thông tin tốt bởi ngân sách k cho trước, đồng thời Budak đã giả sử thông tin tốt có sự 33 ưu tiên kích hoạt hơn so với thông tin sai lệch khi cùng với tới một đỉnh. Ngoài ra, trong nghiên cứu của N. P. Nguyen còn mở rộng hơn đó là xét cả hai trường hợp, tập các đỉnh phát thông tin sai lệch ban đầu có thể biết trước hoặc chưa biết trước. Liên quan gần nhất đến vấn đề nghiên cứu trong luận văn của tác giả đó là công trình nghiên cứu của H. Zhang và các cộng sự, 2016, [1]. Trong nghiên cứu của mình, H. Zhang đề xuất hai bài toán: - Bài toán phát hiện thông tin sai lệch (Misinformation Detection): Giả sử không biết trước nguồn phát thông tin sai lệch (xác suất các đỉnh trở thành nguồn phát thông tin sai lệch là như nhau), yêu cầu xác định k vị trí đặt giám sát (Monitor) trên MXH sao cho cực đại hóa xác suất phát hiện thông tin sai lệch. H. Zhang đã chứng minh bài toán này tương đương với bài toán cực đại hóa ảnh hưởng theo Định nghĩa 2.1 trong đồ thị đảo ngược (đảo chiều mỗi cạnh). - Bài toán đặt giám sát (τ-Monitor Placement): Giả sử biết trước nguồn phát thông tin sai lệch là tập các đỉnh S, r là đỉnh ta cần bảo vệ. Yêu cầu, tìm ra tập đỉnh có kích thước nhỏ nhất để đặt giám sát (sử dụng bộ lọc nội dung nhằm phát hiện thông tin sai lệch ở người dùng (đỉnh) được cài đặt và ngăn chặn sự chia sẻ, lan truyền thông tin sai lệch từ đỉnh này đến những đỉnh láng giềng. Việc đặt giám sát ở một đỉnh tương đương với việc loại bỏ đỉnh này và các cạnh kề với nó khỏi đồ thị ban đầu) sao cho xác suất thông tin sai lệch kích hoạt thành công đỉnh r nhỏ hơn ngưỡng τ cho trước (0 ≤ τ ≤ 1). H. Zhang đã chứng minh bài toán này thuộc lớp #P-khó trên mô hình IC và đề xuất thuật toán tham lam dựa trên định nghĩa cut − set2. Sau đó mở rộng bài toán này cho một nhóm đỉnh cần bảo vệ. 34 Chương 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 Chương này tập trung vào việc xây dựng bài toán Cực tiểu hóa thiệt hại do thông tin sai lệch gây ra - MDM, chứng minh bài toán thuộc lớp bài toán NP-khó, đồng thời đề xuất hai thuật toán tham lam nhằm giải quyết bài toán. 3.1 Phát biểu bài toán Tác giả nghiên cứu vấn đề ngăn chặn sự lan truyền của thông tin sai lệch xét trên mô hình lan truyền thông tin LT. Như đã đề cập trong chương trước, mô hình LT mô tả việc một cá nhân thay đổi hành vi của mình khi chịu sự tác động độc lập của nhiều cá nhân khác trên MXH. Chẳng hạn, với một thông tin sai lệch mới đăng tải trên một trang MXH, ban đầu một người bất kỳ chưa thực sự tin tưởng vào thông tin sai lệch đó. Tuy nhiên, khi thấy nhiều bạn bè, người thân của họ đều chấp nhận và đăng tải, chia sẻ lại những thông tin đó trên trang cá nhân của mình, điều này có thể sẽ khiến họ thay đổi quan điểm, tin theo và tiếp tục chia sẻ thông tin sai lệch nhận được cho những người khác. Cứ như vậy, thông tin sai lệch lan truyền rộng rãi trên MXH. Trong một số trường hợp, ta có thể biết trước nguồn phát tán thông tin sai lệch trên MXH. Ví dụ, bằng các biện pháp nghiệp vụ điều tra, có thể xác định được chính xác các tài khoản Facebook của những đối tượng cơ hội chính trị là nguồn phát tán những thông tin sai lệch; hoặc các bài viết không chính xác, "thổi phồng", phóng đại đặc tính của một sản phẩm khả năng cao đến từ những người tiếp thị cho sản phẩm đó. Một số nghiên cứu về xác định vị trí nguồn phát thông tin có thể kể đến như nghiên cứu của Prakash, 2012, [5]; Shah và Zaman, 2011, [8]; Zhu và Ying, 2014, [11]; Luo, 2013, [12]. Trong luận văn, tác giả xem xét bài toán trong trường hợp đã biết trước nguồn lan truyền thông tin sai lệch ban đầu. Quá trình phát tán thông tin từ tập nguồn S biết trước tới các đỉnh khác 35 trong MXH phát triển theo từng bước thời gian rời rạc t = 0, 1, 2, ... Mỗi đỉnh u ∈ V có thể ở một trong hai trạng thái kích hoạt (active) hoặc không kích hoạt (inactive) với thông tin sai lệch. Tại mỗi bước t, đỉnh u ở trạng thái kích hoạt nếu u là đỉnh nguồn phát thông tin sai lệch S (đỉnh khởi tạo quá trình lan truyền thông tin sai lệch) hoặc u nhận được thông tin sai lệch từ các đỉnh hàng xóm ở trạng thái kích hoạt và chấp nhận thông tin này để tiếp tục chia sẻ, lan truyền những thông tin đó đến những đỉnh khác trong các bước tiếp theo, ngược lại, u ở trạng thái không kích hoạt. Trong luận văn, tác giả quan tâm tới vấn đề ngăn chặn thông tin sai lệch lan truyền trong d bước thời gian (deadline d), vì nếu không ngăn chặn sớm số người dùng bị kích hoạt sẽ tăng lên rất nhanh do tốc độ lan truyền nhanh chóng của thông tin sai lệch. Mặt khác, trong nhiều trường hợp đặt ra vấn đề phải ngăn chặn sự lan truyền của thông tin sai lệch trước một khoảng thời gian xác định. Ví dụ, trước kỳ các sự kiện chính trị trọng đại của một quốc gia, các tổ chức, cá nhân thù địch thường xuyên đăng tải những quan điểm sai trái, thù địch trên mạng xã hội với mục đích phá hoại sự thành công các sự kiện đó. Do vậy, cần phải ngăn chặn sớm những thông tin đó lan truyền trên mạng góp phần đảm bảo sự thành công của các sự kiện chính trị quan trọng. Vì những lý do nêu trên, tác giả đặt ràng buộc cho bài toán của mình là ngăn chặn thông tin sai lệch lan truyền trong khoảng thời gian giới hạn là d bước lan truyền, d ∈ Z+. Toàn bộ các hoạt động của người dùng trên MXH trực tuyến như đăng bài, bình luận, chia sẻ vv.. đều được thu thập (Capture) và phân tích, từ đó thông tin sai lệch có thể được phát hiện một cách tự động. Các kỹ thuật này được đề cập trong các công trình nghiên cứu của Qazvinian, 2011, [9] và Kwon, 2013, [10]. Sau khi thông tin sai lệch được phát hiện, các bộ lọc nội dung sẽ giúp ngăn chặn hay vô hiệu hóa việc người dùng lan truyền những thông tin đó đến bạn bè của họ. Tác giả đề cập đến các kỹ thuật này như là việc tạo miễn dịch (Immunize) hay đặt giám sát (Monitor) cho các đỉnh trong đồ thị MXH (về sau, tác giả sử dụng thuật ngữ tạo miễn dịch để chỉ chung phương pháp này). Trong ngữ cảnh khác, kỹ thuật tạo miễn dịch còn có thể hiểu là việc thuyết phục một người dùng nào đó trên MXH không chấp nhận và lan truyền những thông tin sai lệch đến những người dùng khác. Như vậy, việc tạo miễn dịch cho một đỉnh tương đương với việc loại bỏ đỉnh này và những cạnh kề với nó khỏi đồ thị ban đầu. Do đặc tính của mỗi người dùng là khác nhau trong một MXH, nên chi phí 36 bỏ ra để tạo miễn dịch đối với những người dùng đó cũng khác nhau. Với tính quy mô lớn của các MXH trực tuyến, sẽ là quá đắt để tạo miễn dịch cho toàn bộ người dùng trên mạng. Giải pháp thiệt thực hơn đó là chọn ra một số người dùng để tạo miễn dịch sao cho có thể hạn chế tối đa số đỉnh bị kích hoạt bởi thông tin sai lệch. Như vậy, cần tìm một chiến lược tối ưu nhằm chọn ra những đỉnh để tạo miễn dịch với thông tin sai lệch. Mô hình hóa bài toán Mỗi mạng xã hội được biểu diễn bởi một đồ thị có hướng G = (V, E), trong đó V là tập đỉnh và E ⊆ V × V là tập cạnh, |V | = n, |E| = m. Mỗi đỉnh trong tập V tương ứng với một người dùng trong mạng xã hội, mỗi cạnh có hướng e = (u, v) trong tập E biểu diễn mối quan hệ giữa người dùng u và người dùng v tương ứng. Trong bài toán này, tác giả giả thuyết đã xác định được nguồn phát thông tin sai lệch ban đầu là tập các đỉnh S ⊂ V , S = {s1, s2, ..., sp} và ta không can thiệp trực tiếp được vào tập nguồn S nhưng có thể tạo miễn dịch (hay bố trí các máy giám sát) ở các đỉnh khác để hạn chế sự lan truyền thông tin. Phương pháp đặt giám sát cũng đã được Zhang [1] đề xuất sử dụng để ngăn chặn thông tin sai lệch truyền từ nguồn cho trước tới một đỉnh cần bảo vệ. Mỗi đỉnh u ∈ V có một chi phí c(u) ≥ 0 để tạo miễn dịch với thông tin sai lệch, đồng thời đỉnh u khi bị thông tin sai lệch kích hoạt, tức là người dùng tương ứng tin vào thông tin này sẽ gây ra thiệt hại được lượng hóa bởi đại lượng r(u) ≥ 0. Vì khó ước lượng thiệt hại cho mỗi đỉnh nên trong bài toán này ta xem thiệt hại của mỗi đỉnh kích hoạt gây ra như nhau. Không mất tính tổng quát ta giả thiết r(u) = 1 với mọi đỉnh u là đỉnh kích hoạt. Như vậy, với trường hợp r(u) = 1, tổng thiệt hại do thông tin sai lệch gây ra chính bằng tổng số đỉnh ở trạng thái kích hoạt sau khi quá trình lan truyền thông tin kết thúc. Tuy nhiên, về sau ta vẫn dùng thuật ngữ thiệt hại để chỉ chung hai đại lượng này. Như trình bày trong Chương 2, Chen [60, 61] đã chỉ ra mô hình LT là tương đương với mô hình đồ thị mẫu. Bây giờ, ta sẽ sử dụng mô hình đồ thị mẫu để phân tích bài toán đặt ra. Gọi G là tập hợp tất cả các đồ thị mẫu sinh ra từ đồ thị G = (V, E), P r(GL) 37 là xác suất lựa chọn (xác suất sinh) đồ thị mẫu GL = (V, EGL ) từ tập G, ta có: Y P r(GL) = p(v) (3.1) v∈V Trong đó  w(u, v) nếu ∃u :(u, v) ∈ EG p(v) = L  P 1 − u∈N in(v) w(u, v) ngược lại Ký hiệu σ(S) là kỳ vọng số đỉnh kích hoạt gây ra bởi nguồn thông tin sai lệch S khi kết thúc quá trình lan truyền và R(GL,S) là tập hợp các đỉnh có thể đi đến từ tập S trong đồ thị GL, khi đó σ(S) được xác định bởi công thức sau: X σ(S) = P r(GL)|R(GL,S)| (3.2) GL∈G Ký hiệu D(S) là kỳ vọng thiệt hại tích hợp từ các đỉnh kích hoạt trong quá trình lan truyền gây bởi tập nguồn thông tin sai lệch S, như vậy D(S) tỉ lệ với σ(S). Do mỗi đỉnh u ∈ V khi bị kích hoạt gây ra thiệt hại r(u) = 1, cho nên D(S) trùng với kỳ vọng số đỉnh kích hoạt σ(S), tức là: X D(S) = σ(S) = P r(GL)|R(GL,S)| (3.3) GL∈G Ký hiệu Rd(GL,S) là tập hợp các đỉnh có thể đi đến từ S trong đồ thị GL sau d bước lan truyền hay d bước thời gian. Gọi dGL (S, v) là khoảng cách ngắn nhất trong số tất cả các đường đi từ tập S đến đỉnh v trong đồ thị GL (nếu không tồn tại đường đi từ S đến v thì dGL (S, v) = ∞, nếu v ∈ S thì dGL (S, v) = 0). Đại lượng dGL (S, v) cũng được gọi là khoảng cách từ tập S đến đỉnh v trong đồ thị GL. Khi đó ta có: Rd(GL,S) = {v ∈ V | dGL (S, v) ≤ d} (3.4) S Khi đó từ Công thức 3.3 ta xác định được thiệt hại Dd do nguồn thông tin sai lệch S gây ra sau d bước lan truyền như sau: S X Dd = P r(GL)|Rd(GL,S)| (3.5) GL∈G Ta sẽ xét bài toán tìm tập đỉnh I để tạo miễn dịch sao cho chi phí tạo miễn dịch không vượt quá ngân sách B cho trước và có thiệt hại sau d bước lan truyền thông tin sai lệch nhỏ nhất. Gọi G(I) là đồ thị con của G sau khi loại bỏ tập đỉnh I và tập các cạnh kề với I. Khi đó, thiệt hại gây bởi nguồn thông tin sai lệch S trên đồ thị G sau khi tạo 38 miễn dịch cho tập đỉnh I chính bằng thiệt hại gây bởi nguồn thông tin sai lệch S trên đồ thị G(I). Ta dùng ký hiệu G(I) là tập hợp tất cả các đồ thị mẫu sinh ra từ đồ thị G(I) S và Dd (I) là hàm thiệt hại gây bởi nguồn S sau d bước lan truyền khi đã tạo miễn dịch cho tập đỉnh I. Khi đó từ Công thức 3.5 ta có: S X Dd (I) = P r(GL)|Rd(GL,S)| (3.6) GL∈G(I) Với quá trình lan truyền thông tin sai lệch theo mô hình LT, bài toán Cực tiểu hóa thiệt hai do thông tin sai lệch gây ra (Minimize Damage of Misinformation- MDM ) trên MXH trực tuyến được phát biểu như sau: Định nghĩa 3.1 (Bài toán Cực tiểu hóa thiệt hại-MDM) Cho đồ thị G = (V, E) biểu diễn một MXH cùng với mô hình lan truyền LT. S ⊂ V là tập nguồn thông tin sai lệch. Mỗi đỉnh u ∈ V có một chi phí c(u) ≥ 0 để tạo miễn dịch với thông tin sai lệch và thiệt hại r(u) = 1 khi bị thông tin sai lệch kích hoạt. Với nguồn ngân sách giới hạn B > 0 và số bước lan truyền thông tin d ∈ Z+ cho trước, mục tiêu của bài toán là tìm tập đỉnh cần tạo miễn dịch I ⊂ V \S với tổng P S chi phí không vượt quá B, u∈I c(u) ≤ B, nhằm cực tiểu hóa hàm Dd (I). Bài toán MDM được viết gọn như sau: Tìm tập I ⊂ V \S làm cực tiểu hóa hàm S P Dd (I) với điều kiện u∈I c(u) ≤ B. Điểm khác nhau giữa nghiên cứu của tác giả với nghiên cứu của H. Zhang, 2016, [1] đó là: - H. Zhang xét bài toán trong trường hợp mỗi đỉnh u ∈ V có chi phí đặt giám sát như nhau. Trong bài toán MDM, tác giả mở rộng hơn với chi phí c(u) ≥ 0 khác nhau cho mỗi đỉnh. - H. Zhang nghiên cứu bài toán ngăn chặn thông tin sai lệch đến với 1 đỉnh hoặc một nhóm đỉnh cần bảo vệ. Trong bài toán MDM xét với tất cả các đỉnh trong toàn mạng cần bảo vệ, đồng thời có yếu tố ràng buộc về thời gian d. - H. Zhang nghiên cứu bài toán trên mô hình lan truyền thông tin IC, còn trong bài toán MDM, tác giả xét trên mô hình lan truyền thông tin LT. 39 3.2 Độ khó của bài toán Trong mục này, tác giả chỉ ra rằng bài toán MDM thuộc lớp bài toán NP-khó bằng cách dẫn nó từ bài toán Tập phủ dạng 0 − 1 (hay phiên bản quyết định của bài toán Tập phủ) được định nghĩa như dưới đây. Bài toán Tập phủ dạng 0 − 1: Cho tập vũ trụ U gồm m phần tử, U = {e1, e2, ..., em}, tập S gồm n phần tử là các tập con của U, S = {S1,S2, ..., Sn}, sao S cho i Si = U. Cho trước số tự nhiên k ≤ n, có tồn tại hay không một tập con 0 S S ⊆ S kích thước nhỏ hơn hoặc bằng k, sao cho 0 S = U. Si∈S i Định lý 3.1 MDM là bài toán NP-khó. Chứng minh. Để chứng minh MDM thuộc lớp bài bài toán NP-khó, đầu tiên ta xây dựng phép dẫn (Reduce) từ một bài toán NP-đầy đủ đã biết đó là bài toán Tập phủ dạng 0 − 1 (0 − 1 Set Cover problem) [66]. Tiếp theo, ta chỉ ra sự tương đương giữa hai thể hiện của bài toán MDM và bài toán Tập phủ dạng 0 − 1. Xét phiên bản quyết định của bài toán MDM: Cho đồ thị G = (V, E) biểu diễn một mạng xã hội cùng với mô hình lan truyền LT. S ⊂ V là tập nguồn thông tin sai lệch. Mỗi đỉnh u ∈ V có một chi phí c(u) ≥ 0 để tạo miễn dịch với thông tin sai lệch và thiệt hại r(u) = 1 khi bị thông tin sai lệch kích hoạt. Với nguồn ngân sách giới hạn B > 0 và số bước lan truyền thông tin d ∈ Z+ cho trước, có tồn P tại hay không tập đỉnh cần tạo miễn dịch I ⊂ V \S với u∈I c(u) ≤ B sao cho S Dd (I) ≤ t, trong đó t là số tự nhiên. Xây dựng phép dẫn từ bài toán Tập phủ dạng 0−1 đến bài toán MDM: Cho một thể hiện của bài toán Tập phủ dạng 0−1 là ISC = {U, S, k}, ta xây dựng một thể hiện của bài toán MDM là IMDM = {G, w(u, v), θv, S, c(u), r(u), d, B, t} (Hình 3.1) như sau: • Ứng với mỗi tập Si ∈ S ta xây dựng một đỉnh nguồn thông tin sai lệch si ∈ S và một đỉnh ui, nối hai đỉnh này bằng một cạnh có hướng (si, ui) với trọng số w(si, ui) = 1, ngưỡng kích hoạt θui = 1. • Ứng với mỗi phần tử ej ∈ U ta xây dựng một đỉnh vj. Nếu ej ∈ Si, ta xây 1 dựng một cạnh có hướng (ui, vj) với trọng số w(ui, vj) = , trong đó d+(vj ) d+(vj) là bậc đi đến của đỉnh vj, ngưỡng kích hoạt θvj = 1. • Thiệt hại của mỗi đỉnh khi bị kích hoạt bởi thông tin sai lệch r(ui) = r(vj) = 1 (i = 1..n, j = 1..m). 40 • Chi phí tạo miễn dịch trên mỗi đỉnh c(u1) = c(u2) = ... = c(un) = 1, c(v1) = c(v2) = ... = c(vm) = +∞. 6 • Cuối cùng, đặt B = k, d = 2, t = n − k. HìnhHình 3.1: 1: Phép Thuật dẫn toán từ bài dẫn toán từ Tập bài phủ toán dạng Tập0 − phủ1 đến đến bàiMDM toán .MDM Dễ thấy rằng phép dẫn này thực hiện trong thời gian đa thức theo n. Qua phép dẫn trên ta sẽ chứng minh bài toán Tập phủ tương đương với bài Qua phép dẫn xây dựng ở trên, ta sẽ chứng minh hai thể hiện ISC = {U, S, k} toán có tồn tại hay không một tập giám sát A sao cho thiệt hai của tập S gây và IMDM = {G, w(u, v), θv, S, c(u), r(u), d, B, t} là tương đương với nhau. S ra Dd (APhần) ≤ n − thuận:k và ngượcNếu bài lại. toán Tập phủ dạng 0 − 1 có lời giải thì bài toán MDM Giảcũng sử bài có lời toán giải Tập tương phủ ứng. có lời giải là S0 với |S0| ≤ k. Ta chọn các tập tập giám 0 0 0 sát là AGiả= {u sửi|S thểi ∈ hiện S },I lúcSC có này lời tất giải cả là các tập S đỉnhvớiv|Sj, j| ≤=k 1và..m nóđều có thểkề với phủ ít toàn nhất bộ một các phân tử của tập U. Bằng phép dẫn ở trên,P chọn tập đỉnh để tạo miễn dịch là đỉnh ui ∈ A, do đó sau thời gian d ta có: a w(ui, vj) < 1 = θv , j = 1..m có 0 N (vj ) 0 j I = {u | S ∈ S }. Khi đó, ta có P c(u ) ≤ k = B. Do S phủ tất cả các phần i i ui∈I i nghĩa là không có đỉnh nào được kích hoạt. Các đỉnh ui ∈/ A không được chọn là tử tập U nên mọi đỉnh vj (j = 1..m) đều kề với ít nhất một đỉnh ui ∈ I. Như vậy S giám sát nên sẽ bị kích hoạt bởi S, doP đó thiệt hại sẽ là Dd (A) = n − k. khi tạo miễn dịch trên tập I ta có: in w(ui, vj) < 1 = θvj , suy ra không ui∈Nactive(vj ) S Ngượccó bất lại, kỳ ta đỉnh giảvj sửnào bài được toán kíchMDM hoạt.có Các lời đỉnh giảiu lài ∈/AI saovà kề cho trựcD tiếpd (A) với≤ cácn − k. S Ta thấyđỉnh rằng thuộc tập tậpASchỉsẽ bị có thông thể bao tin sai gồm lệch các kích phần hoạt, tử doui đómàDd không(I) = n − thểk. chứa một Phần nghịch. Nếu bài toán MDM có lờiS giải thì bài toán Tập phủ dạng 0 − 1 trong các đỉnh vj do c(vj) = +∞ > C. Do Dd (A) ≤ n − k và các đỉnh được thuộc cũng có lời giải tương ứng. A đều không bị kích hoạt nên số đỉnh thuộc tập {vj, j = 1..m} bằng m điều này Giả sử thể hiện IMDM có lời giải là tập đỉnh cần tạo miễn dịch I ⊂ V \S với có nghĩaP là mỗi đỉnh trong tậpS này kề với ít nhất một đỉnh ui ∈ A. Trong bài u∈I c(u) = B = k sao cho Dd (I) ≤ n − k. Bằng phép dẫn ở trên, ta xác định toán Tập phủ,0 ta chọn S0 = {S |u ∈ A} thì0 đây chính là lời giải của bài toán này. tập S = {Si | ui ∈ I}. Khi đó,i i ta có |S | = k. Do c(vj) = +∞ > B (j = 1..m) nên Địnhkhông lý được thể chứngtạo miễn minh dịch hoàntrên toàn! các đỉnh vj (j = 1..m), như vậy tập I chỉ có thể Tài liệu [1] H. Zhang, M. Alim, X. Li, M. T. Thai, and H. Nguyen, Misinformation in Online Social Networks: Catch Them All with Limited Budget, ACM Trans- actions on Information Systems (TOIS) 2016. 41 S bao gồm các đỉnh ui (i = 1..n). Ngoài ra, Dd (I) ≤ n − k nên chứng tỏ mọi đỉnh vj (j = 1..m) đều không bị thông tin sai lệch kích hoạt, suy ra mỗi đỉnh vj đều kề 0 với ít nhất một đỉnh ui ∈ I hay tập S phủ toàn bộ các phần tử của tập U. Định lý được chứng minh hoàn toàn! 3.3 Các thuật toán đề xuất giải quyết bài toán MDM Đối với các bài toán dạng lan truyền thông tin, người ta có thể dùng các thuật toán cơ sở Max Degree và thuật toán Random để tìm lời giải “đủ tốt”. Hai thuật toán cơ sở này thường được sử dụng để kiểm định tính hiệu quả khi so sánh với các thuật toán mới đề xuất [1,4,47,55]. Ký hiệu Nk(S) là tập hợp các đỉnh có khoảng cách không quá k tính từ tập nguồn phát thông tin sai lệch S trong đồ thị G. Khi k = 1, Nk(S) là tập đỉnh hàng xóm đi ra từ S. Để ngăn chặn thông tin sai lệch lan truyền sau d bước thời gian thì các đỉnh được lựa chọn để tạo miễn dịch cũng phải nằm trong tập Nd(S) với d ∈ Z+. Trong mục này, tác giả đề xuất hai thuật toán tham lam cho bài toán MDM, thuật toán thứ nhất dựa trên đặc tính hàm số f(I) (cho bởi Công thức 3.7) đo độ giảm thiệt hại sau khi chọn tập đỉnh I để tạo miễn dịch, thuật toán hai sử dụng hàm số α(v) (cho bởi Công thức 3.8) đo độ tăng của hàm f(I) tính trên một đơn vị chi phí khi thêm một đỉnh mới v vào tập I. Hàm giảm thiệt hại. Với mỗi tập I ⊂ Nd(S), ta định nghĩa hàm giảm thiệt hại f(I) thức sau: S S S S f(I) = Dd (∅) − Dd (I) = Dd − Dd (I) (3.7) S S trong đó ngầm định Dd (∅) = Dd . Hàm tăng giá trị của f(I) trên một đơn vị chi phí. Với mỗi tập I đã cho, hàm α(v) đo độ tăng giá trị hàm f(I) khi thêm một đỉnh v ∈ Nd(S) vào tập I xác định như sau: (f(I ∪ {v}) − f(I)) α(v) = (3.8) c(v) 3.3.1 Thuật toán tham lam dựa trên hàm f(I) Mục tiêu của bài toán MDM là cực tiểu hóa tổng thiệt do thông tin sai lệch S gây ra, tức là cực tiểu hóa hàm Dd (I) hoặc hiểu theo cách khác là cực đại hóa độ giảm thiệt hại, tức là cực đại hóa hàm f(I). Như vậy, ta có thể sử dụng f(I) 42 như là một hàm mục tiêu thay thế trong bài toán MDM, thuật toán tác giả đề xuất hoạt động dựa trên việc bổ sung dần tập I theo kiểu ăn tham. Ý tưởng thuật toán: Khởi tạo I = ∅, tiếp theo thực hiện lặp việc chọn đỉnh v ∈ Nd(S) sao cho hàm f(I ∪ {v}) đạt giá trị lớn nhất, nếu tổng chi phí hiện tại để tạo miễn dịch chưa vượt ngưỡng ngân sách B thì bổ sung v vào I, ngược lại thì dừng và trả về kết quả tập I. Quá trình này kết thúc khi tổng chi phí để tạo miễn dịch cho tập đỉnh I vượt ngưỡng ngân sách B đã cho hoặc đã xét hết tất cả các đỉnh trong tập Nd(S). Chi tiết thuật toán được đặc tả trong phần giả mã của Thuật toán 5. Algorithm 1: Thuật toán tham lam dựa trên hàm f(I) Input : G = (V, E), w(u, v), d, B, tập nguồn phát thông tin sai lệch S. Output: Tập đỉnh I là lời giải của bài toán MDM. 1 begin 2 I ← ∅; 3 N ← Nd(S); 4 C ← 0; 5 while (C < B) and (N 6= ∅) do 6 u ← argmaxv∈N f(I ∪ {v}); //Chọn ra đỉnh v sao cho f(I ∪ {v}) đạt giá trị lớn nhất 7 if C + c(u) ≤ B then 8 I ← I ∪ {u}; 9 C ← C + c(u); 10 end 11 N ← N\{u}; 12 end 13 Return I; 14 end 2 Dễ thấy rằng, trong trường hợp xấu nhất, Thuật toán 5 thực hiện tối đa n1 vòng lặp việc tính lại giá trị hàm f(I), với n1 = |Nd(S)|, tuy nhiên theo Công thức 3.7, để tính được giá trị hàm f(I) ta cần tính toán được kỳ vọng số đỉnh bị thông tin sai lệch kích hoạt sau d bước lan truyền. Việc tính toán chính xác giá trị kỳ vọng số đỉnh bị kích hoạt là vấn đề #P-khó [21,60]. Để giải quyết vấn đề này, Wei Chen [21,60] đã sử dụng phương pháp mô phỏng Monte Carlo quá trình lan truyền thông tin, từ đó ước lượng giá trị kỳ vọng số đỉnh bị kích hoạt. Ước S lượng giá trị hàm Dd (I) bằng pháp mô phỏng Mote Carlo quá trình lan truyền thông tin được trình bày trong Thuật toán 2. Với mỗi tập hạt giống S, tiến hành mô phỏng quá trình lan truyền thông tin ngẫu nhiên R lần. Mỗi lần, tính số đỉnh ở trạng thái kích hoạt sau d bước lan truyền, sau đó tính tổng trung bình trên R lần mô phỏng. Khi số lần mô phỏng R càng lớn thì ước lượng giá trị kỳ vọng số đỉnh bị kích hoạt có độ chính xác càng cao. 43 S Algorithm 2: Thuật toán ước lượng giá trị hàm Dd (I) Input : G = (V, E), w(u, v), tập nguồn phát thông tin sai lệch S, tập đỉnh I tạo miễn dịch. S Output: Giá trị ước lượng hàm Dd (I). 1 begin 2 Đồ thị G(I) thu được sau khi loại bỏ tập đỉnh I từ đồ thị G; 3 count ← 0; 4 for j = 1 to R do 5 mô phỏng quá trình lan truyền thông tin trên đồ thị G(I) từ tập nguồn S; 6 na ← số đỉnh kích hoạt sau d bước lan truyền; 7 count ← count + na; 8 end 9 Return count/R; 10 end Như vậy, trong trường hợp xấu nhất, Thuật toán 1 có độ phức tạp tính toán 2 là O(n1R), với n1 = |Nd(S)|, R là số lần mô phỏng. 3.3.2 Thuật toán tham lam dựa trên hàm α(v) Trong mục trước, Thuật toán 1 dựa trên ý tưởng chọn ra những đỉnh thu được độ giảm thiệt hại lớn nhất để thêm vào tập đỉnh cần tạo miễn dịch, tuy nhiên, trong mục này tác giả đề xuất thuật toán khác dựa trên ý tưởng lựa chọn ra những đỉnh thu được lợi nhuận lớn nhất nhưng xét đến yếu tố chi phí bỏ ra. Ý tưởng thuật toán: Khởi tạo I = ∅, tiếp theo thực hiện lặp việc chọn đỉnh v ∈ Nd(S) sao cho hàm α(v) đạt giá trị lớn nhất, nếu tổng chi phí hiện tại để tạo miễn dịch chưa vượt ngưỡng ngân sách B thì bổ sung v vào I, ngược lại thì dừng và trả về kết quả tập I. Quá trình này kết thúc khi tổng chi phí để tạo miễn dịch cho tập đỉnh I vượt ngưỡng ngân sách B đã cho hoặc đã xét hết tất cả các đỉnh trong tập Nd(S). Chi tiết thuật toán được đặc tả trong phân giả mã của Thuật toán 3. Trong trường hợp xấu nhất, Thuật toán 3 cũng có độ phức tạp tính toán là 2 O(n1R), với n1 = |Nd(S)|, R là số lần mô phỏng. 44 Algorithm 3: Thuật toán tham lam dựa trên hàm α(v) Input : G = (V, E), w(u, v), d, B, tập nguồn phát thông tin sai lệch S. Output: Tập đỉnh I là lời giải của bài toán MDM. 1 begin 2 I ← ∅; 3 N ← Nd(S); 4 C ← 0; 5 while (C < B) and (N 6= ∅) do (f(I ∪ {v}) − f(I)) α(v) = , ∀v ∈ N; 6 c(v) 7 u ← argmaxv∈N α(v); //Chọn ra đỉnh v sao cho α(v) đạt giá trị lớn nhất 8 if C + c(u) ≤ B then 9 I ← I ∪ {u}; 10 C ← C + c(u); 11 end 12 N ← N\{u}; 13 end 14 Return I; 15 end 45 Chương 4 THỰC NGHIỆM Ở Chương 4 tác giả tập trung đánh giá chi tiết hiệu quả hai thuật toán đề xuất: Thuật toán 1 và Thuật toán 3, so sánh với các thu