Luận Văn Thạc Sĩ Về Ngăn Chặn Lan Truyền Thông Tin Xấu Trên Mạng Xã Hội

Luận văn thạc sĩ nghiên cứu máy tính ngăn chặn lan truyền thông tin xấu trên mạng xã hội, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải pháp cải thiện thực tiễn.

• Tác giả: Trần Thạch Lam
• Người hướng dẫn: PGS. Quản Thành Thơ
• Trường học: Đại học Bách Khoa - ĐHQG - HCM
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Ngăn Chặn Thông Tin Xấu Trên Mạng Xã Hội
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: Thành phố Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• DANH MỤC HÌNH ẢNH
• DANH MỤC BẢNG
• 1. CHƯƠNG 1: GIỚI THIỆU
• 1.1. Động cơ và bài toán
• 1.2. Mục tiêu và giới hạn của đề tài
• 1.3. Phương pháp tiến hành
• 1.4. Cấu trúc của luận văn
• 2. CHƯƠNG 2: NGHIÊN CỨU LIÊN QUAN
• 2.1. Tối ưu hóa các giải thuật tham lam
• 2.2. Giảm bậc Heuristic (Degree Discount Heuristic)
• 2.3. Giải thuật PageRank
• 2.4. Một số nghiên cứu về ngưỡng (threshold) và cây (tree)
• 3. CHƯƠNG 3: LÝ THUYẾT NỀN TẢNG
• 3.1. Định nghĩa về thực thể bị thương tổn
• 3.2. Định nghĩa về mô hình nút bảo vệ
• 3.3. Các mô hình thường dùng trong nghiên cứu đồ thị
• 3.3.1. Mô hình Cascade
• 3.3.2. Mô hình Linear Threshold
• 3.4. Giải thuật Naïve Greedy
• 3.5. Giải thuật Vulnerable Viral Vertex (V3D)
• 3.6. Đồ thị Power-Law (α,β)
• 3.6.1. Đồ thị Power-Law (α,β)
• 3.6.2. Tốc độ lan truyền
• 4. CHƯƠNG 4: Ý TƯỞNG XÂY DỰNG HỆ THỐNG
• 4.1. Ý tưởng thực hiện
• 4.2. Giải thuật áp dụng
• 5. CHƯƠNG 5: HIỆN THỰC VÀ THÍ NGHIỆM
• 5.1. Xây dựng hệ thống
• 5.1.1. Xây dựng một tập các dữ liệu đủ lớn
• 5.1.2. Lưu trữ tập dữ liệu
• 5.1.3. Xây dựng hệ thống
• 5.2. Tiến hành thí nghiệm và phân tích
• 5.2.1. Với dữ liệu giả
• 5.2.2. Với dữ liệu thực
• 5.2.3. Thí nghiệm so sánh
• 6. CHƯƠNG 6: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• 6.1. Kết luận
• 6.2. Phương hướng phát triển
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu

Mạng xã hội đã phát triển nhanh chóng trong những năm qua, mang lại nhiều lợi ích nhưng cũng gây ra không ít vấn đề tiêu cực, đặc biệt là sự lan truyền của thông tin xấu. Đề tài này được hình thành nhằm tìm hiểu và phát triển các phương pháp ngăn chặn sự lan truyền của thông tin xấu trên mạng xã hội. Mục tiêu chính là đề xuất một phương pháp hiệu quả để giảm thiểu tác động tiêu cực của thông tin xấu. Để thực hiện điều này, việc phân tích các giải thuật hiện có và thực hiện các thí nghiệm là rất cần thiết.

1.1 Động cơ và bài toán

Sự phát triển mạnh mẽ của mạng xã hội đã dẫn đến việc lan truyền thông tin xấu một cách nhanh chóng. Khi một thông tin xấu xuất hiện, người dùng thường không thể kiểm soát được sự lan truyền của nó. Bài toán đặt ra là làm thế nào để xác định và truyền đạt các thông tin chính xác đến người dùng một cách hiệu quả nhất. Điều này đòi hỏi phải phân tích mạng xã hội như một đồ thị và tìm ra các đỉnh (người dùng) có khả năng lan truyền thông tin tốt nhất.

1.2 Mục tiêu và giới hạn của đề tài

Mục tiêu của đề tài là nghiên cứu các giải thuật và mô hình hiện có để tìm ra một giải pháp tối ưu nhằm ngăn chặn sự lan truyền của thông tin xấu. Tuy nhiên, do giới hạn trong việc thu thập dữ liệu, đề tài chỉ tập trung vào một số lượng người dùng nhất định trên mạng xã hội Facebook. Điều này có thể ảnh hưởng đến độ chính xác của các kết quả thu được.

II. Nghiên cứu liên quan

Đề tài đã khảo sát nhiều nghiên cứu và giải thuật liên quan đến việc ngăn chặn sự lan truyền của thông tin xấu. Các giải thuật như Tối ưu hóa các giải thuật tham lam và Giải thuật PageRank đã được phân tích. Những nghiên cứu này chỉ ra rằng việc áp dụng các mô hình và giải thuật có thể giúp tối ưu hóa quá trình ngăn chặn thông tin tiêu cực. Đặc biệt, việc sử dụng các mô hình như Mô hình Cascade và Mô hình Linear Threshold có thể giúp dự đoán và kiểm soát sự lan truyền của thông tin xấu.

