Tóm tắt Luận văn Thạc sĩ: 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 . . . . . . . . . . . . . . 5

1.1.2 Những tính năng của mạng xã hội . . . . . . . . . . . . . . 5

1.2 Các đặc trưng cơ bản của mạng xã hội . . . . . . . . . . . . . . . . 5

1.2.1 Đặc trưng thế giới nhỏ . . . . . . . . . . . . . . . . . . . . . 5

1.2.2 Đặc trưng tập nhân . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.3 Phân bố luật lũy thừa . . . . . . . . . . . . . . . . . . . . . 6

1.2.4 Đặc trưng cấu trúc cộng đồng . . . . . . . . . . . . . . . . . 6

1.2.5 Các đặc trưng khác của mạng xã hội . . . . . . . . . . . . . 6

1.3 Một số chủ đề được nghiên cứu trên mạng xã hội . . . . . . . . . . 7

1.3.1 Phát hiện cấu trúc cộng đồng trên mạng xã hội . . . . . . 7

1.3.2 Dự đoán liên kết trên mạng xã hội . . . . . . . . . . . . . . 7

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

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

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

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

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

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

THÔNG TIN SAI LỆCH 8

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

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

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

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

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

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 12

3.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.2 Độ khó của bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.3 Các thuật toán đề xuất giải quyết bài toán MDM . . . . . . . . . 14

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

3.3.2 Thuật toán tham lam dựa trên hàm α(v) . . . . . . . . . . 16

4 THỰC NGHIỆM 18

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

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

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

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

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

KẾT LUẬN 24

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

PHỤ LỤC 33

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

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.

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

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

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.

- Tính đa phương tiện.

- Tính tương tác.

- Khả năng truyền tải và lưu trữ thông tin.

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

6

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.

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.

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.

1.2.4 Đặc trưng cấu trúc cộng đồng

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

có những cộng đồng con nhỏ hơn. Giữa các nút trong một cộng đồng có mật độ

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

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.

7

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

1.3.2 Dự đoán liên kết trên mạng xã hội

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

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

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

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

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

8

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

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.

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

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.

9

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

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.

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

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

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á

10

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.

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]. 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:

Đị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.3)

σ(S0)

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

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

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

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

11

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

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.

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

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.

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

12

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

Mô hình hóa bài toán

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)

13

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

14

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

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

3.3 Các thuật toán đề xuất giải quyết bài toán MDM

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

15

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 (I)

d (∅) − DS

d (I) = DS

d − DS

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

như là một hàm mục tiêu thay thế trong bài toán MDM, thuật toán tác giả đề

xuất hoạt động dựa trên việc bổ sung dần tập I theo kiểu ăn tham.

Ý tưởng thuật toán: Khởi tạo I = ∅, tiếp theo thực hiện lặp việc chọn đỉnh

v ∈ Nd(S) sao cho hàm f (I ∪ {v}) đạt giá trị lớn nhất, nếu tổng chi phí hiện tại để tạo miễn dịch chưa vượt ngưỡng ngân sách B thì bổ sung v vào I, ngược lại

thì dừng và trả về kết quả tập I. Quá trình này kết thúc khi tổng chi phí để tạo

miễn dịch cho tập đỉnh I vượt ngưỡng ngân sách B đã cho hoặc đã xét hết tất

cả các đỉnh trong tập Nd(S). Chi tiết thuật toán được đặc tả trong phần giả mã của Thuật toán 5.

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

16

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

Input : G = (V, E), w(u, v), d, B, tập nguồn phát thông tin sai lệch S. Output: Tập đỉnh I là lời giải của bài toán MDM. begin

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

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

end N ← N \{u};

end Return I;

end

d (I) bằng pháp mô phỏng Mote Carlo quá trình lan truyền

lượng giá trị hàm DS

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

d (I)

d (I).

Input : G = (V, E), w(u, v), tập nguồn phát thông tin sai lệch S, tập đỉnh I tạo miễn dịch. Output: Giá trị ước lượng hàm DS begin

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

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;

end Return count/R;

end

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.

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,

17

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.

Algorithm 3: Thuật toán tham lam dựa trên hàm α(v)

Input : G = (V, E), w(u, v), d, B, tập nguồn phát thông tin sai lệch S. Output: Tập đỉnh I là lời giải của bài toán MDM. begin

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

α(v) =

, ∀v ∈ N ;

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

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

end N ← N \{u};

end Return I;

end

18

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

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:

19

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.

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,

20

đố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.

(a) Email

(b) CollegeMsg

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

21

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.

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

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

22

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

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

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.

23

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.

24

KẾT LUẬN

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.

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ư

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

25

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,

pp. 1589-1599.

27

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

28

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

29

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

30

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

31

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

32

[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].

33

PHỤ LỤC

Algorithm 4: Thuật toán Max Degree

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

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

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

end N ← N \{u};

end Return I;

end

Algorithm 5: Thuật toán Random

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

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

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

end N ← N \{u};

end Return I;

end