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