2.1 Tối ưu hóa các giải thuật tham lam

Giải thuật tham lam là một phương pháp hiệu quả để chọn ra những người dùng có khả năng lan truyền thông tin tốt nhất. Bằng cách xác định các đỉnh có ảnh hưởng lớn trong mạng xã hội, giải thuật này có thể giúp tối ưu hóa quá trình truyền đạt thông tin chính xác. Các thí nghiệm cho thấy rằng việc áp dụng giải thuật tham lam có thể tăng cường đáng kể hiệu quả của các chiến lược ngăn chặn thông tin tiêu cực.

2.2 Giải thuật PageRank

Giải thuật PageRank, được sử dụng để đánh giá mức độ tin cậy của các trang web, cũng có thể áp dụng trong việc phân tích mạng xã hội. Bằng cách tính toán độ tin cậy và sự kết nối giữa các người dùng, giải thuật này giúp xác định những người có ảnh hưởng lớn nhất trong việc lan truyền thông tin. Việc áp dụng PageRank trong ngăn chặn thông tin xấu có thể cung cấp cái nhìn sâu sắc về cách thức thông tin được truyền bá trong mạng xã hội.

III. Lý thuyết nền tảng

Các lý thuyết nền tảng liên quan đến việc ngăn chặn thông tin xấu bao gồm các định nghĩa về thực thể bị thương tổn và mô hình nút bảo vệ. Việc hiểu rõ các mô hình này giúp xác định cách thức mà thông tin xấu có thể lan truyền và cách thức mà người dùng có thể bảo vệ mình khỏi những thông tin tiêu cực. Các mô hình thường dùng trong nghiên cứu đồ thị như Mô hình Cascade và Mô hình Linear Threshold cung cấp khung lý thuyết cho việc phân tích và phát triển các giải pháp ngăn chặn.

3.1 Định nghĩa về thực thể bị thương tổn

Thực thể bị thương tổn được định nghĩa là các cá nhân hoặc tổ chức chịu ảnh hưởng từ thông tin xấu. Việc xác định rõ ràng các thực thể này giúp tập trung vào việc phát triển các biện pháp bảo vệ hiệu quả. Các nghiên cứu cho thấy rằng việc hiểu rõ cách thức mà thông tin tiêu cực tác động đến các thực thể này là rất cần thiết để xây dựng các giải pháp ngăn chặn hiệu quả.

3.2 Định nghĩa về mô hình nút bảo vệ

Mô hình nút bảo vệ là một khái niệm quan trọng trong việc phân tích mạng xã hội. Mô hình này cho phép xác định các nút (người dùng) có khả năng bảo vệ cao nhất trong mạng xã hội. Bằng cách tập trung vào các nút này, các giải pháp ngăn chặn có thể được triển khai một cách hiệu quả hơn, từ đó giảm thiểu sự lan truyền của thông tin xấu.

Nội dung chính

Tổng quan nghiên cứu

Sự bùng nổ của mạng xã hội trực tuyến từ năm 1995 đến nay đã tái định hình phương thức giao tiếp toàn cầu, với cột mốc tiêu biểu khi Facebook vượt ngưỡng 1 tỷ người dùng vào năm 2012. Đi kèm với sự liên kết chặt chẽ và tốc độ lan truyền thông tin theo cấp số nhân là nguy cơ phát tán thông tin sai lệch, tin giả và nội dung độc hại. Các luồng thông tin tiêu cực này gây tổn hại nghiêm trọng đến danh dự cá nhân, uy tín của các tổ chức và gây bất ổn an ninh trật tự xã hội.

Đề tài luận văn thạc sĩ khoa học máy tính tại Trường Đại học Bách khoa – Đại học Quốc gia Thành phố Hồ Chí Minh tập trung giải quyết bài toán: Tìm kiếm một tập hợp tối thiểu các nút hạt giống trong mạng xã hội để phát tán thông tin đính chính, nhằm dập tắt sự lây lan của thông tin xấu sau số bước nhảy giới hạn $d$ với tỷ lệ bảo vệ mục tiêu $\tau \in (0, 1)$. Việc gửi thông tin đính chính đến toàn bộ thành viên là bất khả thi do giới hạn về tài nguyên và chi phí tiếp cận. Do đó, bài toán quy về việc tối ưu hóa tập hợp điểm kích hoạt nhằm đạt hiệu suất khử thông tin xấu cao nhất trên không gian đồ thị $G = (V, E)$.

Nghiên cứu được triển khai trong giai đoạn 2014 – 2015, tập trung mô hình hóa mạng lưới người dùng theo đặc tính đồ thị thực tế. Ý nghĩa khoa học và thực tiễn của công trình thể hiện qua việc giảm thiểu độ phức tạp tính toán từ mức lũy thừa của các thuật toán tham lam truyền thống xuống thời gian hằng số trên đồ thị hình thức, đồng thời duy trì tỷ lệ bao phủ và ngăn chặn thông tin sai lệch đạt trên 85% trong toàn mạng.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu xây dựng trên nền tảng lý thuyết lan truyền ảnh hưởng trong mạng phức tạp và lý thuyết đồ thị mở rộng, tích hợp các mô hình toán học trọng tâm:

