Luận văn tốt nghiệ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

LỜI CAM ĐOAN

Tôi xin cam đoan, những kiến thức trình bày trong luận văn là do tôi tìm

hiểu, nghiên cứu và trình bày dưới sự hướng dẫn của PGS.TS Hoàng Xuân

Huấn. Trong quá trình làm luận văn, tôi đã tham khảo các tài liệu có liên quan

và đều trích dẫn nguồn đầy đủ, rõ ràng. Những kết quả mới trong luận văn là

của riêng tôi, không sao chép từ bất kỳ một công trình nào khác. Nếu có điều gì

không trung thực, tôi xin hoàn toàn chịu trách nhiệm.

Học viên

Vũ Minh Mạnh

LỜI CẢM ƠN

Trước hết, tôi xin gửi lời cảm ơn sâu sắc đến PGS.TS Hoàng Xuân Huấn,

người thầy đã giành nhiều thời gian để hướng dẫn, góp ý giúp tôi hoàn thành

luận văn này. Thầy luôn truyền cho tôi cảm hứng, nhiệt huyết nghiên cứu khoa

học, động viên và cho tôi nhiều lời khuyên quý báu.

Tôi cũng xin bày tỏ lòng biết ơn chân thành tới các thầy, cô giáo đã giảng dạy

tôi trong suốt 2 năm học tại Trường Đại học Công nghệ - Đại học Quốc gia Hà

Nội. Mỗi thầy cô đều cho tôi những bài giảng thật hay và bổ ích.

Tôi cũng xin gửi lời cảm ơn tới Ban giám đốc Học viện An ninh nhân dân,

Lãnh đạo Khoa Công nghệ và An ninh thông tin cùng các anh chị đồng nghiệp

đã tạo mọi điều kiện thuận lợi giúp tôi tham gia và hoàn thành khóa học.

Cuối cùng, tôi xin gửi lời biết ơn đến bố mẹ, anh chị trong gia đình, bạn bè,

người thân đã luôn ủng hộ, động viên tôi vượt qua những khó khăn trong cuộc

sống, để tôi có thể theo đuổi ước mơ và hoài bão của mình.

Học viên

Vũ Minh Mạnh

Mục lục

MỞ ĐẦU 1

1 GIỚI THIỆU VỀ MẠNG XÃ HỘI 5

1.1 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 IC LT MDM

Independent Cascade Linear Threshold Minimize Damage of Misinforma- tion Social Network

MXH

Thuật ngữ tiếng Việt Mô hình tầng độc lập Mô hình ngưỡng tuyến tính Bài toán cực tiểu hóa thiệt hại do thông tin sai lệch gây ra Mạng xã hội

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,

1https://www.facebook.com 2https://www.twitter.com 3https://www.instagram.com 4http://www.statista.com

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

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

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)

là ở giới trẻ trên toàn thế giới.

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ỡ,

5https://www.classmate.com 6https://www.aol.com 7https://www.sixgegrees.org 8https://www.wikipedia.org 9https://www.meetup.com

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

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

Hình 1.2: Các trang mạng xã hội trên Internet

10https://www.friendster.org 11https://www.myspace.org

bỏ ra 19 phút trên trang này mỗi ngày.

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.

12https://www.youtube.com 13https://www.pinterest.com

- Tính tương tác: Thể hiện không chỉ ở chỗ thông tin được truyền đi sau đó

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ó

Tên mạng WWW Film Actors Telephone Call Graph Email Networks Sexual Contacts Internet Peer-To-Peer Metabolic Network Protein Interactions

Số mũ α 2.3/2.7 2.3 2.1 1.5/2.0 3.2 2.5 2.1 2.2 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

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ũ α.

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 độ

Hình 1.5: Mạng đồng tác giả

kết nối lớn hơn so với các nút bên ngoài.

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 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

hệ đó ảnh hưởng thế nào đến cấu trúc của toàn MXH.

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

mà còn ứng dụng trong nhiều lĩnh vực khác nhau như truy hồi thông tin, tin

sinh học và thương mại điện tử [35]. Trong mạng sinh học như mạng tương tác

protein, mạng trao đổi chất, một liên kết chưa biết giữa hai đỉnh được chứng

minh là tồn tại bằng kiến thức lĩnh vực đó hoặc tại phòng thí nghiệm thường

có chi phí cao. Thay vào đó, việc dự đoán các liên kết dựa trên các thông tin

và các liên kết đã có rõ ràng sẽ giảm được nhiều công sức và chi phí nếu việc

dự đoán đạt được một độ chính xác đủ lớn. Hơn nữa, việc phân tích MXH cũng

gặp nhiều khó khăn khi dữ liệu bị thiếu hoặc bị mất, khi đó các thuật toán dự

đoán liên kết đóng một vai trò lớn cho bài toán phân tích MXH. Dữ liệu xây

dựng trên nền các MXH có thể chứa các thông tin không chính xác hay các liên

kết giả mạo, các thuật toán dự đoán liên kết có thể giúp phát hiện các liên kết

giả mạo này [37]. Các thuật toán dự đoán liên kết còn giúp dự đoán những mối

quan hệ có thể xuất hiện trong tương lai trong quá trình mở rộng và phát triển

của mạng. Trong MXH trực tuyến, có những liên kết chưa tồn tại nhưng có thể

được gợi ý như một mối quan hệ triển vọng, giúp người dùng tìm kiếm bạn mới

và từ đó làm tăng sự tin tưởng của người dùng với ứng dụng đó.

14https://www.amazon.com

Các nghiên cứu về dự đoán liên kết điển hình có thể kể đến là nghiên cứu

16

của Lu, 2010, [40] và Wu, 2015, [41] trình bày hai nhóm phương pháp dự đoán

liên kết theo độ đo tương tự dựa trên cấu trúc. Leskovec và Kleinberg, 2010, [39]

trong nghiên cứu của mình, đã đưa ra khái niệm liên kết âm và liên kết dương.

Trong các mối quan hệ bạn bè, người thân được coi là liên kết dương, còn các

mối quan hệ đối đầu thù địch được coi là liên kết âm. Việc nghiên cứu các liên

kết âm, liên kết dương có nhiều ứng dụng trong thực tế, ví dụ được ứng dụng trong hệ thống đánh giá sản phẩm trực tuyến trust/distrust như Epinions15 hay Slashdots16.

1.3.3 Tính riêng tư trên mạng xã hội

Một nguy cơ đối với người dùng khi sử dụng MXH là sự rò rỉ thông tin. Thông

tin bị rò rỉ ở đây có thể là các thông tin cá nhân của người dùng như: tin nhắn,

e-mail, địa chỉ, cơ quan, sở thích, bạn bè vv.. Đây là những thông tin mà kẻ xấu

có thể lợi dụng để phục vụ cho các mục đích của chúng. Chúng có thể dùng các

thông tin này để lừa đảo, gửi spam, phát tán virus vv..

Ngoài những thông tin cá nhân, người dùng còn bị lộ lọt những thông tin nội

dung bài đăng, nội dung chia sẻ, vị trí người dùng, các thông tin của tổ chức mà

người dùng đang tham gia đến những đối tượng không mong muốn chia sẻ. Do

vậy, bảo vệ tính riêng tư của người dùng trên MXH đang là một vấn đề mới và

nhận được sự quan tâm của nhiều nhà nghiên cứu trong thời gian gần đây, một

trong số đó phải kể đến nghiên cứu của T. N. Dinh [42], Y. Shen [43, 44] vv..

1.3.4 Tiến hóa động trên mạng xã hội

MXH luôn có tính động và không ngừng biến đổi theo thời gian bằng cách bổ

sung hoặc loại bỏ một nút, một liên kết trong mạng [33]. Một số thành viên mới

có thể tham gia vào mạng hoặc một số thành viên cũ có thể ngừng tham gia.

Ngoài ra, các liên kết mới được tạo ra khi các thành viên tương tác với nhau

hoặc một số liên kết cũ mất đi khi các thành viên ngừng tương tác với nhau.

Chính những điều này dẫn đến sự thay đổi cấu trúc trong toàn mạng.

Đã có nhiều nghiên cứu về phân tích MXH nhưng chỉ trong giai đoạn gần

đây, các nhà nghiên cứu mới chuyển sự chú ý đến quá trình tiến hóa của MXH.

Trong đó, nổi lên một số câu hỏi: Các luật chi phối sự tiến hóa của MXH là gì?

15http://www.epinions.com/ 16https://slashdot.org/

Mô hình nào là phù hợp để giải thích sự tiến hóa đó? Một cấu trúc cộng đồng

17

được sinh ra trong MXH như thế nào, điều gì làm cho một cộng đồng có thể thu

Hình 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

hẹp hoặc mở rộng?

Các nghiên cứu điển hình về tiến hóa động trên MXH có thể kể đến là nghiên

cứu của Leskevec [33, 45, 46], và một số nghiên cứu các các học giả khác.

1.3.5 Khai phá dữ liệu trên mạng xã hội

Sự phát triển nhanh chóng của các phương tiện truyền thông xã hội (Social

Media) cung cấp một lượng lớn dữ liệu tạo ra bởi người dùng. Theo thống kế, có

khoảng 6 tỉ bức ảnh được đăng tải lên Facebook mỗi tháng, 72 giờ video được đăng tải mỗi phút trên YouTube17, hơn 400 triệu tweet mỗi ngày trên Twitter.

Do vậy, cần phải có những kỹ thuật khai phá dữ liệu phù hợp để có thể trích

xuất ra những mẫu hữu ích từ lượng lớn dữ liệu phức tạp và thương xuyên thay

đổi trong thời gian ngắn.

Khai phá dữ liệu trên MXH có nhiều ứng dụng trong các lĩnh vực cụ thể. Đầu

tiên là ứng dụng trong các hệ tư vấn xã hội. Hệ tư vấn xã hội là hệ tư vấn nhắm

đến lĩnh vực phương tiện xã hội, nguồn dữ liệu sử dụng là dữ liệu phương tiện

xã hội. Chẳng hạn như hệ tư vấn những người bạn mới, nhóm mới hữu ích cho

người dùng. Tiếp theo, ứng dụng trong bài toán phân tích hành vi người dùng

