Luận án tiến sĩ về các kỹ thuật phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội

• Tác giả: Nguyễn Hiền Trinh
• Người hướng dẫn: PGS.TS Đoàn Văn Ban
• Trường học: Đại học Thái Nguyên - Trường Đại học Công nghệ Thông tin và Truyền thông
• Chuyên ngành: Khoa học máy tính
• Đề tài: Một số kỹ thuật phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2023
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
• DANH MỤC CÁC THUẬT NGỮ
• MỞ ĐẦU
• 1. CHƯƠNG 1: TỔNG QUAN VỀ ĐỒ THỊ MẠNG XÃ HỘI VÀ BÀI TOÁN PHÁT HIỆN CẤU TRÚC CỘNG ĐỒNG TRÊN ĐỒ THỊ MẠNG XÃ HỘI
• 1.1. Giới thiệu chung
• 1.2. Mạng xã hội và đồ thị mạng xã hội
• 1.3. Một số đặc tính của mạng xã hội
• 1.4. Đồ thị mạng xã hội và cấu trúc cộng đồng của mạng xã hội
• 1.5. Một số độ đo quan trọng trên đồ thị mạng xã hội
• 1.5.1. Độ đo trung tâm theo bậc
• 1.5.2. Độ đo trung tâm theo vector riêng
• 1.5.3. Hệ số phân cụm đồ thị
• 1.6. Bài toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội
• 1.6.1. Nhóm thuật toán phát hiện cấu trúc cộng đồng truyền thống
• 1.6.2. Nhóm thuật toán phát hiện cấu trúc cộng đồng dựa trên tối ưu hóa độ đo đơn thể
• 1.6.3. Nhóm thuật toán phát hiện cấu trúc cộng đồng dựa vào độ đo trung gian
• 1.6.4. Nhóm thuật toán phát hiện cấu trúc cộng đồng dựa trên lan truyền nhãn
• 1.6.5. Nhóm thuật toán phát hiện cấu trúc cộng đồng dựa vào mạng học sâu
• 1.7. Các độ đo đánh giá thuật toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội
• 1.7.1. Thông tin tương hỗ chuẩn NMI
• 1.8. Tổng kết chương 1
• 2. CHƯƠNG 2: PHÁT HIỆN CẤU TRÚC CỘNG ĐỒNG RỜI NHAU TRÊN ĐỒ THỊ MẠNG XÃ HỘI
• 2.1. Phát hiện cấu trúc cộng đồng rời nhau bằng phương pháp phân cụm phổ (Spectral)
• 2.1.1. Những vấn đề cơ bản trong phương pháp phân cụm phổ (Spectral Clustering)
• 2.1.2. Bài toán và phương pháp phân cụm phổ
• 2.1.3. Thuật toán đề xuất
• 2.1.4. Các kết quả thực nghiệm
• 2.2. Cải tiến thuật toán lan truyền nhãn LPA
• 2.2.1. Thuật toán lan truyền nhãn LPA
• 2.2.2. Thuật toán lan truyền nhãn LPAMD với hàm f đề xuất
• 2.2.3. Kết quả thực nghiệm thuật toán LPAMD
• 2.3. Kết hợp rút gọn đồ thị và thuật toán lan truyền nhãn
• 2.3.1. Thuật toán LPARLV (LPA Reduce Leaf Vertex)
• 2.3.2. Kết quả thực nghiệm
• 2.4. Tổng kết chương 2
• 3. CHƯƠNG 3: PHÁT HIỆN CẤU TRÚC CỘNG ĐỒNG CHỒNG CHÉO TRÊN ĐỒ THỊ MẠNG XÃ HỘI
• 3.1. Khái quát về vấn đề cộng đồng chồng chéo
• 3.2. Hệ số phân cụm đồ thị và hệ số thuộc về cộng đồng
• 3.2.1. Hệ số phân cụm đồ thị
• 3.2.2. Hệ số thuộc về cộng đồng
• 3.3. Phát hiện cấu trúc cộng đồng chồng chéo theo lan truyền nhãn và dựa vào hệ số thuộc về cộng đồng
• 3.4. Độ phức tạp thuật toán COPA-BC
• 3.5. Kết quả thực nghiệm
• 3.6. Tổng kết chương 3
• KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN CỦA LUẬN ÁN
• DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CÓ LIÊN QUAN ĐẾN LUẬN ÁN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Kỹ thuật phát hiện cấu trúc cộng đồng