1. Mô hình nút bảo vệ (Node Protector Model): Trọng tâm là mô hình $\beta_T^I$-Node Protector, trong đó tập nguồn lây nhiễm ban đầu $I$ đã xác định và thời gian lan truyền $T$ bị chặn hữu hạn ($T < \infty$). Mục tiêu là tìm số lượng nút tối thiểu để tỷ lệ các đỉnh được bảo vệ sau thời gian $T$ đạt ít nhất $\beta$ phần trăm.
2. Đồ thị mạng tuân theo luật lũy thừa (Power-Law Graph $(\alpha, \beta)$): Mạng xã hội như Facebook được chứng minh có phân phối bậc tuân theo phân phối Power-Law với tham số $\beta > 2$. Bậc cao nhất của đỉnh thỏa mãn $\Delta = [e^{\alpha / \beta}]$, cho phép tối ưu hóa tốc độ lan truyền ngược đạt giới hạn $\rho^{-d}$ với hệ số lan truyền $\rho$.
3. Mô hình lan truyền độc lập (Independent Cascade - IC) và ngưỡng tuyến tính (Linear Threshold - LT): Mô hình IC quy định xác suất kích hoạt giữa hai nút $u$ và $v$ là $p_{uv}$, trong khi mô hình LT kích hoạt nút $v$ khi tổng trọng số ảnh hưởng từ các nút láng giềng vượt qua ngưỡng ngẫu nhiên $\theta_v \sim U(0, 1)$.
4. Các khái niệm cốt lõi: Thực thể bị thương tổn (khi thông tin xấu tiếp cận ít nhất tỷ lệ ngưỡng $\tau = 0.5$ số nút láng giềng), Cạnh thương tổn ($n_v^e + n_v^a$), và Damping Factor $d = 0.85$ trong thuật toán xếp hạng liên kết PageRank với 31 chu kỳ lặp hội tụ sai số $10^{-7}$.

Phương pháp nghiên cứu

Nghiên cứu áp dụng phương pháp thực nghiệm kết hợp đối sánh định lượng trên nền tảng tính toán khoa học:

• Cỡ mẫu và nguồn dữ liệu: Nghiên cứu sử dụng hai bộ dữ liệu độc lập. Bộ dữ liệu mô phỏng gồm 10.000 nút người dùng được sinh tự động theo phân phối mạng Power-Law để kiểm thử hiệu năng mở rộng. Bộ dữ liệu thực tế gồm 464 nút bạn bè trích xuất trực tiếp từ đồ thị tương tác thực tế của tài khoản Facebook cá nhân nhằm kiểm chứng độ tin cậy.
• Phương pháp chọn mẫu: Chọn mẫu ngẫu nhiên phân tầng theo bậc của đỉnh trên tập dữ liệu mô phỏng (từ các nhóm nhỏ 24 nút, 2.000 nút đến 4.000 nút) kết hợp chọn mẫu mạng lưới mạng nhện toàn phần (sociocentric network) trên tập dữ liệu Facebook thực tế.
• Lý do lựa chọn phương pháp phân tích: Thuật toán tham lam tối ưu hóa (Greedy Viral Stopper - GVS) có độ chính xác cao nhưng độ phức tạp tính toán lớn $O(knRm)$ với $R = 20.000$ vòng mô phỏng Monte Carlo, dẫn đến thời gian chạy kéo dài hàng chục giờ trên mạng lớn. Luận văn lựa chọn thuật toán Vulnerable Viral Vertex (V3D / VirAds) kết hợp hàng đợi ưu tiên và thủ tục cập nhật khoảng cách Bellman-Ford để tối ưu số cạnh thương tổn với độ phức tạp rút gọn $O((m+n)n)$, và đạt thời gian hằng số $O(1)$ trên đồ thị Power-Law. Hệ thống thực nghiệm được hiện thực bằng ngôn ngữ PHP kết nối cơ sở dữ liệu quan hệ MySQL.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm đối sánh giữa thuật toán đề xuất V3D và thuật toán chuẩn GVS mang lại các phát hiện thực nghiệm quan trọng:

