Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu độ đo trung gian và thuật toán phát hiện cộng đồng trên mạng xã hội

Nội dung chính của đề tài là tìm hiểu mạng xã hội, cấu trúc cộng đồng trên đồ thị mạng xã hội và các phương pháp tìm kiếm cấu trúc cộng đồng mạng xã hội. Nghiên cứu các độ đo trên đồ thị mạng xã hội và tìm hiểu các thuật toán phát hiện cấu trúc cộng đồng trên mạng xã hội. Xây dựng ứng dụng phát hiện cộng đồng mạng xã hội ở tập dữ liệu đã được công bố trên mạng. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu độ đo trung gian và thuật toán phát hiện cộng đồng trên mạng xã hội ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG DƯƠNG THỊ TÌNHNGHIÊN CỨU ĐỘ ĐO TRUNG GIAN VÀ THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2020 LỜI CAM ĐOAN Tôi xin cam đoan các kết quả nghiên cứu trong luận văn này là do tựbản thân tôi tìm hiểu dưới sự hướng dẫn của PGS. TS. Đoàn Văn Ban. Cácchương trình thực nghiệm do chính bản thân tôi lập trình, các kết quả là hoàntoàn trung thực. Các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồngốc. TÁC GIẢ LUẬN VĂN Dương Thị Tình LỜI CẢM ƠN Để hoàn thành được luận văn này, tôi đã nhận được rất nhiều sự quantâm, giúp đỡ và góp ý quý báu của các cá nhân và tập thể. Trước hết tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS. ĐoànVăn Ban đã quan tâm, định hướng và đưa ra những góp ý chỉnh sửa quý báucho tôi trong quá trình làm luận văn tốt nghiệp. Đồng thời tôi cũng xin chân thành cảm ơn sự góp ý chân thành của cácthầy, cô giáo Viện Công nghệ thông tin, các thầy, cô giáo Trường Đại học Côngnghệ thông tin và Truyền thông Thái Nguyên đã tạo mọi điều kiện thuận lợicho tôi hoàn thành đề tài này. Dù đã rất cố gắng nhưng chắc chắn sẽ không tránh khỏi những thiếu sótvì vậy rất mong nhận được sự góp ý của các thầy, cô và các bạn để luận vănnày được hoàn thiện hơn. Tôi xin chân thành cảm ơn! Thái Nguyên, tháng 08 năm 2020 Dương Thị Tình MỤC LỤC TrangMỞ ĐẦU .......................................................................................................... 1CHƯƠNG 1 MẠNG XÃ HỘI VÀ CÁC ĐỘ ĐO TRÊN ĐỒ THỊ MẠNGXÃ HỘI ............................................................................................................ 4 1.1. MẠNG XÃ HỘI ......................................................................................... 4 1.2. CẤU TRÚC CỘNG ĐỒNG MẠNG XÃ HỘI ...................................................... 8 1.3. CÁC ĐỘ ĐO TRÊN ĐỒ THỊ MẠNG XÃ HỘI .................................................. 11 1.3.1. Hệ số cố kết của mạng .................................................................. 12 1.3.2. Hệ số trung tâm vector đặc trưng .................................................. 13 1.3.3. Độ đo trung tâm của đỉnh .............................................................. 14 1.3.4. Hệ số trung gian của đỉnh ............................................................. 18 1.3.5. Độ đo trung gian của cạnh ............................................................ 20 1.4. THUẬT TOÁN TÍNH ĐỘ TRUNG GIAN ....................................................... 22 1.5. KẾT LUẬN CHƯƠNG ............................................................................... 26CHƯƠNG 2 THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI......................................................................................................................... 27 2.1. BÀI TOÁN PHÁT HIỆN CỘNG ĐỒNG TRÊN ĐỒ THỊ MẠNG XÃ HỘI ............... 27 2.2. THUẬT TOÁN PHÂN CỤM PHÂN CẤP........................................................ 28 2.3. THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG DỰA TRÊN TỐI ƯU HOÁ ĐỘ ĐO ĐƠN THỂ ............................................................................................................... 30 2.4. THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG DỰA VÀO ĐỘ ĐO TRUNG GIAN ...... 30 2.5. PHÁT HIỆN CÁC CỘNG ĐỒNG GỐI NHAU .................................................. 33 2.5.1. Phát hiện các k-cliques trong mạng xã hội ................................... 34 2.5.2. Thuật toán phát hiện k-clique........................................................ 36 2.5.3. Thuật toán EAGLE ....................................................................... 38 2.5.4. Đánh giá thuật toán ....................................................................... 43 2.6. KẾT LUẬN CHƯƠNG 2............................................................................. 44CHƯƠNG 3 ỨNG DỤNG THUẬT TOÁN GIRVAN-NEWMAN TRONGPHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI .......................................... 45 3.1. MÔ TẢ BÀI TOÁN PHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI ........................ 45 3.2. CHƯƠNG TRÌNH PHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI .......................... 45 3.2.1. Bộ cơ sở dữ liệu ............................................................................ 45 3.2.2. Môi trường thử nghiệm ................................................................. 47 3.2.3. Thử nghiệm và đánh giá................................................................ 49 3.3. KẾT LUẬN CHƯƠNG 3............................................................................. 54KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................................... 55TÀI LIỆU THAM KHẢO ............................................................................ 56 DANH MỤC CÁC HÌNH VẼHình 1.1. Mạng xã hội Facebook ...................................................................... 7Hình 1.2. Mạng xã hội Zing me ........................................................................ 7Hình 1.3. Mô hình mạng lưới cộng tác của các nhà khoa học làm việc tại SFI 9Hình 1.4. Đồ thị có 4 đỉnh và 5 cạnh .............................................................. 15 ...