trên MXH, giúp các công ty hiểu hơn về khách hàng của họ nhằm cải thiện chiến

17https://www.youtube.com

dịch tiếp thị, bán có mục tiêu và đưa ra dịch vụ tốt hơn. Hiểu biết dự định mua

18

sản phẩm của khách hàng để tìm kiếm sản phẩm khách hàng có khả năng mua

nhất. Ứng dụng trong bài toán giám sát các sự kiện nóng trên MXH; trong bài

toán quản lý thương hiệu, giúp các doanh nghiệp, công ty theo dõi, giám sát mức

độ thâm nhập, sức lan tỏa, ảnh hưởng của thương hiệu trên MXH vv..

1.3.6 Tối đa hóa ảnh hưởng trên mạng xã hội

Các MXH trực tuyến như Facebook, Youtube, Twitter vv.. là phương tiện giúp

lan truyền thông tin nhanh chóng và thuận tiện, đó là một ưu thế lớn giúp các

doanh nghiệp tiếp thị sản phẩm dễ dàng hơn, cho phép thông tin và ý tưởng có

thể ảnh hưởng đến một số lượng lớn người dùng khác trong một thời gian ngắn.

Bài toán tối đa hóa ảnh hưởng (Influence Maximizing) xuất phát từ nhu cầu

thực tiễn khi cần chọn một số lượng k người dùng (gọi là tập hạt giống) để khởi

tạo quá trình lan truyền hoặc bắt đầu ảnh hưởng sao cho số người bị ảnh hưởng

bởi thông tin lan truyền là cực đại. Bài toàn này có ý nghĩa lớn trong tiếp thị

sản phẩm đối với các hoạt động kinh doanh trên MXH hiện nay hay trong các

chiến dịch quảng cáo, tranh cử tổng thống vv..

Kemp, 2003, [47] là người đầu tiên phát biểu bài toán này trên mô hình MXH.

Ông đã đưa ra hai mô hình lan truyền thông tin trên MXH đó là: Mô hình ngưỡng

tuyến tính (Linear Threshold) và mô hình bậc độc lập (Independent Cascade).

Trong hai mô hình này, ông chỉ ra bài toán tối đa hóa ảnh hưởng là bài toán

NP-Khó và đưa ra một thuật toán tham lam có tỷ lệ xấp xỉ là 1 − 1/e dựa trên

tính chất của hàm mục tiêu là submodular. Một số nghiên cứu liên quan đến

vấn đề này có thể kể đến các công trình của Huiyuan Zhang [48], J Zhang [49],

Zhuang [50], Goyal [51] vv..

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

Trong thực tế trên MXH luôn tồn tại những thông tin lệch lạc, không lành

mạnh gây ra ảnh hưởng tiêu cực đến người dùng. Hơn nữa với sự lan truyền

thông tin nhanh chóng, nếu những thông tin sai lệch này đến được nhiều người

dùng thì hậu quả sẽ nghiêm trọng.

Đối với những vấn đề mang tính xã hội, những thông tin sai lệch ảnh hưởng

tiêu cực đến tâm lý, đời sống tinh thần của người dùng khi chúng được phát tán

trên mạng. Ví dụ, những thông tin không đúng về sự phát tán một dịch bệnh

19

nguy hiểm ảnh hưởng tiêu cực đến người dùng. Nó có thể ảnh hưởng đến tinh

thần, thái độ, thậm chí cả kinh tế của khu vực người dùng sinh sống. Trong hoạt

động kinh doanh, những thông tin sai lệch mang tính tiêu tiêu cực về sản phẩm

của một doanh nghiêp ảnh hưởng xấu đến tài chính, giá bán, doanh thu, và thậm

chí là thương hiệu của doanh nghiệp đó. Các nghiên cứu liên quan nhằm hạn

chế, hoặc khử nhiễm những thông tin sai lệnh, có thể kể đến một số nghiên cứu

điển hình [1, 2, 18, 19, 65].

20

Chương 2

THÔNG TIN SAI LỆCH VÀ CÁC MÔ HÌNH LAN TRUYỀN THÔNG TIN SAI LỆCH

Thông tin sai lệch lan truyền trên các MXH đang trở thành vấn nạn đối với

nhiều quốc gia. Do vậy, hạn chế sự lan truyền của thông tin sai lệch trên MXH

trực tuyến là một trong các chủ đề nhận được sự quan tâm của nhiều nhà nghiên

cứu trong thời gian gần đây. Để có thể đưa ra giải pháp hiệu quả trong việc

ngăn chặn sự lan truyền của thông tin sai lệch, chúng ta phải hiểu được cơ chế

thông tin sai lệch lan truyền trên MXH. Chương này trình bày định nghĩa thông

tin sai lệch, phân tích quá trình lan truyền thông tin sai lệch dưới hai mô hình:

Mô hình tầng độc lập và mô hình ngưỡng tuyến tính, đây là hai mô hình đang

được sử dụng rộng rãi trong các công trình nghiên cứu liên quan đến vấn đề lan

truyền thông tin, lan truyền ảnh hưởng trên MXH. Đồng thời, chương này cũng

trình bày một số hướng nghiên cứu khác nhau được công bố trong những năm

gần đây, trong việc giải quyết bài toán hạn chế lan truyền thông tin sai lệch.

2.1 Định nghĩa thông tin sai lệch

MXH được ví như con dao hai lưỡi, ngoài những giá trị tích cực thì trên MXH

cũng ẩn chứa nhiều vấn đề bất cập và hiểm họa khó lường đối với người dùng.

Trong thực tế, bên cạnh các thông tin bổ ích, có giá trị đối với xã hội thì còn

vô số thông tin, hình ảnh có nội dung xấu độc. Tại khoản 1, điều 5 Nghị định

72/2013/NĐ-CP ngày 15/7/2013 của Chính phủ đã có quy định chi tiết về việc

quản lý, cung cấp, sử dụng dịch vụ Internet và thông tin trên mạng. Trong đó

có nhiều hành vi bị nghiêm cấm như lợi dụng việc cung cấp, sử dụng dịch vụ

Internet và thông tin trên mạng nhằm mục đích chống lại Nhà nước Cộng hòa

xã hội chủ nghĩa Việt Nam; gây phương hại đến an ninh quốc gia, trật tự an

toàn xã hội; phá hoại khối đại đoàn kết dân tộc; tuyên truyền chiến tranh, khủng

bố; gây hận thù, mâu thuẫn giữa các dân tộc, sắc tộc, tôn giáo. Tuyên truyền,

kích động bạo lực, dâm ô, đồi trụy, tội ác, tệ nạn xã hội, mê tín dị đoan, phá

hoại thuần phong, mỹ tục của dân tộc. Tiết lộ bí mật nhà nước, bí mật quân sự,

21

an ninh, kinh tế, đối ngoại và những bí mật khác do pháp luật quy định. Đưa

thông tin xuyên tạc, vu khống, xúc phạm uy tín của tổ chức, danh dự và nhân

phẩm của cá nhân. Quảng cáo, tuyên truyền, mua bán hàng hóa, dịch vụ bị cấm;

truyền bá tác phẩm báo chí, văn học, nghệ thuật, xuất bản phẩm bị cấm. Giả

mạo tổ chức, cá nhân và phát tán thông tin giả mạo, thông tin sai sự thật xâm

hại đến quyền và lợi ích hợp pháp của tổ chức, cá nhân.

Hiện nay có nhiều khái niệm khác nhau về thông tin sai lệch (hay còn gọi là

thông tin xấu độc). Theo Đại tá, Nguyễn Đức Thắng - Viện Khoa học xã hội

nhân văn quân sự [14], thông tin sai lệch tán phát trên Internet và mạng xã hội

là những thông tin bịa đặt, bóp méo sự thật, xuyên tạc vấn đề, “đổi trắng, thay

đen”, làm lẫn lộn đúng sai, thật giả; hoặc có một phần sự thật nhưng được đưa

tin với dụng ý xấu, phân tích và định hướng dư luận bằng luận điệu sai trái,

thù địch. Một số thông tin chưa được kiểm chứng, thông tin sai sự thật gây ảnh

hưởng đến cá nhân, tổ chức; một số thông tin có những ngôn từ thô tục nội dung

phản cảm, thậm chí soi mói, bình phẩm chủ quan chuyện đời tư của người khác,

xúc phạm danh dự, nhân phẩm của nhiều cá nhân, gây bức xúc trong dư luận

xã hội; vi phạm chuẩn mực đạo đức, văn hóa, thuần phong mỹ tục; kích động

đồi trụy, bạo lực, bôi nhọ đời tư, vu khống vv..

Theo Karlova và Fisher, 2013, [58], thông tin sai lệch (Misinformation) được

hiểu là những thông tin giả mạo, không chính xác. Dựa trên mục đích của người

lan truyền, thông tin sai lệch được phân thành hai loại:

- Thông tin sai lệch lan truyền vô ý : Thông tin sai lệch được tạo ra và lan

truyền một cách vô ý, không có chủ đích. Mọi người có xu hướng giúp lan

truyền những thông tin như vậy do niềm tin với bạn bè, người thân và ảnh

hưởng của họ trên MXH.

- Thông tin sai lệch lan truyền cố ý : Đó là những tin đồn, tin tức giả mạo

được tạo ra và lan truyền một cách cố ý bởi người dùng với mục đích, động

cơ không trong sáng.

Như vậy, có thể thấy rằng, mặc dù có những định nghĩa khác nhau về thông

tin sai lệch tuy nhiên về nội hàm khái niệm có những điểm tương đồng nhau. Đó

đều là những thông tin không đảm bảo tính chính xác hoặc thông tin giả mạo,

xuyên tạc vấn đề, xuyên tạc nội dung vv.. gây ảnh hưởng xấu đến cá nhân và tổ

chức, đồng thời mỗi quốc gia có những quy định riêng về những hành vị bị cấm

khi đưa thông tin lên mạng và đều được cụ thể hóa trong văn bản pháp luật.

22

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 những thông tin sai lệch là ngang bằng so với những

tin tức chính thống. Chính đ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. Chẳng hạn, tin đồn tổng thống Obama bị thương sau hai