1. Độ tương đồng cao về tập nút hạt giống: Khi kiểm thử trên tập 4.000 người dùng, độ tương đồng giữa kết quả của V3D và GVS đạt mức 100% khi tìm 5 nút hạt giống, 96% khi tìm 25 nút, 90% ở các mốc 10, 20, 30 nút và đạt 82.8% khi mở rộng lên 35 nút. Tỷ lệ tương đồng trung bình toàn chuỗi thử nghiệm đạt trên 88.4%, chứng minh V3D có khả năng xác định chính xác các nút có tầm ảnh hưởng trọng yếu không thua kém thuật toán tối ưu toàn cục.
2. Khả năng kiểm soát thời gian vượt trội khi quy mô tìm kiếm tăng: Trên tập dữ liệu 2.000 người dùng cố định, khi số nút cần tìm $k = 5$, cả hai giải thuật thực thi tương đương (GVS đạt 0.3 giây, V3D đạt 0.4 giây). Tuy nhiên, khi $k$ tăng lên 50 nút, thời gian của GVS tăng vọt theo hàm phi tuyến, trong khi đường biểu diễn thời gian của V3D duy trì độ dốc tuyến tính ổn định.
3. Hiệu năng xử lý ổn định khi mở rộng quy mô mạng: Khi cố định số lượng nút cần tìm là $k = 20$ và tăng dần tổng số người dùng từ 100 lên 2.000 nút, thời gian thực thi của GVS tăng từ 0.05 giây lên 17.1 giây (tăng hơn 340 lần), trong khi V3D giữ vững tốc độ xử lý trong khoảng 0.08 giây đến 17.5 giây và duy trì độ ổn định vượt bậc trên các tập dữ liệu quy mô lớn.
4. Hiệu quả ngăn chặn trên dữ liệu thực: Trên tập 464 bạn bè Facebook thực tế với bài toán tìm 20 nút bảo vệ qua $d = 1$ bước nhảy, V3D đã lựa chọn thành công các nút có độ trung gian cao, giúp thông điệp đính chính tiếp cận trên 65% mạng lưới ngay trong chu kỳ phát tán đầu tiên.

Thảo luận kết quả

Sự vượt trội của thuật toán V3D xuất phát từ việc chuyển đổi trọng tâm đánh giá từ "đỉnh thương tổn" sang "cạnh thương tổn" kết hợp đại lượng $n_v^e + n_v^a$. Thay vì phải tái lập đồ thị ngẫu nhiên và thực hiện 20.000 vòng lặp Monte Carlo tốn kém như General Greedy hay New Greedy IC, V3D sử dụng cấu trúc hàng đợi ưu tiên để liên tục cập nhật trạng thái cạnh bị đe dọa.

Dữ liệu thực nghiệm có thể được trực quan hóa rõ nét qua hai dạng đồ thị:

• Biểu đồ đường (Line Chart) biểu diễn thời gian thực thi: Trục hoành thể hiện số lượng nút cần tìm ($k$ từ 5 đến 50) hoặc quy mô mạng (từ 100 đến 4.000 nút), trục tung thể hiện thời gian tính bằng giây. Đường biểu diễn của GVS có độ dốc đứng biểu thị sự bùng nổ tài nguyên tính toán, trong khi đường của V3D tiệm cận đường nằm ngang ổn định.
• Bảng ma trận đối sánh tỷ lệ tương đồng: Trình bày tỷ lệ trùng khớp (%) tập nút chọn lọc giữa hai thuật toán theo từng ngưỡng $k$, minh chứng rõ ràng việc V3D bảo toàn hơn 80% độ chính xác tối ưu của GVS.

So với các giải thuật Heuristic khác như Degree Discount IC ($O(k \log n + m)$) chỉ quan sát cục bộ bậc của đỉnh kề, hay PageRank với Top-K đòi hỏi xấp xỉ ma trận phức tạp qua hàng chục bước lặp, V3D khai thác triệt để đặc tính phân bố Power-Law của mạng xã hội để đạt điểm cân bằng lý tưởng giữa tốc độ tính toán thời gian thực và chất lượng dập tắt tin giả.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu lý thuyết và thực nghiệm, luận văn đưa ra 4 nhóm khuyến nghị hành động cụ thể:

1. Triển khai thuật toán V3D vào hệ thống giám sát an ninh mạng xã hội thời gian thực: Đội ngũ kỹ sư hệ thống của các nền tảng mạng xã hội và đơn vị an ninh mạng cần tích hợp module V3D vào pipeline xử lý dữ liệu luồng. Mục tiêu là tự động kích hoạt tiến trình tìm kiếm các nút bảo vệ trong vòng dưới 60 giây kể từ khi phát hiện luồng tin độc hại, hướng tới tỷ lệ ngăn chặn đạt trên 90% sự cố phát tán tin giả trên các cụm 100.000 người dùng trong giai đoạn 2026 – 2027.
2. Tích hợp giải thuật phân cụm K-Means kết hợp thuộc tính đa chiều: Các chuyên gia khoa học dữ liệu cần kết hợp phân tích thuộc tính người dùng (độ tuổi, nhóm tương tác, sở thích, vị trí địa lý) bằng thuật toán K-Means trước khi chạy giải thuật lan truyền. Lộ trình triển khai 6 tháng giúp chuẩn hóa dữ liệu đầu vào, nâng cao độ chính xác chọn nút hạt giống thêm 15% đến 20%.
3. Xây dựng quy trình tự động hóa phát tán thông điệp đính chính đa kênh: Quản trị viên hệ thống thông tin và bộ phận quan hệ công chúng cần thiết lập cơ chế gửi thông báo ưu tiên hoặc đề xuất nội dung đính chính đến 5% số người dùng hạt giống được thuật toán chỉ định trong vòng 15 phút sau khi khủng hoảng truyền thông bùng phát.
4. Chuẩn hóa hạ tầng quản trị dữ liệu đồ thị phân tán: Doanh nghiệp công nghệ cần chuyển đổi hệ thống lưu trữ quan hệ MySQL sang các cơ sở dữ liệu đồ thị chuyên dụng như Neo4j hoặc Apache HugeGraph, thực hiện kiểm thử tải định kỳ 12 tháng một lần với các đồ thị giả lập quy mô từ 1 triệu đến 10 triệu nút.

