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.