vụ nổ tại Nhà trắng năm 2013 đã làm chao đảo thị trường tài chính [54]. Hoặc tin

đồn về dịch cúm lợn năm 2009 lan truyền trên mạng Twitter đã gây ra sự hoang

mang trong xã hội [56]. Tin đồn về trận động đất ở tỉnh Ghazni, Iran vào tháng

8/2012 đã làm hàng ngàn người hoảng sợ phải rời bỏ nhà cửa của họ [57]. Ngày

30 tháng 9 năm 2014, ca nhiễm bệnh Ebola đầu tiên tại Mỹ được phát hiện, tuy

nhiên ngay sau đó, hàng loạt thông tin không chính xác được lan truyền chóng

mặt trên các MXH trực tuyến như: "Ebola có thể lây lan qua không khí, nước

và thực phẩm"; "Ebola lây lan khắp Newark, bãi biển Miami và tại Washington

D.C" vv.. Trên MXH Twitter, ước tính mỗi phút có khoảng 6000 tweet liên quan

đến dịch Ebola, buộc Bộ Y tế Hoa Kỳ phải ban hành các tuyên bố nhằm xua tan

những tin đồn không đúng sự thật trên. Hay như trong cuộc bầu cử tổng thống

Mỹ năm 2016, các nhóm đã được lập ra trên MXH trực tuyến nhằm tạo và lan

truyền những tin đồn, hạ uy tín ứng viên Tổng thống Hillary Clinton buộc bà

phải bỏ ra nhiều chi phí để giảm bớt những bất lợi này [59].

Ở Việt Nam, trong thời gian gần đây, trên các MXH liên tục đăng tải nhiều

thông tin bịa đặt, sai sự thật, lan truyền rất nhanh và thu hút sự quan tâm của

cộng đồng mạng và dư luận xã hội. Đáng chú ý nhất là vào cuối năm 2016, tin

đồn thất thiệt về việc Ngân hàng Nhà nước sắp đổi tiền đã gây tâm lý hoang

mang rất lớn trong dư luận [24]. Nhiều người dân đổ xô đi mua vàng và USD

để làm nơi trú ẩn an toàn cho tài sản của mình. Dù thông tin thất thiệt này

đã được lãnh đạo Ngân hàng Nhà nước sớm lên tiếng khẳng định là không có

cơ sở nhưng nó cũng đã có những tác động tiêu cực lớn đến nền kinh tế khiến

giá USD và vàng tăng cao. Vào đầu tháng 12/2016, đã có lúc giá USD chợ đen

tăng lên mức kỷ lục vượt quá 23.000 đồng/1USD. Giá vàng trong nước cũng đi

ngược chiều với giá thế giới. Sau đó, với sự lên tiếng kịp thời của cơ quan chức

năng nên tình hình mới dần được cải thiện và đi vào ổn định. Ngày 15/12/2016,

Tổng Cục an ninh Bộ Công an bắt giữ được các nghi can. Những người này khai

đã lập ra một fanpage trên MXH Facebook với gần 70 nghìn lượt like, liên tục

đăng tải các thông tin bịa đặt liên quan đến việc đổi tiền. Do có lượng theo dõi

23

lớn nên thông tin bịa đặt mà trang này đăng tải được chia sẻ và lan truyền rất

nhanh trên mạng.

Cũng trong thời gian trên, tin đồn lệ phí cấp hộ chiếu tăng giá đến 70

USD/quyển kể từ ngày 1/1/2017 lan truyền nhanh trên mạng khiến hàng nghìn

người dân đổ xô đến trụ sở cơ quan Quản lý xuất nhập cảnh để làm thủ tục

đề nghị cấp hộ chiếu [25]. Điều này khiến cho nhiều trụ sở cấp, đổi hộ chiếu ở

các địa phương trở nên quá tải. Để giải quyết tình hình trên, Cục Quản lý xuất

nhập cảnh (Bộ Công an) phải ban hành công văn phản hồi trước thông tin sai

lệch trên và cho biết nguyên nhân của tin đồn này xuất phát từ sự hiểu nhầm

về lệ phí cấp hộ chiếu phổ thông cho công dân Việt Nam ở trong nước với công

dân ở nước ngoài.

Hơn bao giờ hết, làn sóng tin tức giả lan truyền trên MXH với tốc độ chóng

mặt và ngày càng diễn biến phức tạp. Để ứng phó với vấn nạn này, nhiều nước

đã gấp rút thành lập các cơ quan chống tin tức giả mạo trên mạng, đồng thời

hợp tác với các nước có kinh nghiệm trong lĩnh vực này để thực hiện chiến dịch

phòng chống tin tức giả mạo. Để đảm bảo cho cuộc bầu cử Đức vào tháng 9/2017

tới đây diễn ra một cách suôn sẻ, Đức đã lên kế hoạch thành lập một trung tâm

chống tin tức giả mạo. Ngày 6/4/2017, chính phủ Đức thông qua khoản tiền phạt

lên tới 50 triệu Euro đối với các MXH nếu như không nhanh chóng xử lý tin tức

giả mạo và những phát ngôn gây thù hận. Các mạng xã hội như Facebook hay

Twitter vv.. sẽ có 24 giờ đồng hồ để xóa hoặc ngăn chặn các nội dung vi phạm

pháp luật sau khi nhận được báo cáo và 7 ngày để hành động đối với các nội

dung tiêu cực khác.

Gần đây, Indonesia là quốc gia cũng đi theo xu hướng này, ngày 5/1/2017

Indonesiasẽ thành lập cơ quan chuyên xử lý nạn tin tức giả mạo lan tràn trên

MXH. Theo hãng tin AFP, động thái này diễn ra sau khi làn sóng tin tức giả

mạo đã gây ra nhiều hoang mang, hỗn loạn với dư luận tại Indonesia, trong đó có

cả những thông tin cho rằng Trung Quốc đang tiến hành một cuộc chiến tranh

sinh học tại Indonesia bằng cách tung ra những loại hạt giống ớt nhiễm độc.

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.

Xuất phát từ những thực tế nêu trên, tác giả nhận thấy viêc ngăn chặn kịp

thời sự lan truyền của thông tin sai lệch trên MXH là một thách thức lớn cần

24

giải quyết nhằm giảm thiểu tối đa những thiệt hai do chúng gây ra đối với người

dùng, góp phần làm trong sạch môi trường mạng, nâng cao sự tin tưởng của

người dùng đối với những thông tin trên MXH. Do vậy, trong luận văn này, tác

giả đề xuất một giải pháp giúp ngăn chặn sự lan truyền của thông tin sai lệch

trên MXH. Chi tiết giải pháp sẽ được trình bày trong Chương 3 của luận văn.

2.2 Mô hình lan truyền thông tin sai lệch

Một MXH được biểu diễn bởi một đồ thị có hướng G = (V, E) trong đó:

- V là tập hợp gồm n đỉnh, biểu diễn các cá nhân trong MXH.

- E ⊆ V × V là tập hợp gồm m cạnh có hướng, biểu diễn mối quan hệ giữa

các cá nhân trong MXH.

Do G là đồ thị có hướng nên với mỗi đỉnh u, cạnh (u, v) ∈ E được gọi là cạnh đi ra từ u, cạnh (v, u) ∈ E được gọi là cạnh đi vào đỉnh u. Ta ký hiệu N out(u) và N in(u) tương ứng là tập hợp các đỉnh hàng xóm đi ra và đi vào đỉnh u.

Quá trình lan truyền thông tin theo các bước thời gian rời rạc, với thời gian

t = 0, 1, 2, vv.. Gọi St ⊆ V là tập các đỉnh ở trạng thái kích hoạt tại thời điểm t. S0 là tập hạt giống hay tập nguồn phát thông tin sai lệch ban đầu.