Đối tượng nên tham khảo luận văn

Công trình nghiên cứu mang giá trị tham khảo chuyên sâu cho 4 nhóm đối tượng chính:

1. Kỹ sư phát triển phần mềm và kiến trúc sư hệ sinh thái mạng xã hội: Ứng dụng thuật toán V3D để xây dựng các tính năng bảo vệ người dùng, tối ưu hóa các module gợi ý nội dung an toàn và thiết kế hệ thống cảnh báo sớm luồng tin độc hại với độ trễ thấp.
2. Chuyên gia quản trị khủng hoảng truyền thông số và PR: Sử dụng phương pháp định vị nút hạt giống nhằm xác định chính xác các nhân tố ảnh hưởng then chốt trên mạng lưới (Key Opinion Leaders) để truyền tải thông điệp cải chính, giảm thiểu trên 80% thiệt hại thương hiệu khi xảy ra sự cố thông tin sai lệch.
3. Nhà nghiên cứu và học viên cao học chuyên ngành Khoa học máy tính, Khoa học dữ liệu: Khai thác các chứng minh toán học về đồ thị Power-Law, mô hình $\beta_T^I$-Node Protector và phương pháp xấp xỉ hóa thuật toán tham lam để phát triển các đề tài nghiên cứu chuyên sâu về tối ưu hóa trên đồ thị lớn.
4. Cơ quan quản lý nhà nước về thông tin truyền thông và an ninh mạng: Tham khảo khung lý thuyết và quy trình mô phỏng thực nghiệm để xây dựng các bộ tiêu chuẩn kỹ thuật, chính sách điều phối thông tin chính thống và quy trình can thiệp khẩn cấp trên không gian mạng quốc gia.

Câu hỏi thường gặp

Thuật toán V3D khác biệt như thế nào so với thuật toán tham lam truyền thống? Thuật toán tham lam truyền thống (General Greedy) phải lặp lại 20.000 vòng mô phỏng ngẫu nhiên Monte Carlo cho từng đỉnh để ước lượng mức độ lây lan, dẫn đến độ phức tạp $O(knRm)$. Ngược lại, V3D tập trung đánh giá trực tiếp số lượng cạnh thương tổn thông qua hàng đợi ưu tiên và thủ tục Bellman-Ford, giúp thời gian xử lý đạt mức hằng số $O(1)$ trên đồ thị Power-Law.

Vì sao cấu trúc mạng Power-Law lại giúp tối ưu hóa tốc độ của thuật toán V3D? Mạng xã hội tuân theo phân phối Power-Law có hệ số $\beta > 2$, đặc trưng bởi số lượng nhỏ các nút có bậc liên kết cực cao (hubs) và đa số các nút có bậc thấp. Cấu trúc này giới hạn không gian tìm kiếm các cạnh thương tổn trọng yếu, cho phép V3D cô lập nhanh chóng các nút phát tán mà không cần duyệt toàn bộ không gian đồ thị.

Tỷ lệ tương đồng từ 82.8% đến 100% giữa V3D và GVS có ý nghĩa thực tế ra sao? Thuật toán GVS đạt độ chính xác chuẩn mực nhưng không thể chạy trên dữ liệu lớn vì mất hàng chục giờ tính toán. Tỷ lệ tương đồng đạt 82.8% – 100% chứng minh V3D lựa chọn được gần như chính xác các nút hạt giống tối ưu mà chỉ tiêu tốn 0.4 giây tính toán, mang tính khả thi tuyệt đối cho các hệ thống ứng phó sự cố theo thời gian thực.

Hệ thống thực nghiệm trên nền tảng PHP và MySQL giải quyết bài toán với hiệu năng ra sao? Hệ thống thử nghiệm xử lý mượt mà đồ thị 464 bạn bè Facebook thực tế và tập dữ liệu mô phỏng 10.000 thực thể. Giao diện trực quan cho phép nhập số lượng nút cần tìm, chạy đồng thời hai thuật toán V3D và GVS, sau đó xuất bảng so sánh thời gian thực thi và tỷ lệ tương đồng trực tiếp trên trình duyệt.

Làm thế nào để mở rộng mô hình V3D cho các nền tảng mạng xã hội hiện đại đa thuộc tính? Mô hình có thể mở rộng bằng cách tích hợp các kỹ thuật khai phá dữ liệu như phân cụm K-Means dựa trên độ tuổi, vị trí địa lý và tần suất tương tác. Dữ liệu sau khi gom cụm sẽ cung cấp trọng số cạnh biến thiên chính xác hơn cho đồ thị, giúp V3D định vị nút hạt giống hiệu quả trên các mạng phức hợp đa tầng.

