Luận án tiến sĩ: Nghiên cứu thuật toán rút gọn đồ thị và ứng dụng phát hiện cộng đồng trên mạng xã hội

• Tác giả: Nguyễn Xuân Dũng
• Người hướng dẫn: PGS.TS Đoàn Văn Ban
• Trường học: Học viện Công nghệ Bưu chính Viễn thông
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Thuật toán rút gọn đồ thị và ứng dụng phát hiện cộng đồng trên mạng xã hội
• Loại tài liệu: luận án tiến sĩ
• Địa điểm: Hà Nội

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN RÚT GỌN ĐỒ THỊ VÀ PHÁT HIỆN CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI
• 1.1. Một số hệ số đo quan trọng trên đồ thị mạng xã hội
• 1.2. Hệ số cố kết mạng
• 1.3. Các hệ số đo tính trung tâm của tác nhân
• 1.4. Bài toán phát hiện cộng đồng mạng xã hội
• 1.5. Cộng đồng mạng xã hội
• 1.6. Các thuật toán phát hiện cộng đồng mạng xã hội
• 1.7. Bài toán rút gọn đồ thị
• 1.8. Sự cần thiết phải rút gọn đồ thị mạng xã hội
• 1.9. Các thuật toán rút gọn đồ thị
• 1.10. Các độ đo đánh giá thuật toán phát hiện cộng đồng mạng xã hội
• 1.11. Độ đo đơn thể mô đun Q
• 1.12. Độ đo dựa trên lý thuyết thông tin
• 1.13. Kết luận chương 1
• 2. CHƯƠNG 2: THUẬT TOÁN RÚT GỌN ĐỒ THỊ MẠNG XÃ HỘI DỰA VÀO ĐỘ ĐO TRUNG TÂM TRUNG GIAN VÀ NGUYÊN LÝ LAN TRUYỀN NHÃN
• 2.1. Các tính chất của độ đo trung tâm trung gian trên đồ thị mạng xã hội
• 2.2. Các lớp đỉnh treo tương đương
• 2.3. Các lớp đỉnh sườn tương đương
• 2.4. Các lớp đỉnh đồng nhất tương đương
• 2.5. Thuật toán rút gọn đồ thị dựa vào độ đo trung tâm trung gian
• 2.6. Thuật toán rút gọn đồ thị dựa vào nguyên lý lan truyền nhãn
• 2.7. Thuật toán lan truyền nhãn
• 2.8. Thực nghiệm và đánh giá
• 2.8.1. Bộ dữ liệu
• 2.8.2. Cài đặt thực nghiệm
• 2.8.3. Kết quả thực nghiệm
• 2.9. Kết luận chương 2
• 3. CHƯƠNG 3: ÁP DỤNG THUẬT TOÁN RÚT GỌN ĐỒ THỊ ĐỂ PHÁT HIỆN CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI
• 3.1. Thuật toán tính nhanh độ đo trung tâm trung gian trên đồ thị mạng xã hội rút gọn
• 3.2. Duyệt đồ thị theo chiều rộng
• 3.3. Thuật toán tính nhanh độ đo trung tâm trung gian
• 3.4. Thuật toán phát hiện cộng đồng mạng xã hội trên đồ thị rút gọn dựa vào độ đo trung tâm trung gian
• 3.5. Thuật toán lan truyền nhãn phát hiện cộng đồng trên đồ thị mạng xã hội rút gọn
• 3.6. Thực nghiệm và đánh giá
• 3.6.1. Cài đặt thực nghiệm
• 3.6.2. Đánh giá thực nghiệm
• 3.7. Kết luận chương 3
• KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• DANH MỤC CÁC CÔNG TRÌNH CÓ LIÊN QUAN ĐẾN LUẬN ÁN
• TÀI LIỆU THAM KHẢO

I. Tổng quan về luận án

Luận án tập trung vào thuật toán rút gọn đồ thị và ứng dụng trong phát hiện cộng đồng trên mạng xã hội. Nghiên cứu này nhằm giải quyết thách thức về quy mô lớn của các mạng xã hội hiện đại, nơi các thuật toán truyền thống không còn hiệu quả. Mạng xã hội (Social Networks) đã trở thành một phần không thể thiếu trong cuộc sống, với các ứng dụng như Facebook, Twitter, và LinkedIn. Phân tích mạng xã hội (Social Network Analysis) là một lĩnh vực quan trọng, giúp hiểu rõ các mối quan hệ và cấu trúc xã hội. Phát hiện cộng đồng (Community Detection) là một nhiệm vụ trọng tâm, có ứng dụng rộng rãi trong nhiều lĩnh vực như xã hội học, sinh học, và kinh tế.