Khi có thông tin sai lệch, mỗi đỉnh u ∈ V ở 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 thời gian 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 ban đầu (đỉ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.

Hiện nay, có nhiều mô hình lan truyền thông tin khác nhau được nghiên cứu và

đề xuất như: mô hình ngưỡng (Threshold Model) [26], mô hình tầng (Cascading

Model) [27], mô hình dịch bệnh (Epidemic Model) [28], mô hình lan truyền ảnh

hưởng cạnh tranh (Competitive Influence Diffusion Model) [29]. Trong đó hai

mô hình tầng độc lập (Independent Cascade - IC) và mô hình ngưỡng tuyến tính

(Linear Threshold - LT) do Kempe, 2003, [47] đề xuất đang được dùng rộng rãi

trong nhiều công trình nghiên cứu.

25

2.2.1 Mô hình tầng độc lập

Đặc trưng chính của mô hình IC đó là quá trình lan truyền thông tin dọc theo

các cạnh của đồ thị một cách độc lập nhau.

Trong mô hình IC, mỗi cạnh (u, v) ∈ E được gán một xác suất ảnh hưởng

(Influence Probability) p(u, v) ∈ [0, 1] biểu diễn mức độ ảnh hưởng của đỉnh u

đến đỉnh v. Nếu (u, v) /∈ E thì p(u, v) = 0. Mô hình IC hoạt động theo bước thời

gian rời rạc t như sau:

- Tại thời điểm t = 0, tập đỉnh ở trạng thái kích hoạt chính là tập nguồn phát

thông tin sai lệch S0.

- Tại thời điểm t ≥ 1, mỗi đỉnh u ∈ (St−1\St−2) được kích hoạt ở bước t − 1 có một cơ hội duy nhất để kích hoạt các đỉnh hàng xóm của nó ở trạng thái

không kích hoạt với xác suất kích hoạt thành công p(u, v) và sự kích hoạt

này là độc lập với các kích hoạt khác. Nếu đỉnh u không kích hoạt được đỉnh

v ở thời điểm t, nó sẽ không có cơ hội kích hoạt lại v ở các bước tiếp theo.

Nếu đỉnh v có nhiều đỉnh hàng xóm cùng kích hoạt tại một thời điểm, các

đỉnh này sẽ kích hoạt v theo thứ tự tùy ý. Nếu một đỉnh được kích hoạt, nó

sẽ giữ nguyên trạng thái kích hoạt ở các bước tiếp theo.

- Quá trình lan truyền thông tin kết thúc khi không có thêm đỉnh nào được

kích hoạt, tức là St = St−1.

Trong hình 2.1 chỉ ra một ví dụ của quá trình lan truyền thông tin trên mô

hình IC. Các đỉnh màu da cam và màu xanh tương ứng biểu diễn các đỉnh ở

trạng thái kích hoạt, và không kích hoạt. Cạnh liền màu đỏ từ u đến v biểu diễn

u kích hoạt thành công v, cạnh nét đứt màu xanh từ u đến v biểu diễn u kích

hoạt không thành công v.

Tại bước t = 0, hai đỉnh v1, v2 ở trạng thái kích hoạt. Ở bước t = 1, v1 kích hoạt thành công v5 nhưng thất bại với v3, trong khi đó v2 kích hoạt thành công v3 và v4 nhưng thất bại với v6. Tại bước t = 2, v3 kích hoạt thất bại v6 trong khi v5 kích hoạt thành công v6 nhưng thất bại với v9. Ở bước t = 3, v6 kích hoạt thất bại v7, đến đây quá trình lan truyền thông tin kết thúc do không có đỉnh nào được kích hoạt thêm.

26

Hình 2.1: Một ví dụ quá trình lan truyền thông tin trên mô hình IC

2.2.2 Mô hình ngưỡng tuyến tính

Mô hình IC phù hợp để mô tả quá trình lan truyền thông tin, ở đó một đỉnh

được kích hoạt trực tiếp từ duy nhất một đỉnh khác kề với nó, ví dụ như sự lây

lan của Virus. Trong thực tế có nhiều trường hợp, 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 như trên thị trường có một mẫu Iphone mới ra, một người chưa thực

sự tin tưởng để mua chiếc Iphone này nhưng khi thấy nhiều bạn bè, người thân

của họ mua chiếc Iphone đó, có thể làm thay đổi suy nghĩ và dẫn đến hành động

người này chấp nhận mua chiếc Iphone. Các nhà khoa học xã hội gọi những hành

vi này là hành vi ngưỡng và Kempe là người đầu tiên đề xuất mô hình ngưỡng

tuyến tính (LT) để phản ánh kiểu hành vi này.

Trong mô hình LT, mỗi cạnh (u, v) ∈ E được gán một trọng số ảnh hưởng

(Influence Weight) w(u, v) ∈ [0, 1] biểu diễn mức độ ảnh hưởng của đỉnh u đến

đỉnh v. Nếu (u, v) /∈ E thì w(u, v) = 0. Các trọng số này được chuẩn hóa sao cho

27

với mỗi đỉnh v, tổng trọng số tất cả các cạnh đi đến đỉnh v lớn nhất bằng 1, tức

là:

(cid:88)

w(u, v) ≤ 1

u∈N in(v)

(2.1)

Tùy vào đặc tính của từng người dùng tương ứng, mỗi đỉnh v ∈ V có một giá

trị θv ∈ [0, 1], biểu diễn ngưỡng đỉnh v bị ảnh hưởng bởi các đỉnh kích hoạt hàng xóm mà trở thành kích hoạt. Nếu giá trị θv lớn, tức là cần nhiều đỉnh hàng xóm để kích hoạt đỉnh v; nếu giá trị θv nhỏ, tức là đỉnh v dễ dàng bị kích hoạt bởi một vài đỉnh hàng xóm. Do thiếu thông tin về ngưỡng của mỗi người dùng trong

mạng xã hội nên trong mô hình này các giá trị ngưỡng θv được lựa chọn ngẫu nhiên, độc lập phân bố đều trong đoạn [0, 1] và được cập nhật trong suốt quá

trình lan truyền, vì vậy mô hình này cũng như mô hình IC thuộc lớp mô hình

ngẫu nhiên. Mô hình LT hoạt động theo bước thời gian rời rạc t như sau:

- Tại thời điểm t = 0, tập đỉnh ở trạng thái kích hoạt chính là tập nguồn phát

thông tin sai lệch S0.

- Tại thời điểm t ≥ 1, với mỗi đỉnh ở trạng thái không kích hoạt v ∈ V \St−1 sẽ bị kích hoạt nếu tổng ảnh hưởng từ những đỉnh hàng xóm kích hoạt tới

nó vượt ngưỡng θv, tức là:

(cid:88)

(2.2)

w(u, v) ≥ θv

u∈St−1∩N in(v)

Nếu một đỉnh được kích hoạt, nó sẽ giữ nguyên trạng thái kích hoạt ở các

bước tiếp theo.

- Quá trình lan truyền thông tin kết thúc khi không có thêm đỉnh nào được

kích hoạt, tức là St = St−1.

Trong hình 2.2 chỉ ra một ví dụ của quá trình lan truyền thông tin trên mô

hình LT. Các đỉnh màu da cam và màu xanh tương ứng biểu diễn các đỉnh ở

trạng thái kích hoạt, và không kích hoạt. Các cạnh liền màu đỏ cùng đến đỉnh v

biểu diễn tổng trọng số các cạnh này kích hoạt thành công v.

Tại bước t = 0, tất cả các đỉnh được khởi tạo ngẫu nhiên ngưỡng θv ∈ [0, 1], hai đỉnh v1, v2 là các đỉnh hạt giống. Ở bước t = 1, v1 và v2 kích hoạt thành công v3, v1 cũng kích hoạt thành công v5 và v2 kích hoạt thành công v4; tuy nhiên, v6 lại không bị kích hoạt vì tổng trọng số các cạnh đi đến v6 là 0.3, trong khi ngưỡng kích hoạt của v6 là 0.7. Tại bước t = 2, các đỉnh hàng xóm đi đến v6 là

28

v2, v3, v5 đã được kích hoạt cho nên tổng trọng số các cạnh đi đến là 0.7, đủ để kích hoạt v6. Tại bước t = 3, quá trình lan truyền thông tin kết thúc do không có đỉnh nào được kích hoạt thêm.

Hình 2.2: Một ví dụ quá trình lan truyền thông tin trên mô hình LT

Một mô hình lan truyền thông tin thuộc lớp mô hình lan truyền tăng trưởng

(Progressive Diffusion Model) khi một đỉnh được kích hoạt sẽ giữ nguyên trạng

thái kích hoạt ở các bước thời gian tiếp theo, tức là ∀t ≥ 1, St−1 ⊆ St. Cả hai mô hình IC và mô hình LT đều thuộc lớp mô hình lan truyền tăng trưởng này, bởi

vì tập các đỉnh ở trạng thái kích hoạt là đơn điệu và không giảm theo các bước

thời gian rời rạc. Ngoài ra, hai mô hình này cũng thuộc lớp mô hình ngẫu nhiên

(theo các bước thời gian rời rạc), nghĩa là tập các đỉnh ở trạng thái kích hoạt St (∀t ≥ 1) là tập ngẫu nhiên.

Gọi Φ(S0) là tập các đỉnh ở trạng thái kích hoạt sau khi quá trình lan truyền thông tin kết thúc, ở đây S0 là tập nguồn phát thông tin sai lệch ban đầu. Tập Φ(S0) là một tập ngẫu nhiên, xác định bởi quá trình lan truyền ngẫu nghiên trên mô hình IC và mô hình LT. Gọi E(X) là giá trị kỳ vọng của biến ngẫu nhiên X;

gọi σ(S0) là giá trị kỳ vọ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 hay còn gọi là hàm lan truyền ảnh hưởng của tập S0, khi đó σ(S0) = E(|Φ(S0)|).

Chen [60, 61] và các cộng sự đã chỉ ra rằng việc tính toán chính xác giá trị

σ(S0) với S0 là tập hạt giống ban đầu là một bài toán #P-khó dưới cả hai mô hình IC và LT, ngay cả khi tập S0 chỉ gồm một đỉnh. Đồng thời cũng chỉ ra mô hình IC và mô hình LT cùng tương đương với mô hình đồ thị live-arc (tạm dịch

là mô hình đồ thị cạnh sống hay đồ thị mẫu), tuy nhiên hai mô hình này lại

t=1 là như nhau trong cả hai mô hình. Mô hình đồ thị mẫu

không tương đương với nhau. Hai mô hình được gọi là tương đương theo nghĩa các tập kích hoạt {St}T

29

cho ta một cách nhìn thay thế mô hình IC và mô hình LT, giúp hiểu rõ hơn hai

mô hình này. Mô hình đồ thị mẫu được định nghĩa như sau:

- Đồ thị mẫu dưới mô hình LT : Với đồ thị G = (V, E) cho trước, mỗi cạnh

(u, v) ∈ E được gán một trọng số ảnh hưởng w(u, v) ∈ [0, 1]. Sinh ngẫu nhiên

một đồ thị mẫu GL bằng cách, với mỗi đỉnh v ∈ V chọn nhiều nhất một cạnh kề đi đến nó với xác suất chọn cạnh (u, v) ∈ E là w(u, v) và xác suất không có cạnh nào được lựa chọn là 1 − (cid:80) u∈N in(v) w(u, v). Những cạnh được chọn được gọi là cạnh sống (live-arc) và tất cả những cạnh khác được gọi là

cạnh bị chặn (blocked-arc). Như vậy, GL là đồ thị gồm tập đỉnh V và tập cạnh là những cạnh sống.

- Đồ thị mẫu dưới mô hình IC : Với đồ thị G = (V, E) cho trước, mỗi cạnh

(u, v) ∈ E được gán một xác suất ảnh hưởng p(u, v) ∈ [0, 1]. Sinh ngẫu nhiên

một đồ thị mẫu GL bằng cách, mỗi cạnh (u, v) ∈ E được chọn là cạnh sống với xác suất p(u, v). Như vậy, GL là đồ thị gồm tập đỉnh V và tập cạnh là những cạnh sống.

Ta có thể sử dụng mô hình đồ thị mẫu để tính toán giá trị hàm σ(S0). 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) là xác suất lựa chọn đồ thị GL từ tập G và R(GL, S0) là tập hợp các đỉnh đi đến được từ tập S0 trong đồ thị GL. Hàm lan truyền ảnh hưởng σ(S0) được tính bởi công thức sau:

(cid:88)

(2.3)

σ(S0) =

P r(GL)|R(GL, S0)|

GL∈G