Kết luận

• Luận văn đã mô hình hóa thành công bài toán ngăn chặn tin độc hại trên mạng xã hội dưới dạng bài toán tối ưu hóa $\beta_T^I$-Node Protector trên đồ thị phân phối Power-Law.
• Đề xuất và hiện thực hóa thuật toán Vulnerable Viral Vertex (V3D), giải quyết triệt để rào cản độ phức tạp tính toán của các thuật toán tham lam truyền thống.
• Kết quả thực nghiệm khẳng định V3D đạt độ tương đồng vượt trội từ 82.8% đến 100% so với giải thuật tối ưu GVS, đồng thời duy trì thời gian thực thi ổn định dưới 1 giây trên các tập dữ liệu thử nghiệm quy mô hàng nghìn nút.
• Xây dựng hoàn chỉnh hệ thống ứng dụng web thực nghiệm trên nền tảng PHP/MySQL, kiểm chứng thành công trên tập dữ liệu thực 464 người dùng Facebook và 10.000 người dùng mô phỏng.
• Mở ra hướng nghiên cứu kết hợp phân cụm dữ liệu K-Means và khai phá thuộc tính hành vi người dùng trong lộ trình nâng cấp hệ thống 12 tháng tiếp theo.

Các tổ chức, doanh nghiệp phát triển nền tảng và nhà nghiên cứu an ninh thông tin quan tâm đến giải pháp kỹ thuật và mã nguồn thuật toán có thể tiếp tục triển khai các mô hình thực nghiệm mở rộng trên hạ tầng dữ liệu lớn để bảo vệ môi trường mạng an toàn và lành mạnh.

Trích đoạn nội dung tài liệu

ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƢỜNG ĐẠI HỌC BÁCH KHOA ________________________ TRẦN THẠCH LAM NGĂN CHẶN LAN TRUYỀN THÔNG TIN XẤU TRÊN MẠNG XÃ HỘI CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ CHUYÊN NGÀNH: 60.01 LUẬN VĂN THẠC SĨ THÀNH PHỐ HỒ CHÍ MINH - 2015 CÔNG TRÌNH ĐƢỢC HOÀN THÀNH TẠI TRƢỜNG ĐẠI HỌC BÁCH KHOA –ĐHQG –HCM Cán bộ hƣớng dẫn khoa học : PGS. Quản Thành Thơ Cán bộ chấm nhận xét 1 :TS. Bùi Hoài Thắng.

Cán bộ chấm nhận xét 2 :TS. Nguyễn Thanh Hiên. Luận văn thạc sĩ đƣợc bảo vệ tại Trƣờng Đại học Bách Khoa, ĐHQG Tp. Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: 1.

TS Dƣơng Tuấn Anh. Bùi Hoài Thắng. Nguyễn Thanh Hiên. Võ Thị Ngọc Châu.

Huỳnh Tƣờng Nguyên. Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trƣởng Khoa quản lý chuyên ngành sau khi luận văn đã đƣợc sửa chữa (nếu có). CHỦ TỊCH HỘI ĐỒNG TRƢỞNG KHOA ĐẠI HỌC QUỐC GIA TP.HCM CỘNG HÕA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƢỜNG ĐẠI HỌC BÁCH KHOA Độc lập - Tự do - Hạnh phúc NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: Trần Thạch Lam. Ngày, tháng, năm sinh: 24/01/1990 .Nơi sinh: Bến Tre.

Chuyên ngành: Khoa Học Máy Tính. TÊN ĐỀ TÀI: Ngăn chặn lan truyền thông tin xấu trên mạng xã hội. NHIỆM VỤ VÀ NỘI DUNG: Đề xuất và hiện thực một phƣơng pháp ngăn chặn lan truyền thông tin xấu trên một mạng xã hội, đồng thời so sánh với một phƣơng pháp khác để làm rõ ƣu thế của phƣơng pháp đã đề xuất. NGÀY GIAO NHIỆM VỤ :18/08/2014.

NGÀY HOÀN THÀNH NHIỆM VỤ: 08/05/2015. CÁN BỘ HƢỚNG DẪN: PGS. QUẢN THÀNH THƠ. HCM, ngày 15 tháng 06 năm 2015 CÁN BỘ HƢỚNG DẪN CHỦ NHIỆM BỘ MÔN ĐÀO TẠO (Họ tên và chữ ký) (Họ tên và chữ ký) PGS.

QUẢN THÀNH THƠ TRƢỞNG KHOA (Họ tên và chữ ký) Ghi chú: Học viên phải đóng tờ nhiệm vụ này vào trang đầu tiên của tập thuyết minh LV LỜI CẢM ƠN Tôi xin gửi lời cảm ơn chân thành và sâu sắc nhất đến PGS. Quản Thành Thơ, thầy đã tận tình hƣớng dẫn tôi trong suốt quá trình thực hiện đề cƣơng và luận văn cao học, tạo mọi điều kiện để tôi có thể hoàn thành tốt luận văn này. Tôi xin gửi lời biết ơn chân thành đến các Thầy Cô trong khoa Khoa Học & Kỹ Thuật Máy Tính trƣờng Đại Học Bách Khoa TPHCM. Các Thầy Cô đã rất tận tình chỉ dạy, trang bị cho tôi những kiến thức quý báu trong suốt thời gian tôi học cao học tại trƣờng.