1.1. Tính cấp thiết của luận án

Sự phát triển nhanh chóng của mạng xã hội đã tạo ra các đồ thị có quy mô khổng lồ, gây khó khăn cho việc phân tích và phát hiện cộng đồng. Các thuật toán truyền thống không thể xử lý hiệu quả các đồ thị lớn do độ phức tạp tính toán cao. Luận án đề xuất các phương pháp rút gọn đồ thị để giảm thiểu kích thước đồ thị mà vẫn bảo toàn các tính chất quan trọng, từ đó cải thiện hiệu suất của các thuật toán phát hiện cộng đồng.

1.2. Mục tiêu của luận án

Mục tiêu chính của luận án là phát triển các thuật toán rút gọn đồ thị dựa trên độ đo trung tâm trung gian (Betweenness Centrality) và nguyên lý lan truyền nhãn (Label Propagation). Các thuật toán này nhằm giảm thiểu số lượng đỉnh và cạnh của đồ thị, đồng thời cải tiến các thuật toán phát hiện cộng đồng để hoạt động hiệu quả trên đồ thị rút gọn.

II. Các thuật toán rút gọn đồ thị

Luận án đề xuất hai thuật toán chính để rút gọn đồ thị: REG (Reduce Equivalence Graph) và LREN (Label based Reduce Equivalence Nodes). REG dựa trên độ đo trung tâm trung gian, trong khi LREN sử dụng nguyên lý lan truyền nhãn. Cả hai thuật toán đều nhằm mục đích giảm thiểu kích thước đồ thị bằng cách kết hợp các đỉnh tương đương thành một đỉnh đại diện, từ đó giảm độ phức tạp tính toán.

2.1. Thuật toán REG

Thuật toán REG tập trung vào việc rút gọn đồ thị dựa trên độ đo trung tâm trung gian. Các đỉnh có cùng giá trị độ đo này được coi là tương đương và được kết hợp thành một đỉnh đại diện. Phương pháp này giúp giảm đáng kể số lượng đỉnh và cạnh của đồ thị, đồng thời bảo toàn các tính chất quan trọng của cộng đồng.

2.2. Thuật toán LREN

Thuật toán LREN sử dụng nguyên lý lan truyền nhãn để xác định các đỉnh tương đương. Các đỉnh có cùng nhãn được kết hợp thành một đỉnh đại diện, giúp rút gọn đồ thị mà vẫn duy trì cấu trúc cộng đồng. Phương pháp này đặc biệt hiệu quả trong việc xử lý các đồ thị lớn với cấu trúc phức tạp.

III. Ứng dụng phát hiện cộng đồng

Luận án cũng đề xuất các thuật toán phát hiện cộng đồng hiệu quả trên đồ thị rút gọn, bao gồm CDAB (Community Detection Algorithm based on Betweenness centrality) và LPAA (Label Propagation Algorithm on Abridged graph). Các thuật toán này được thiết kế để hoạt động hiệu quả trên các đồ thị đã được rút gọn, giúp giảm thời gian tính toán mà vẫn đảm bảo chất lượng phát hiện cộng đồng.

3.1. Thuật toán CDAB

Thuật toán CDAB sử dụng độ đo trung tâm trung gian để phát hiện các cộng đồng trên đồ thị rút gọn. Phương pháp này cải tiến thời gian tính toán so với các thuật toán truyền thống như Girvan-Newman, đồng thời duy trì độ chính xác trong việc xác định cộng đồng.

3.2. Thuật toán LPAA

Thuật toán LPAA dựa trên nguyên lý lan truyền nhãn để phát hiện cộng đồng trên đồ thị rút gọn. Phương pháp này giúp giảm thiểu thời gian tính toán so với thuật toán LPA truyền thống, đồng thời đảm bảo chất lượng phát hiện cộng đồng thông qua các độ đo như đơn thể mô đun Q và NMI (Normalized Mutual Information).