Trong đó ký hiệu |X| chỉ số phần tử của tập X.

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

Tối ưu hóa ảnh hưởng các đối tượng trên MXH là bài toán được nghiên cứu

lần đầu tiên bởi Domingos và Richardson, 2001 [62]. Đây là bài toán có ý nghĩa

và mang tính thời sự, nhận được sự quan tâm lớn của nhiều nhà nghiên cứu

trong những năm gần đây. Trong nghiên cứu của mình, Domingos và Richardson

đã thiết kế các chiến lược tiếp thị lan truyền (Viral Marketing) và phân tích

quá trình lan truyền thông tin sử dụng phương pháp khai phá dữ liệu. Sau đó,

Kempe, 2003 [47] là người đầu tiên xây dựng vấn đề tối ưu hóa ảnh hưởng trên

MXH theo cách tối ưu hóa rời rạc, bài toán được phát biểu như sau:

30

Định nghĩa 2.1 (Tối ưu hóa ảnh hưởng) Cho đồ thị G = (V, E) biểu diễn

một MXH, trong đó tập V biểu diễn các cá nhân trong MXH, tập E biểu diễn

mối quan hệ giữa các cá nhân. Với ngân sách k cho trước, tìm tập hạt giống

S0 ⊆ V với |S0| = k, sao cho hàm lan truyền ảnh hưởng của tập S0, σ(S0), dưới mô hình lan truyền thông tin ngẫu nhiên cho trước, đạt giá trị cực đại. Tức là, cần tính S∗ ⊆ V sao cho1:

(2.4)

σ(S0)

S∗ = argmax S0⊆V,|S0|=k

Trong Định nghĩa 2.1, thuật ngữ lan truyền ảnh hưởng ở đây có thể hiểu là

sự lây lan cảm xúc, quan điểm, hành vi từ người này sang người khác, từ nhóm

người này sang nhóm người khác trước một vấn đề, một sự kiện hay một hiện

tượng nào đó. Hàm lan truyền ảnh hưởng trả về kết quả là số người bị ảnh hưởng

trong một MXH.

Một ví dụ điển hình của bài toán tối ưu hóa lan truyền ảnh hưởng là vấn đề

tiếp thị sản phẩm. Chẳng hạn, một công ty muốn giới thiệu cho cộng đồng một

sản phẩm do công ty tạo ra đó là một ứng dụng trực tuyến. Tuy nhiên, công

ty đó lại có ngân sách hạn chế (ngân sách ở đây được hiểu là chi phí bỏ ra), vì

vậy chỉ có thể lựa chọn một số lượng nhỏ người sử dụng ban đầu để trải nghiệ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ệ

1Hàm argmax trả về các tập hạt giống tối ưu, S∗ là một tập trong số đó.

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

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 − (cid:15)).

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à

v . Gọi I A

v và θB

0 và I B

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 tin sai lệch B tương ứng là θA

wA

uv ≥ θA

u∈I A

t−1

uv ≥ θB

u∈I B

t−1

0 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 bởi thông tin tốt nếu (cid:80) nếu (cid:80) wB bởi thông tin tốt nếu P A

v = ((cid:80)

v và ngược lại, trong đó P i

v ≥ P B

u∈N in

a (v) wi

v hoặc bị kích hoạt bởi thông tin sai lệch v . Nếu cả hai ngưỡng đều thỏa mãn, v được coi là bị kích hoạt uv)/θi 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

0 , với |I A

0 ban đầu và số kA cho trước, hãy xác định tập các đỉnh 0 | = 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.

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 phát thông tin sai lệch I B nguồn phát thông tin tốt I A

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ó:

(cid:89)

p(v)

(3.1)

P r(GL) =

v∈V

Trong đó

w(u, v)

 

nếu ∃u : (u, v) ∈ EGL

p(v) =

1 − (cid:80)

ngược lại



u∈N in(v) w(u, v)

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:

(cid:88)

σ(S) =

(3.2)

P r(GL)|R(GL, S)|

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à:

(cid:88)

D(S) = σ(S) =

(3.3)

P r(GL)|R(GL, S)|

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ó:

(3.4)

Rd(GL, S) = {v ∈ V | dGL(S, v) ≤ d}

d do nguồn thông tin

Khi đó từ Công thức 3.3 ta xác định được thiệt hại DS

sai lệch S gây ra sau d bước lan truyền như sau:

(cid:88)

DS

(3.5)

P r(GL)|Rd(GL, S)|

d =

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).