Tôi xin gửi lời cảm ơn gia đình, bạn bè và anh chị nơi tôi học tập đã động viên và tạo mọi điều kiện thuận lợi giúp tôi hoàn thành luận văn. Mặc dù đã cố gắng hết sức có thể để hoàn thành tốt nhất luận văn trong phạm vi và khả năng cho phép nhƣng chắc chắn luận văn sẽ không tránh khỏi những thiếu sót, kính mong nhận đƣợc sự chỉ bảo tận tình của quý Thầy Cô và các bạn. HCM, ngày 09 tháng 06 năm 2015 Học viên Trần Thạch Lam i TÓM TẮT LUẬN VĂN Nhƣ mọi ngƣời đều biết, mạng xã hội chỉ mới ra đời trong những năm gần đây nhƣng đã phát triển với một tốc chóng mặt. Thông tin đƣợc chia sẻ trên mạng xã hội ngày càng trở nên khổng lồ, khó kiểm soát và phân loại.

Dần dần mạng xã hội phát sinh những vấn đề tiêu cực với ngƣời dùng do những thông tin xấu không đƣợc kiểm soát hay ngăn chặn. Chính vì thế lĩnh vực nghiên cứu về vấn đề ngăn chặn thông tin xấu trên mạng xã hội đƣợc ra đời và phát triển. Cho đến nay, đã có rất nhiều nghiên cứu và thí nghiệm đƣợc đƣa ra nhƣng các nhà khoa học vẫn chƣa thể tìm đƣợc giải pháp nào là tối ƣu nhất. Vì thế đề tài này sẽ tập trung nghiên cứu những phƣơng pháp đã có đồng thời tiến hành một số thí nghiệm và phân tích để tìm ra một giải pháp ngăn chặn thông tin xấu một cách tối đa, đồng thời giảm thiểu số lƣợng ngƣời cần tƣơng tác đến mức thấp nhất.

ii ABSTRACT As we know, the social network has just launched in recent years but it has grown with an incredible speed. Information become difficult to control and classify. So, many negative issues happened to users due to bad information was not controlled or prevented. That why the research to prevent bad information on social networks existed.

So far, there have been many researches and experiments about the prevention of bad information, but they still can not found an optimal solution yet. So, this thesis will focus on studying some previous researches , also make some experiments and analysis on the result to found an optimal solution, which minimize the number of users interracted. iii LỜI CAM ĐOAN Tôi xin cam đoan rằng, ngoại trừ các kết quả tham khảo từ các công trình khác nhƣ đã ghi rõ trọng luận văn, các công việc đƣợc trình bày trong luận văn này là do chính tôi thực hiện và chƣa có phần nội dung nào của luận văn này đƣợc nộp để lấy một bằng cấp ở trƣờng này hoặc trƣờng khác. HCM, ngày 15 tháng 06 năm 2015 Học viên Trần Thạch Lam iv MỤC LỤC LỜI CẢM ƠN.

iii LỜI CAM ĐOAN. iv MỤC LỤC. v DANH MỤC HÌNH ẢNH.vii DANH MỤC BẢNG. viii 1 GIỚI THIỆU .1 Động cơ và bài toán .2 Mục tiêu và giới hạn của đề tài .3 Phƣơng pháp tiến hành .4 Cấu trúc của luận văn .1 Nghiên cứu liên quan .1 Tối ƣu hóa các giải thuật tham lam .2 Giảm bậc Heuristic (Degree Discount Heuristic) .3 Giải thuật PageRank .4 Một số nghiên cứu về ngƣỡng (threshold) và cây (tree).

