ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Vũ Thị Thu Hương PHÁT HIỆN CỘNG ĐỒNG SỬ DỤNG THUẬT TOÁN CONGA VÀ KHAI PHÁ QUAN ĐIỂM CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Cơng nghệ thơng tin HÀ NỘI - 2012 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Vũ Thị Thu Hương PHÁT HIỆN CỘNG ĐỒNG SỬ DỤNG THUẬT TOÁN CONGA VÀ KHAI PHÁ QUAN ĐIỂM CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Cơng nghệ thông tin Cán hướng dẫn: PSG.TS Hà Quang Thụy Cán đồng hướng dẫn: ThS Trần Mai Vũ HÀ NỘI - 2012 VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERITY OF ENGINEERING AND TECHNOLOGY Vu Thi Thu Huong COMMUNITY DETECTION BY CONGA ALGORITHM AND COMMUNITIES’ OPINION MINING ON SOCIAL NETWORK Major: Information of Technology Supervior: Assor Prof Thuy Ha Quang Co-Supervior: Master Vu Tran Mai HA NOI - 2012 LỜI CẢM ƠN Đầu tiên, em xin gửi lời cảm ơn chân thành sâu sắc tới thầy Hà Quang Thụy thầy Trần Mai Vũ, người trực tiếp hướng dẫn tận tình đóng góp ý kiến q báu suốt q trình em làm khóa luận tốt nghiệp Em xin gửi lời cảm ơn tới anh chị bạn phịng thí nghiệm KTLAB, người tận tình giúp đỡ em trình làm khóa luận Tiếp theo em xin gửi lời cảm ơn đến đến thầy cô giáo trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà Nội, tận tâm truyền đạt kiến thức quý báu làm tảng để em bước vào đời Cuối cùng, em xin cảm ơn cha mẹ, bạn bè người thân, người bên em, khuyến khích động viên em sống, học tập Sinh viên Vũ Thị Thu Hương PHÁT HIỆN CỘNG ĐỒNG SỬ DỤNG THUẬT TOÁN CONGA VÀ KHAI PHÁ QUAN ĐIỂM CỘNG ĐỒNG Vũ Thị Thu Hương Khóa QH-2008-I/CQ, ngành Cơng nghệ thơng tin Tóm tắt Khóa luận tốt nghiệp: Sự phát triển nhanh chóng mạng xã hội kéo theo bùng nổ liệu mạng xã hội Đây nguồn thơng tin hữu ích, liên tục cập nhật Một đặc trưng chất mạng xã hội tính cộng đồng Việc đánh giá quan điểm cộng đồng mang lại nhìn rõ ràng lớp đối tượng cần hướng đến Khóa luận tập trung nghiên cứu giải toán dựa thuật toán CONGA (Cluster Overlapping Newman Girvan Algorithm) phát cộng đồng Steve Gregory đề xuất năm 2007 học máy Nạve Bayes Khóa luận đề nghị mơ hình kết hợp hai thuật tốn vào việc phát đánh giá quan điểm cộng đồng mạng xã hội Hệ thống chia thành hai phần chính: Phần – phát cộng đồng Twitter xây dựng dựa phần mềm CONGA (Steve Gregory, 2010) Twitter API (Yusuke Yamamoto cộng sự, 2009) Phần hai – phân lớp quan điểm cộng đồng xây dựng dựa học máy Naïve Bayes Kết thực nghiệm mơ hình cho kết phù hợp Từ khóa: Cộng đồng mạng xã hội, CONGA, quan điểm cộng đồng, Nạve Bayes LỜI CAM ĐOAN Tơi xin cam đoan mơ hình phát khai phá quan điểm cộng đồng mạng xã hội trực tuyến Twitter, thực nghiệm dựa thuật tốn CONGA Nạve Bayes trình bày khóa luận tơi thực hướng dẫn PGS TS Hà Quang Thụy, ThS Trần Mai Vũ Tất báo, khóa luận, tài liệu, cơng cụ phần mềm tác giả khác sử dụng lại khóa luận dẫn tường minh tác giả có danh sách tài liệu tham khảo Hà Nội, ngày 18 tháng năm 2012 Sinh viên Vũ Thị Thu Hương MỤC LỤC Chương TỔNG QUAN VỀ MẠNG XÃ HỘI, BÀI TOÁN PHÁT HIỆN VÀ ĐÁNH GIÁ QUAN ĐIỂM CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI 1.1 Tổng quan mạng xã hội 1.2 Bài toán phát cộng đồng mạng xã hội 1.2.1 Cộng đồng mạng xã hội 1.2.2 Giới thiệu toán phát cộng đồng 1.3 Bài toán khai phá quan điểm người dùng mạng xã hội 1.4 Kết luận chương 11 Chương THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG VÀ ĐÁNH GIÁ QUAN ĐIỂM CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI 12 2.1 Họ thuật toán phát cộng đồng GIRVAN-NEWMAN 12 2.1.1 Thuật toán Girvan-Newman 12 2.1.2 Thuật toán CONGA 15 2.2 Đánh giá quan điểm sử dụng Học máy xác suất Bayes 19 2.1.1 Học máy xác suất Bayes 19 2.1.2 Phân lớp quan điểm sử dụng Bayes 20 2.3 Kết luận chương 23 Chương MƠ HÌNH ĐÁNH GIÁ QUAN ĐIỂM CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI 24 3.1 Mơ hình đánh giá quan điểm cộng đồng Twitter 24 3.2 Pha 1: Phát hiên cộng đồng mạng xã hội 27 3.3 Pha 2: Khai phá quan điểm cộng đồng mạng xã hội 30 3.4 Kết luận chương 33 Chương THỰC NGHIỆM VÀ ĐÁNH GIÁ 34 4.1 Mô tả thực nghiệm 34 4.1.1 Mô tả liệu 34 4.1.2 Môi trường thực nghiệm 35 4.1.3 Các công cụ phầm mềm sử dụng 35 4.2 Thực nghiệm đánh giá 36 4.1.1 Thực nghiệm 36 4.1.2 Đánh giá 38 4.3 Kết luận chương 40 KẾT LUẬN VÀ PHƯƠNG HƯỚNG 41 TÀI LIỆU THAM KHẢO 42 DANH SÁCH HÌNH VẼ Hình 1.1: Đồ thị sử dụng mạng xã hội giới (tổng hợp tháng 11 năm 2011) Hình 1.2: Cộng đồng mạng xã hội đơn giản với cộng đồng Hình 1.3.a: Mơ hình mạng lưới thành viên Câu lạc Karate (Zachary, 1977) Hình 1.3.b: Mơ hình mạng lưới cộng tác nhà khoa học làm việc SFI Hình 1.3.c: Mạng biểu diễn loài cá heo sống Doubtful Sound, New Zealand Hình 1.4: Lược đồ chung xây dựng phân lớp văn 10 Hình 2.1: Ví dụ phát cộng đồng sử dụng Girven-Newman 13 Hình 2.2: Ví dụ trường hợp không phân tách đỉnh v đồ thị 16 Hình 2.3: Ví dụ phép phân chia đỉnh đồ thị 17 Hình 2.4: Tìm phép phân chia tối ưu 18 Hình 3.1: Phân bố sử dụng Twitter giới 24 Hình 3.2: Mơ hình đề xuất giải toán phát khai phá quan điểm cộng đồng mơ hình mạng xã hội Twitter 26 Hình 3.3: Thông tin ID người dùng twitter follow @linkhay 27 Hình 3.4: Mạng xã hội xây dựng danh sách người dùng thu thập 28 Hình 3.5: Cộng đồng mạng xã hội sau qua CONGA 29 Hình 4.1: Kết phân chia cộng đồng 36 Hình 4.2: Cấu trúc đồ thị chia thành cộng đồng 37 DANH SÁCH BẢNG BIỂU Bảng 1: Bảng ký hiệu 31 Bảng 2: Môi trường thực nghiệm (phần cứng hệ điều hành) 35 Bảng 3: Các công cụ phần mềm sử dụng 35 Bảng 4: Tập liệu huấn luyện 37 Bảng 5: Kết quan điểm cộng đồng với kiện 1: 38 Bảng 6: Kết quan điểm cộng đồng với kiện 2: 38 Bảng 7: Kết quan điểm cộng đồng với kiện 3: 38 Bảng 8: Kết đánh giá phát cộng đồng mạng xã hội sử dụng CONGA 38 Bảng 9: Kết đánh giá phân lớp Naïve Bayes 39 ... TỔNG QUAN VỀ MẠNG XÃ HỘI, BÀI TOÁN PHÁT HIỆN VÀ ĐÁNH GIÁ QUAN ĐIỂM CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI 1.1 Tổng quan mạng xã hội 1.2 Bài toán phát cộng đồng mạng xã hội 1.2.1 Cộng đồng. .. giá quan điểm cộng đồng mạng xã hội Chương 2: Trình bày thuật tốn phát cộng đồng CONGA thuật toán đánh giá quan điểm mạng xã hội sử dụng học máy Nạve Bayes Chương 3: Mơ hình đề xuất phát cộng đồng. .. GIÁ QUAN ĐIỂM CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI 24 3.1 Mơ hình đánh giá quan điểm cộng đồng Twitter 24 3.2 Pha 1: Phát hiên cộng đồng mạng xã hội 27 3.3 Pha 2: Khai phá quan điểm