và DS 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) d (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ó:

(cid:88)

DS

(3.6)

P r(GL)|Rd(GL, S)|

d (I) =

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

u∈I c(u) ≤ B, nhằm cực tiểu hóa hàm DS

d (I).

u∈I c(u) ≤ B.

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 chi phí không vượt quá B, (cid:80)

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 d (I) với điều kiện (cid:80) DS Đ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 cho (cid:83) 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 S(cid:48) ⊆ S kích thước nhỏ hơn hoặc bằng k, sao cho (cid:83)

Si∈S (cid:48) Si = U.

Đị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

d (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:

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 tại hay không tập đỉnh cần tạo miễn dịch I ⊂ V \S với (cid:80) u∈I c(u) ≤ B sao cho DS

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à IM DM = {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 d+(vj), trong đó

dựng một cạnh có hướng (ui, vj) với trọng số w(ui, vj) = 1 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) = +∞.

• Cuối cùng, đặt B = k, d = 2, t = n − k.

Hình 3.1: Phép dẫn từ bài toán Tập phủ dạng 0 − 1 đến bài 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 xây dựng ở trên, ta sẽ chứng minh hai thể hiện ISC = {U, S, k}

và IM DM = {G, w(u, v), θv, S, c(u), r(u), d, B, t} là tương đương với nhau.

Phần thuận: Nếu bài toán Tập phủ dạng 0 − 1 có lời giải thì bài toán MDM

(cid:48)

(cid:48) với |S

cũng có lời giải tương ứng.

| ≤ k và nó có thể phủ toàn bộ

(cid:48)

Giả sử thể hiện ISC có lời giải là tập S

các phân tử của tập U. Bằng phép dẫn ở trên, chọn tập đỉnh để tạo miễn dịch là (cid:48) phủ tất cả các phần

}. Khi đó, ta có (cid:80)

ui∈I c(ui) ≤ k = B. Do S

I = {ui | Si ∈ S 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 khi tạo miễn dịch trên tập I ta có: (cid:80) active(vj) w(ui, vj) < 1 = θvj , suy ra không ui∈N in có bất kỳ đỉnh vj nào được kích hoạt. Các đỉnh ui /∈ I và kề trực tiếp với các đỉnh thuộc tập S sẽ bị thông tin sai lệch kích hoạt, do đó DS

d (I) = n − k.

Phần nghịch. Nếu bài toán MDM có lời giải thì bài toán Tập phủ dạng 0 − 1

cũng có lời giải tương ứng.

(cid:80)

(cid:48)

(cid:48)

tập S

= {Si | ui ∈ I}. Khi đó, ta có |S

Giả sử thể hiện IM DM có lời giải là tập đỉnh cần tạo miễn dịch I ⊂ V \S với u∈I c(u) = B = k sao cho DS d (I) ≤ n − k. Bằng phép dẫn ở trên, ta xác định | = k. Do c(vj) = +∞ > B (j = 1..m) nên không thể tạo miễn dịch trên các đỉnh vj (j = 1..m), như vậy tập I chỉ có thể

41

bao gồm các đỉnh ui (i = 1..n). Ngoài ra, DS d (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ề với ít nhất một đỉnh ui ∈ I hay tập S (cid:48) 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:

f (I) = DS

d (∅) − DS

d (I) = DS

d − DS

d (I)

(3.7)

d (∅) = DS d .

trong đó ngầm định DS

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:

α(v) =

(3.8)

(f (I ∪ {v}) − f (I)) c(v)

3.3.1 Thuật toán tham lam dựa trên hàm f (I)

gây ra, tức là cực tiểu hóa hàm DS

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 d (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

Algorithm 1: Thuật toán tham lam dựa trên hàm f (I)

1

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. begin

2

3

4

5

I ← ∅; N ← Nd(S); C ← 0; while (C < B) and (N (cid:54)= ∅) do

6

7

8

9

u ← argmaxv∈N f (I ∪ {v}); //Chọn ra đỉnh v sao cho f (I ∪ {v}) đạt giá trị lớn nhất if C + c(u) ≤ B then I ← I ∪ {u}; C ← C + c(u);

10

11

end N ← N \{u};

12

13

end Return I;

14

end

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.

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 n2 1 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 lượng giá trị hàm DS d (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

Algorithm 2: Thuật toán ước lượng giá trị hàm DS

d (I)

d (I).

1

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. Output: Giá trị ước lượng hàm DS begin

2

3

4

Đồ thị G(I) thu được sau khi loại bỏ tập đỉnh I từ đồ thị G; count ← 0; for j = 1 to R do

5

6

7

mô phỏng quá trình lan truyền thông tin trên đồ thị G(I) từ tập nguồn S; na ← số đỉnh kích hoạt sau d bước lan truyền; count ← count + na;

8

9

end 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

1R), với n1 = |Nd(S)|, R là số lần mô phỏng.

là O(n2

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à

O(n2

1R), 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)

1

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. begin

2

3

4

5

I ← ∅; N ← Nd(S); C ← 0; while (C < B) and (N (cid:54)= ∅) do

α(v) =

, ∀v ∈ N ;

6

(f (I ∪ {v}) − f (I)) c(v)

7

8

9

10

u ← argmaxv∈N α(v); //Chọn ra đỉnh v sao cho α(v) đạt giá trị lớn nhất if C + c(u) ≤ B then I ← I ∪ {u}; C ← C + c(u);

11

12

end N ← N \{u};

13

14

end 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ật toán cơ sở khác như

thuật toán Max Degree và thuật toán Random. Tính hiệu quả ở đây xét trong

ngữ cảnh độ giảm thiệt hại hay độ giảm số đỉnh bị thông tin sai lệch kích hoạt

sau khi tạo miễn dịch cho tập đỉnh I.

4.1 Mục đích thực nghiệm

Trong phần này, luận văn trình bày cách thức tiến hành thực nghiệm và kết

quả thực nghiệm nhằm đánh giá hiệu quả hai thuật toán tham lam: Thuật toán

1 và Thuật toán 3, so sánh với các thuật toán cơ sở khác như thuật toán Max

Degree và thuật toán Random. Hai thuật toán cơ sở này được sử dụng nhiều

trong thực nghiệm nhằm so sánh với các thuật toán đề xuất: Kempe, 2003, [47];

Chen, 2010, [61]; Goyal, 2011, [64]. Ngoài ra, thực nghiệm cũng nhằm giải quyết

các câu hỏi: Khi ngân sách B thay đổi sẽ ảnh hưởng thế nào đến kết quả? Kích

thước của tập nguồn phát thông tin sai lệch S thay đổi sẽ ảnh hưởng thế nào

đến kết quả?

4.2 Dữ liệu tiến hành thực nghiệm

Dữ liệu được tiến hành thực nghiệm bao gồm dữ liệu của ba mạng xã hội

trong thực tế và chúng được dùng rộng rãi trong các nghiên cứu về lan truyền

thông tin, được lấy từ nguồn [http://snap.stanford.edu/data/]. Ba bộ dữ liệu

được chọn đại diện cho các mạng với quy mô khác nhau, từ vài trăm đến vài

nghìn đỉnh.

• Email: Đây là một mạng lưới trao đổi email trong một cơ quan nghiên cứu

lớn của châu Âu. Toàn bộ thông tin về các email gửi đến và gửi đi giữa các

thành viên trong cơ quan được ẩn danh. Mỗi nhà nghiên cứu là một đỉnh

trong đồ thị và một email từ nhà nghiên cứu u đến nhà nghiên cứu v tạo

46

thành một cạnh (u, v, t) tương ứng, trong đó t là thời điểm gửi thư. Bộ dữ

liệu thu thập được của mạng xã hội này gồm: 986 đỉnh và 332, 334 cạnh.

• CollegeMsg: Đây là bộ dữ liệu bao gồm các tin nhắn được gửi trên một mạng

xã hội trực tuyến tại Đại học California, Irvine. Mỗi người dùng có thể tìm

kiếm bạn bè trên mạng dựa trên thông tin tiểu sử của người kia, sau đó bắt

đầu cuộc trò chuyện bằng cách gửi tin nhắn cho nhau. Mỗi người dùng trong

mạng là một đỉnh trong đồ thị và một tin nhắn từ người dùng u đến người

dùng v tạo thành một cạnh (u, v, t) tương ứng, trong đó t là thời điểm gửi

tin nhắn. Bộ dữ liệu thu thập được của mạng xã hội này gồm: 1, 899 đỉnh

và 59, 835 cạnh.

• Gnutella: Gnutella là một mạng chia sẻ tập tin ngang hàng, được xây dựng

vào năm 2000. Sử dụng một trình khách (Client) Gnutella được cài đặt trên

máy, người dùng có thể tìm kiếm, tải xuống, tải lên các tệp tin trên mạng.

Bộ dữ liệu thu được bằng một loạt các bức ảnh chụp nhanh (Snapshot) của

mạng chia sẻ tập tin ngang hàng Gnutella. Tổng cộng có 9 bức ảnh chụp

nhanh vào tháng 8/2002. Các đỉnh của đồ thị đại diện cho các máy trạm

trong tôpô mạng, các cạnh biểu diễn các kết nối giữa những máy trạm này.

Bộ dữ liệu thu thập được của mạng này gồm: 6, 301 đỉnh và 20, 777 cạnh.

Thông tin chi tiết về các bộ dữ liệu tiến hành thực nghiệm được mô tả trong

Tên mạng Kiểu đồ thị Số đỉnh Số cạnh Bậc lớn nhất Bậc trung bình

Email CollegeMsg Gnutella

Có hướng Có hướng Có hướng

986 1,899 6,301

332,334 59,835 20,777

333 237 48

25.2 10.6 3.2

Bảng 4.1: Dữ liệu thực nghiệm

bảng 4.1 dưới đây:

4.3 Cài đặt thực nghiệm

Các thuật toán trong thực nghiệm được cài đặt bằng ngôn ngữ lập trình

Python. Thực nghiệm được tiến hành với các bộ dữ liệu mạng quy mô lớn, do

vậy tất cả các thực nghiệm đều được chạy trên máy tính có tốc độ tính toán

cao để đảm bảo hiệu suất và thời gian chạy thực nghiệm. Cụ thể, cấu hình máy

tính thực nghiệm như sau: Chipset: 2 x Intel(R) Xeon(R) CPU E5-2697 v4 @

2.30GHz, RAM: 64 GB DIMM ECC DDR4 @ 2400MHz, hệ điều hành CentOS.

47

Ngoài hai thuật toán tham lam được đề xuất, tác giả sử dụng hai thuật toán

sau đây để so sánh, chi tiết hai thuật toán xem trong phần phụ lục của luận văn:

• Max Degree: Lựa chọn những đỉnh có bậc cao nhất để tạo miễn dịch.

• Random: Lựa chọn ngẫu nhiên các đỉnh để tạo miễn dịch.

Trọng số ảnh hưởng w(u, v) trong mô hình lan truyền thông tin LT, được thiết

lập như trong nội dung thực nghiệm của Kempe, 2003, [47] và nhiều công trình

nghiên cứu khác [13, 61]: Mỗi cạnh đi đến đỉnh v được gán trọng số ảnh hưởng

bằng 1/d(v), với d(v) là bậc đi đến (In-degree) của v. Điều này có nghĩa rằng mỗi

cạnh đều có đóng góp như nhau trọng việc kích hoạt đỉnh v và tổng trọng số của

tất cả các cạnh đi đến đỉnh v bằng 1.

Chi phí tạo miễn dịch với thông tin sai lệch đối với mỗi đỉnh u ∈ V được khởi

tạo ngẫu nhiên một số thuộc khoảng [1.0, 3.0].

Hơn nữa, tất cả những thuật toán sử dụng phương pháp mô phỏng Mote Carlo

đều được chọn số lần mô phỏng R = 10000.

4.4 Kết quả thực nghiệm

Ảnh hưởng khi ngân sách B thay đổi: Chúng ta so sánh hiệu quả của

Thuật toán 1 và Thuật toán 3 với các thuật toán còn lại khi ngân sách B thay

đổi, B = {10, 25, 35, 50, 70, 110}, với d = 6 và tập nguồn phát thông tin sai lệch

được khởi tạo ngẫu nhiên, |S| = 10. Tổng thiệt hại do thông tin sai lệch gây

ra sau khi tạo miễn dịch cho tập đỉnh I được chỉ ra trong hình 4.1. Ở tất cả

các trường hợp, Thuật toán 1 và Thuật toán 3 đều tốt hơn hai thuật toán Max

Degree và Random, độ giảm thiệt hại khi áp dụng hai thuật toán này cao hơn

từ 1.017 lần đến 3.4781 lần so với thuật toán Max Degree. Đặc biệt, đối với mạng

Email, khi ngân sách B = 10, Thuật toán 1 và Thuật toán 3 hiệu quả hơn 3.4781

lần và 2.87 lần tương ứng, so với thuật toán Max Degree; đối với mạng Gnutella,

khi ngân sách B = 10, Thuật toán 1 và Thuật toán 3 hiệu quả hơn 3.0521 lần và

3.02781 lần tương ứng, so với thuật toán Max Degree.

Khi ngân sách B = {50, 70, 110}, áp dụng Thuật toán 1 và Thuật toán 3 hạn

chế được từ 43.11% đến 90.44% thông tin sai lệch lan truyền trên mạng. Đặc biệt,

đối với mạng Gnutella, khi B = 110, Thuật toán 1 và Thuật toán 3 hạn chế được

90.44% và 90.41% tương ứng, thông tin sai lệch lan truyền.

48

(a) Email

(b) CollegeMsg

(c) Gnutella

Hình 4.1: Tổng thiệt hại khi ngân sách B thay đổi, d = 6, |S| = 10

Khi ta tăng kích thức của tập nguồn phát thông tin sai lệch lên |S| = 20, kết

quả được chỉ ra trong hình 4.2. Ta thấy rằng, ở tất cả các trường hợp, hai thuật

toán tham lam đề xuất đều tốt hơn hai thuật toán Max Degree và Random. Đặc

biệt, đối với mạng Gnutella, khi ngân sách B = 25, Thuật toán 1 và Thuật toán

3 hiệu quả hơn thuật toán Max Degree 3.466 lần xét về độ giảm thiệt hại sau khi

tạo miễn dịch với tập đỉnh I.

49

Nhìn chung, Thuật toán 1 và Thuật toán 3 có hiệu quả gần như nhau khi

(a) Email

(b) CollegeMsg

(c) Gnutella

Hình 4.2: Tổng thiệt hại khi ngân sách B thay đổi, d = 6, |S| = 20

ngân sách B thay đổi trên ba bộ dữ liệu.

Ảnh hưởng khi kích thước tập nguồn S thay đổi: Chúng ta so sánh

hiệu quả của hai thuật toán tham lam với các thuật toán còn lại khi kích thước

tập nguồn phát thông tin sai lệch S thay đổi, |S| = {5, 10, 15, 20, 25}, với d = 5 và

ngân sách cố định B = 25. Hình 4.3 chỉ ra độ giảm thiệt hại do thông tin sai lệch

50

gây ra sau khi áp dụng các thuật toán nhằm tìm ra tập đỉnh I để tạo miễn dịch.

Ta thấy rằng, ở tất cả các trường hợp, Thuật toán 1 và Thuật toán 3 đều tốt

hơn hai thuật toán còn lại. Với bộ dữ liệu Email, khi |S| = 5, ta thấy Thuật toán

1 hiệu quả gấp 2.563 lần thuật toán Max Degree, còn trên bộ dữ liệu Gnutella,

(a) Email

(b) CollegeMsg

(c) Gnutella

Hình 4.3: Độ giảm thiệt hại khi kích thước nguồn S thay đổi, d = 5, B = 25

khi |S| = 20, Thuật toán 1 hiệu quả gấp 3.98 lần thuật toán Max Degree.

51

4.5 Kết luận và nhận xét

Khi ngân sách B tăng dần, ta thấy rằng cả hai thuật toán tham lam: Thuật

toán 1 và Thuật toán 3 đều hiệu quả hơn thuật toán Max Degree và thuật toán

Random. Tuy nhiên, tính hiệu quả được thể hiện rõ nhất khi với giá trị B nhỏ.

Tính hiệu quả của hai thuật toán đề xuất không thay đổi nhiều khi kích thước

tập nguồn phát thông tin sai lệch tăng lên.

Thuật toán 1 trong đa số các trường hợp là hiệu quả hơn Thuật toán 3, tuy

nhiên hai thuật toán này chênh lệch nhau không nhiều.

52

KẾT LUẬN

Sự bùng nổ của thông tin sai lệch trên các mạng xã hội trực tuyến đang là một

nguy cơ lớn đối với người dùng. Thông tin sai lệch lan truyền nhanh chóng trên

các mạng xã hội có thể đến từ sự chủ quan vô ý của người dùng hoặc được lan

truyền một cách có chủ đích với động cơ, mục đích không trong sáng. Do những

thiệt hại to lớn mà thông tin sai lệch gây ra đối với 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ây mất ổn định an ninh quốc gia, cho nên việc đưa ra một giải pháp hiệu quả

để ngăn chặn kịp thời sự lan truyền của thông tin sai lệch trên mạng xã hội trực

tuyến là việc làm hết sức cấp thiết nhằm giảm thiểu tối đa thiệt hai do chúng

gây ra đối với người dùng, góp phần làm trong sạch môi trường mạng, đồng thời

nâng cao sự tin tưởng của người dùng đối với những thông tin trên mạng xã hội.

Trong luận văn này, tác giả đề xuất một giải pháp ngăn chặn sự lan truyền

của thông tin sai lệch bằng cách tạo miễn dịch cho một số đỉnh trong đồ thị

mạng xã hội, từ đó hạn chế thông tin sai lệch lây lan sang những đỉnh khác.

Luận văn đã đạt được một số kết quả chính như sau:

• Tìm hiểu tổng quan về mạng xã hội, các đặc trưng cơ bản của mạng xã hội.

Tìm hiểu một số chủ đề nổi bật liên quan đến mạng xã hội đang nhận được

sự quan tâm nghiên cứu của nhiều học giả.

• Tìm hiểu cơ chế lan truyền thông tin và đặc tính của hai mô hình lan truyền

thông tin: Mô hình tầng độc lập (IC) và mô hình ngưỡng tuyến tính (LT).

Đặc biệt, tác giả tìm hiểu các hướng nghiên cứu liên quan đến bài toán hạn

chế thông tin sai lệch lan truyền trên mạng xã hội đã công bố.

• Đề xuấ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 và chứng minh bài toán này thuộc lớp NP-Khó,

đồng thời đề xuất hai thuật toán tham lam để giải quyết bài toán này. 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 Max Degree và thuật

toán Random trong việc hạn chế thông tin sai lệch lan truyền trên mạng.

Mặc dù đã cố gắng và nỗ lực hết mình, nhưng do thời gian nghiên cứu và

trình độ của bản thân có hạn nên luận văn không thể tránh khỏi những thiếu

53

sót và hạn chế, tác giả rất mong nhận được những ý kiến đóng góp để luận văn

đạt được kết quả tốt hơn.

Hướng phát triển:

Trong thời gian tới, tác giả đề xuất một số hướng phát triển của luận văn như

sau:

• Thiết kế thuật toán đạt tỉ lệ tối ưu cao hơn cho bài toán MDM. Cải tiến

thời gian chạy thuật toán, giúp thuật toán chạy nhanh hơn đối với các mạng

xã hội có quy mô lớn.

• Mở rộng phạm vi bài toán MDM xét với trường hợp mỗi đỉnh u ∈ V khi bị

kích hoạt bởi thông tin sai lệch sẽ gây ra những thiệt hai khác nhau, đồng

thời nghiên cứu bài toán trên các mô hình lan truyền thông tin khác.

• Trong luận văn, tác giả giả thiết rằng tập nguồn thông tin sai lệch S đã

được biết trước. Tuy nhiên, xác định được nguồn thông tin sai lệch ban đầu

là một vấn đề phức tạp, do vậy đây cũng là hướng nghiên cứu tiếp theo của

tác giả trong tương lai.

54

DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ

1. Manh M. Vu and Huan X. Hoang, Minimizing the Spread of Misinformation

on Online Social Networks with Time and Budget Constraint, In proceeding

of the 9th International Conference on Knowledge and Systems Engineering

(KSE 2017) (Notification of acceptance: July 30, 2017).

2. Canh V. Pham, Manh M. Vu and Huan X. Hoang, Preventing and Detecting

Infiltration on Online Social Networks, In proceeding of the 4th International

Conference on Computational Social Networks (CsoNet), 2015, pp. 60-73.

Tài liệu tham khảo

[1] H. Zhang, M. Alim, X. Li, M. T. Thai, and H. Nguyen. Misinformation

in Online Social Networks: Detect Them All with Limited Budget. ACM

Transactions on Information Systems, 2016, pp. 18:1-18:24.

[2] Ceren Budak, Divyakant Agrawal, Amr El Abbadi. Limiting the Spread of

Misinformation in Social Networks. In Proceedings of the 20th International

Conference on World Wide Web, 2011, pp. 665-674.

[3] H. Zhang, H. Zhang, X. Li, and M. T. Thai. Limiting the Spread of Misinfor-

mation while Effectively Raising Awareness in Social Networks. In Proceed-

ings of the 4th International Conference on Computational Social Networks,

2015, pp. 35-47.

[4] N. P. Nguyen, G. Yan, and M. T. Thai. Analysis of Misinformation Con-

tainment in Online Social Networks. Elsevier Computer Networks-Towards

a Science of Cyber Security, 2013, pp. 2133-2146.

[5] B. Aditya Prakash, Jilles Vreeken, and Christos Faloutsos. Spotting Culprits

in Epidemics: How many and Which ones?. In Data Mining (ICDM), 2012

IEEE 12th International Conference on. IEEE, 2012, pp. 11-20.

[6] V. Qazvinian, E. Rosengren, D. R. Radev, and Qiaozhu Mei. Rumor has

it: Identifying Misinformation in Microblogs. In Proc. EMNLP, 2011, pp.

1589-1599.

[7] S. Kwon, M. Cha, K. Jung, W. Chen, and Y. Wang. 2013. Prominent Fea-

tures of Rumor Propagation in Online Social Media. In Proc. ICDM, 2013,

pp. 1103-1108.

[8] Devavrat Shah and Tauhid Zaman. Rumors in a Network: Who’s the Cul-

prit?. IEEE Transactions on Information Theory, 2011, pp. 5163-5181.

[9] Vahed Qazvinian, Emily Rosengren, Dragomir R. Radev, and Qiaozhu Mei.

Rumor has it: Identifying Misinformation in Microblogs. In Proceedings of

the Conference on Empirical Methods in Natural Language Processing, 2011,

55

pp. 1589-1599.

56

[10] Sejeong Kwon, Meeyoung Cha, Kyomin Jung, Wei Chen, and Yajun Wang.

Prominent Features of Rumor Propagation in Online Social Media. In Data

Mining (ICDM), 2013 IEEE 13th International Conference on. IEEE, 2013,

pp. 1103-1108.

[11] Kai Zhu and Lei Ying. 2014. A Robust Information Source Estimator with

Sparse Observations. Computational Social Networks, 2014, pp. 1-21.

[12] Wuqiong Luo, Wee Peng Tay, and Mei Leng. Identifying Infection Sources

and Regions in Large Networks. IEEE Transactions on Signal Processing,

2013, pp. 2850-2865.

[13] H. Nguyen and R. Zheng. On budgeted Influence Maximization in Social

Networks. IEEE Journal on Selected Areas in Communications, 2013, pp.

1084-1094.

[14] Mạng xã hội nhận diện thông tin xấu độc. Truy xuất từ

http://dangcongsan.vn/dien-dan/mang-xa-hoi-nhan-dien-thong-tin-xau-

doc-434891.html [Ngày truy cập 22/5/2017].

[15] Bimal Viswanath, Alan Mislove, Meeyoung Cha, Krishna P. Gummadi. On

the Evolution of User Interaction in Facebook. In Proceedings of the 2nd

ACM Workshop on Online Social Networks, 2009, pp. 37-42.

[16] N. P. Nguyen, M. A. Alim, T. N. Dinh, and M. T. Thai. A Method to Detect

Communities with Stability in Social Networks. Social Network Analysis and

Mining, 2014, pp. 224:1-224:15.

[17] N. P. Nguyen, G. Yan, M. T. Thai, and S. Eidenbenz. Containment of Mis-

information Spread in Online Social Networks. In Proceedings of the 4th

Annual ACM Web Science Conference, 2012, pp. 213-222.

[18] H. Zhang, M. Alim, M. T. Thai, and H. Nguyen. Monitor Placement to

Timely Detect Misinformation in Online Social Networks. In Proceedings

of the 2015 IEEE International Conference on Communications, 2015, pp.

1152-1157.

[19] H. Zhang, H. Zhang, X. Li, and M. T. Thai. Limiting the Spread of Misinfor-

mation while Effectively Raising Awareness in Social Networks. In Proceed-

ings of the 4th International Conference on Computational Social Networks,

2015, pp. 35-47.

57

[20] T. N. Dinh, H. Zhang, D. T. Nguyen, and M. T. Thai. Cost-Effective Vi-

ral Marketing for Time-Critical Campaigns in Large-Scale Social Networks.

IEEE/ACM Transactions on Networking, 2014, pp. 2001-2011.

[21] Wei Chen, Wei Lu, and Ning Zhang. Time-Critical Influence Maximization

in Social Networks with Time-Delayed Diffusion Process. In Proc. AAAI,

2012, pp. 1-5.

[22] Santo Fortunato. Community Detection in Graphs. Physics reports, 2010,

pp. 75-174.

[23] Misinformation on Social Media: Can Technology Save Us?. Avail-

able at https://www.usnews.com/news/national-news/articles/2016-11-

28/misinformation-on-social-media-can-technology-save-us [Accessed 12

May 2017].

[24] Việt Nam sắp đổi tiền: Hoàn toàn bịa đặt. Truy xuất từ

http://vietnamnet.vn/vn/kinh-doanh/tai-chinh/viet-nam-sap-doi-tien-

hoan-toan-bia-dat-342761.html [Ngày truy cập 21/5/2017].

[25] Bác thông tin tăng lệ phí cấp hộ chiếu tại Việt Nam. Truy xuất

từ http://dantri.com.vn/xa-hoi/bac-thong-tin-tang-le-phi-cap-ho-chieu-tai-

viet-nam-20161209192924661.htm [Ngày truy cập 21/5/2017].

[26] D. Kempe, J. Kleinberg, and E. Tardos. Influential Nodes in a Diffusion

Model for Social Networks. In ICALP, 2005, pp. 1127-1138.

[27] J. Goldenberg, B. Libai, and E. Muller. Talk of the Network: A Complex Sys-

tems Look at the Underlying Process of Word-of-Mouth. Marketing Letters,

2001, pp. 211-223.

[28] J. Leskovec, M. Mcglohon, C. Faloutsos, N. Glance, and M. Hurst. Cas-

cading Behavior in Large Blog Graphs. In Proceedings of the 2007 SIAM

International Conference on Data Mining, 2007, pp. 551-556.

[29] T. Carnes, R. Nagarajan, S. M. Wild, and A. V. Zuylen. Maximizing Influ-

ence in a Competitive Social Network: a Follower’s Perspective. In Proceed-

ings of the Ninth International Conference on Electronic Commerce, 2007,

pp. 351-360.

58

[30] Alexandra Marin and Barry Wellman. Social Network Analysis: An Intro-

duction. The SAGE Handbook of Social Network Analysis, 2011, pp. 11-25.

[31] Jiyang Chen. Community Mining: Discovery Communities in Social Net-

work. Thesis, University of Alberta, 2010.

[32] Jon Kleinberg. Authoritative Sources in a Hyperlinked Environment. Journal

of the ACM, 1999, pp. 604-632.

[33] Jurij Lescovec. Dynamics of Large Networks. Carnegie Mellon University,

2008.

[34] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs Over Time:

Densification Laws, Shrinking Diameters and Possible Explanations. In Pro-

ceedings of the Eleventh ACM SIGKDD International Conference on Knowl-

edge Discovery in Data Mining,2005, pp. 177-187.

[35] Charu C. Aggarwal. Social Network Data Analytics. New York: Springer,

2011.

[36] M. E. J. Newman. Modularity and Community Structure in Networks. In

Proceedings of the National Academy of Sciences, 2006, pp. 8577-8582.

[37] R. Guimera, M. Sales-Pardo. Missing and Spurious Interactions and the Re-

construction of Complex Ntworks. In Proceedings of the National Academy

of Sciences, 2009, pp. 22073-22078.

[38] Steve Gregory. Finding Overlapping Communities Using Disjoint Commu-

nity Detection Algorithms. Complex networks, 2009, pp. 47-61.

[39] Leskovec, Huttenlocher, and Kleinberg. Predicting Positive and Negative

Links in Online Social Networks. In Proceedings of the 19th International

Conference on World Wide Web, 2010, pp. 641-650.

[40] Linyuan Lu, Tao Zhou. Link Prediction in Complex Networks: A Survey.

Physica A: Statistical Mechanics and Its Applications, 2011, pp. 1150-1170.

[41] Zhihao Wu, Youfang Lin, Jing Wang, Steve Gregory. Efficient Link Pre-

diction with Node Clustering Coefficient. arXiv preprint arXiv:1510.07819,

2015.

59

[42] T. N. Dinh, Y. Shen, and M. T. Thai. The Walls Have Ears: Optimize

Sharing for Visibility and Privacy in Online Social Networks. In Proceedings

of ACM Int Conference on Information and Knowledge Management, 2012,

pp. 1452-1461.

[43] Y. Shen, Y-S. Syu, D. T. Nguyen, and M. T. Thai. Maximizing Circle of

Trust in Online Social Networks. In Proceedings of ACM Conference on

Hypertext and Social Media, 2012, pp. 155-164.

[44] Y. Shen, M. T. Thai, and H. Nguyen. Staying Safe and Visible via Message

Sharing in Online Social Networks. Journal of Combinatorial Optimization,

2014, pp. 186-217.

[45] J. Leskovec, L. Backstrom, R. Kumar, A. Tomkins. Microscopic Evolution

of Social Networks. In Proc. KDD, 2008, pp. 462-470.

[46] J. Leskovec, J. Kleinberg, C. Faloutsos. Graph Evolution: Densification and

Shrinking Diameters. ACM TKDD, 2007.

[47] D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the Spread of Influence

through a Social Network. In Proceedings of the Ninth ACM SIGKDD In-

ternational Conference on Knowledge Discovery and Data Mining, 2003, pp.

137–146.

[48] Huiyuan Zhang, Thang N. Dinh, and My T. Thai. Maximizing the Spread

of Positive Influence in Online Social Networks. In Distributed Computing

Systems (ICDCS), 2013 IEEE 33rd International Conference on. IEEE, 2013,

pp. 317-326.

[49] J Zhang, P Zhou, C Cao, Y Guo L . Personalized Influence Maximization on

Social Networks. In Proceedings of the 22nd ACM International Conference

on Information and Knowledge Management, 2013, pp. 199-2008.

[50] Honglei Zhuang, Yihan Sun, Jie Tang, Jialin Zhangz and Xiaoming Sunz. In-

fluence Maximization in Dynamic Social Networks. In Data Mining (ICDM),

2013 IEEE 13th International Conference on. IEEE, 2013, pp. 1313-1318.

[51] A. Goyal, F. Bonchi, and L. V. S. Lakshmanan. Learning Influence Proba-

bilities in Social Networks. In Proceedings of the third ACM International

Conference on Web Search and Data Mining, 2010, pp. 241-250.

60

[52] How bin Laden news spread on Twitter. Available at

http://edition.cnn.com/2011/TECH/social.media/05/02/osama.bin.laden.

twitter/index.html [Accessed 16 April 2017].

[53] Twitter Breaks News of Whitney Houston Death 27 Minutes Be-

fore Press. Available at http://mashable.com/2012/02/12/whitney-houston-

twitter/ [Accessed 16 April 2017].

[54] Hackers send fake market-moving AP tweet on White House explo-

sions. Available at http://www.reuters.com/article/net-us-usa-whitehouse-

ap-idUSBRE93M12Y20130423 [Accessed 16 April 2017].

[55] A. Goyal, W. Lu, and L. V. S. Lakshmanan. Simpath: An Efficient Algorithm

for Influence Maximization under the Linear Threshold Model. In Proc.

ICDM, 2011, pp. 211-220.

[56] Swine Flu Frenzy Demonstrates Twitter’s Achilles Heel. Available

at http://www.pcworld.com/businesscenter/article/163920/swine flufrenzy

demonstratest-witters achillesheel.html [Accessed 22 April 2017].

[57] Fan, L., Lu, Z., Wu, W., Thuraisingham, B., Ma, H., and Bi, Y. Least Cost

Rumor Blocking in Social Networks. In Distributed Computing Systems,

2013 IEEE 33rd International Conference on. IEEE, 2013, pp. 540-549.

[58] Karlova, Natascha, Fisher Karen. A Social Diffusion Model of Misinforma-

tion and Disinformation for Understanding Human Information Behaviour.

Information Research, 2013, pp. 1-17.

[59] Liang Wu, Fred Morstatter, Huan Liu. Misinformation in Social Media: Dif-

fusion, Detection and Intervention. SBP-BRIMS 2016 Tutorial.

[60] Wei Chen, Laks V.S. Lakshmanan, and Carlos Castillo. Information and

Influence Propagation in Social Networks. A Publication in the Morgan &

Claypool Publishers series Synthesis Lectures on Data Management, 2014.

[61] Wei Chen, Yifei Yuan, and Li Zhang. Scalable Influence Maximization in

Social Networks under the Linear Threshold Model. In Data Mining (ICDM),

2010 IEEE 10th International Conference on. IEEE, 2010, pp. 88-97.

61

[62] Pedro Domingos and Matthew Richardson. Mining the Network Value of

Customers. In Proceedings of the Seventh ACM SIGKDD International Con-

ference on Knowledge Discovery and Data Mining, 2001, pp. 57-66.

[63] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, N. Glance.

Cost-Effective Outbreak Detection in Networks. In Proc. KDD, 2007, pp.

420-429.

[64] A. Goyal, W. Lu, L. V.S. Lakshmanan. Celf++: Optimizing the Greedy

Algorithm for Onfluence Maximization in Social Networks. In Proc. WWW,

2011, pp. 47-48.

[65] D. T. Nguyen, N. P. Nguyen, and M. T. Thai. Sources of Misinformation

in Online Social Networks: Who to Suspect?. In Proceedings of the IEEE

Military Communications Conference, 2012, pp. 1-6.

[66] Kempe, 2008. Design and Analysis of Algorithms. Available at http://www-

bcf.usc.edu/ dkempe/CS303/solutions13.pdf [Accessed 22 May 2017].

62

PHỤ LỤC

Algorithm 4: Thuật toán Max Degree

1

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. begin

2

3

4

5

I ← ∅; N ← Nd(S); C ← 0; while (C < B) and (N (cid:54)= ∅) do

6

7

8

9

u ← maxdegree(N ); //Chọn ra đỉnh có bậc lớn nhất trong tập N để tạo miễn dịch if C + c(u) ≤ B then I ← I ∪ {u}; C ← C + c(u);

10

11

end N ← N \{u};

12

13

end Return I;

14

end

Algorithm 5: Thuật toán Random

1

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. begin

2

3

4

5

I ← ∅; N ← Nd(S); C ← 0; while (C < B) and (N (cid:54)= ∅) do

6

7

8

9

u ← random(N ); //Chọn ngẫu nhiên đỉnh trong tập N để tạo miễn dịch if C + c(u) ≤ B then I ← I ∪ {u}; C ← C + c(u);

10

11

end N ← N \{u};

12

13

end Return I;

14

end