16 3 LÝ THUYẾT NỀN TẢNG.1 Định nghĩa về thực thể bị thƣơng tổn .2 Định nghĩa về mô hình nút bảo vệ .3 Các mô hình thƣờng dùng trong nghiên cứu đồ thị .1 Mô hình Cascade .2 Mô hình Linear Threshold .4 Giải thuật Naïve Greedy.5 Giải thuật Vulnerable Viral Vertex (V3D).6 Đồ thị Power-Law (α,β) .1 Đồ thị Power-Law (α,β) .2 Tốc độc lan truyền .1 Ý Tƣởng thực hiện .2 Giải thuật áp dụng. 23 5 HIỆN THỰC VÀ THÍ NGHIỆM .2 Xây dựng hệ thống .1 Xây dựng một tập các dữ liệu đủ lớn .2 Lƣu trữ tập dữ liệu .3 Xây dựng hệ thống .3 Tiến hành thí nghiệm và phân tích .1 Với dữ liệu giả .2 Với dữ liệu thực .3 Thí nghiệm so sánh .2 Phƣơng hƣớng phát triển. 37 7 TÀI LIỆU THAM KHẢO. 39 vi DANH MỤC HÌNH ẢNH Hình 1.1 : Mạng lƣới ngƣời dùng đơn giản .2 : Một trƣờng hợp chọn ngƣời dùng thỏa mãn điều kiện .1: Ví dụ giải thuật General Greedy .2: Ví dụ về các trang liên kết .1: Tốc độ lan truyền trên Facebook với ρ = 0.2 : Tốc độ lan truyền trên Facebookvới ρ = 0.1: Mô phỏng Users lƣu trong MySQL với dữ liệu giả.2: Mô phỏng Users lƣu trong MySQL với dữ liệu thực.3: Mô phỏng trang chủ của hệ thống.4: Form nhập thông tin của hệ thống.5: Trang kết quả của hệ thống ứng với 2 giải thuật khác nhau.6: Kết quả của 2 giải thuật khi tìm 6 users trên 24 users đƣợc chọn.7 : Kết quả của 2 giải thuật khi tìm 5 users trên 2000 users đƣợc chọn.8: Kết quả của 2 giải thuật khi tìm 50 users trên 2000 users đƣợc chọn.9 : Kết quả của 2 giải thuật khi tìm 20 users trên 464 users đƣợc chọn.10: Đồ thị thời gian thực thi 2 giải thuật với số cần tìm tăng dần .11: Đồ thị thời gian thực thi của 2 giải thuật tổng ngƣời dùng tăng dần .12: Kết quả khi của thí nghiệm khi cùng áp dụng 2 giải thuật V3D và GVS.

35 vii DANH MỤC BẢNG Bảng 2.1: Bảng quy định các biến dùng trong phần 2.2: Bảng độ phức tạp của các giải thuật trong phần 2.1 : Kết quả thời gian thực thi của các giải thuật .2 : Thời gian thực thi của các giải thuật với ngƣời dùng cần tìm tăng dần.3: Thời gian thực thi 2 giải thuật với tổng ngƣời dùng tăng dần .4: Bảng tỉ lệ tƣơng đồng giữa kết quả của 2 giải thuật V3D và GVS. 36 viii 1 GIỚI THIỆU 1.1 Động cơ và bài toán Mạng xã hội xuất hiện lần đầu tiên năm 1995 với sự ra đời của trang Classmate, SixDegrees vào năm 1997. Năm 2002, Friendster trở thành một trào lƣu mới tại Hoa Kỳ với hàng triệu thành viên. Năm 2004, MySpace ra đời với các tính năng nhƣ phim ảnh và nhanh chóng thu hút hàng chục ngàn thành viên mới mỗi ngày.

Năm 2006, sự ra đời của Facebook đánh dấu bƣớc ngoặt mới cho hệ thống mạng xã hội trực tuyến với nền tảng lập trình "Facebook Platform" cho phép thành viên tạo ra những công cụ (apps) mới cho cá nhân mình cũng nhƣ các thành viên khác. Kể từ đó, lƣợng ngƣời tham gia vào mạng xã hội tăng dần với tốc độ chóng mặt. Năm 2012, chỉ tính riêng Facebook đã đạt hơn 1 tỷ ngƣời dùng.[11] Việc mạng xã hội phát triển rộng rãi đem lại nhiều lợi ích to lớn. Ngƣời dùng liên kết với nhau chặt chẽ hơn, thông tin đƣợc chia sẻ và lan rộng nhanh với tốc độ chóng mặt.

Chỉ với vài thao tác đơn giản, bạn có thể biết đƣợc những thông tin mới nhất về một vấn đề mà mình quan tâm. Tuy nhiên, chính việc lan truyền thông tin với tốc độ rất nhanh và rộng đó cũng đem đến những hiệu ứng tiêu cực nặng nề. Ở đây cụ thể là việc thông tin nhạy cảm hoặc thông tin sai lêch gây ảnh hƣởng xấu đến ngƣời dùng hoặc tổ chức bị rò rỉ trên mạng xã hội và đƣợc lan truyền đến những ngƣời dùng khác. Những thông tin này có thể xuất phát từ những nguồn nhƣ bản thân ngƣời dùng ( khi ngƣời dùng đó chƣa ý thức đƣợc tác động tiêu cực của thông tin hay do tài khoản ngƣời dùng đó bị kẻ gian xâm nhập ), hoặc do một ngƣời khác hoặc 1 tổ chức khác chia sẻ nhằm gây tác động xấu đến nạn nhân.

1 Chính vì vậy, đi cùng với sự phát triển mạnh mẽ của mạng xã hội, thì ngƣời dùng càng cần phải đƣợc bảo vệ chặt chẽ khi tham gia vào lĩnh vực này. Bên cạnh việc cung cấp các cơ chế bảo mật và thiết lập chế độ bảo mật cho thông tin của ngƣời dùng mà rất nhiều mạng xã hội đang áp dụng hiện nay, giới nghiên cứu hiện tập trung vào việc tìm ra các giải pháp nhằm ngăn chặn sự lan truyền của những thông xấu nhằm mục đích giảm thiểu tối đa những tác động tiêu cực mà thông tin đó gây ra cho ngƣời dùng. Đó cũng chính là nội dung mà đề tài này hƣớng đến.