Luận án tập trung vào kỹ thuật phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội, một lĩnh vực quan trọng trong phân tích mạng xã hội. Các phương pháp được đề cập bao gồm phân cụm phổ, lan truyền nhãn, và tối ưu hóa độ đo. Các kỹ thuật này giúp xác định các nhóm thực thể có mối quan hệ chặt chẽ trong mạng, từ đó hỗ trợ hiểu sâu hơn về cấu trúc và tương tác xã hội.

1.1. Phân cụm phổ

Phương pháp phân cụm phổ sử dụng ma trận Laplace để giảm chiều dữ liệu và tối ưu hóa hàm Min-cut. Kỹ thuật này hiệu quả trong việc phát hiện cấu trúc cộng đồng rời nhau trên đồ thị mạng xã hội. Thuật toán SCN (Spectral Clustering New) được đề xuất, kết hợp ý tưởng giảm chiều dữ liệu và tối ưu hóa hàm Min-cut, mang lại kết quả chính xác và thời gian tính toán nhanh.

1.2. Lan truyền nhãn

Lan truyền nhãn là phương pháp hiệu quả với thời gian tính toán gần tuyến tính. Tuy nhiên, nó có nhược điểm là kết quả không duy nhất và mang tính gần đúng. Luận án đề xuất cải tiến thuật toán LPA (Label Propagation Algorithm) bằng cách sử dụng hàm xác định nhãn tối ưu, giúp nâng cao tính ổn định và hiệu quả trong việc phát hiện cấu trúc cộng đồng rời nhau.

II. Phát hiện cộng đồng chồng chéo

Luận án cũng tập trung vào phát hiện cộng đồng chồng chéo, một vấn đề phức tạp nhưng có ý nghĩa thực tiễn cao. Các phương pháp như loại bỏ cạnh có độ trung gian cao, phát hiện đồ thị con dày đặc, và tối ưu hóa modul được nghiên cứu và cải tiến để xử lý hiệu quả các mạng lớn và dày đặc.

2.1. Phương pháp lan truyền nhãn chồng chéo

Phương pháp lan truyền nhãn chồng chéo được cải tiến bằng cách sử dụng hệ số phân cụm cải tiến. Thuật toán COPA-BC (Community Overlap Propagation Algorithm Based on New Belonging Coefficient) được đề xuất, giúp phát hiện nhanh và chính xác các cấu trúc cộng đồng chồng chéo trên đồ thị mạng xã hội.

2.2. Tối ưu hóa modul

Tối ưu hóa modul là phương pháp quan trọng trong việc xác định các cộng đồng chồng chéo. Luận án đề xuất cải tiến thuật toán PCB (Belief Propagation and Conflict) để giảm độ phức tạp thời gian và không gian, giúp xử lý hiệu quả các mạng lớn.

III. Ứng dụng và đánh giá

Luận án đánh giá hiệu quả của các thuật toán đề xuất thông qua thực nghiệm trên các bộ dữ liệu thực. Các độ đo như Modularity và NMI (Normalized Mutual Information) được sử dụng để đánh giá chất lượng cộng đồng được phát hiện. Kết quả cho thấy các thuật toán đề xuất có hiệu suất vượt trội so với các phương pháp truyền thống.

3.1. Thực nghiệm và kết quả

Các thuật toán SCN, LPAMD, và COPA-BC được thực nghiệm trên các bộ dữ liệu như Karate Club, Dolphin Group, và Email-Enron. Kết quả cho thấy các thuật toán này có thời gian tính toán nhanh và độ chính xác cao, đặc biệt trong việc phát hiện cấu trúc cộng đồng rời nhau và chồng chéo.

3.2. Đánh giá độ đo

Các độ đo Modularity và NMI được sử dụng để đánh giá chất lượng cộng đồng. Kết quả thực nghiệm cho thấy các thuật toán đề xuất đạt được giá trị Modularity và NMI cao hơn so với các phương pháp truyền thống, chứng tỏ hiệu quả vượt trội trong việc phát hiện cấu trúc cộng đồng.