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
Khoa học máy tính (Mã số: 9. 48. 01. 01)
Mạng xã hội, được biểu diễn dưới dạng đồ thị, luôn thể hiện tính cấu trúc cộng đồng mạnh mẽ, nơi các đỉnh có xu hướng tương tác với nhau nhiều hơn các đỉnh bên ngoài nhóm. Phát hiện cấu trúc cộng đồng là một vấn đề quan trọng và cốt lõi trong khai phá dữ liệu đồ thị, thu hút sự quan tâm của nhiều học giả. Tuy nhiên, các thuật toán hiện có thường có độ phức tạp lớn, khó cân bằng giữa hiệu quả và độ chính xác, đặc biệt trên các mạng lớn và phức tạp. Luận án này khảo sát các vấn đề lý thuyết liên quan và đề xuất một số kỹ thuật mới nhằm phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội, bao gồm cả cộng đồng rời nhau và chồng chéo.
Mục tiêu chính của luận án là nghiên cứu phân cụm phổ sử dụng vectơ riêng, phát triển các thuật toán lan truyền nhãn với hàm xác định nhãn tối ưu, và phát triển thuật toán phát hiện cấu trúc cộng đồng chồng chéo dựa trên hệ số phụ thuộc về cộng đồng cải tiến. Luận án đã đóng góp bốn thuật toán chính: (1) **SCN (Spectral Clustering New)**: Phát hiện cấu trúc cộng đồng rời nhau dựa trên kỹ thuật phân cụm phổ, giảm số chiều dữ liệu và sử dụng ma trận Laplace. (2) **LPAMD (Label Propagation Algorithm with Modularity and Density)**: Phát hiện nhanh cộng đồng rời nhau bằng cách cải tiến thuật toán lan truyền nhãn tổng quát, kết hợp tiêu chí Modularity và mật độ cộng đồng. (3) **LPARLV (LPA Reduce Leaf Vertex)**: Kết hợp rút gọn đồ thị ban đầu về RLVG để giảm kích thước mạng, sau đó sử dụng LPAMD với hàm gắn nhãn fr_max để xác định cấu trúc cộng đồng rời nhau. (4) **COPA-BC (Community Overlap Propagation Algorithm Based on New Belonging Coefficient)**: Phát hiện cấu trúc cộng đồng chồng chéo bằng cách kết hợp thuật toán lan truyền nhãn và hệ số thuộc về cộng đồng cải tiến.
Các kết quả nghiên cứu này có ý nghĩa khoa học sâu sắc, cung cấp cơ sở lý luận và kinh nghiệm để giải quyết hiệu quả bài toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội lớn và phức tạp. Về mặt thực tiễn, chúng có thể áp dụng trong phân tích mạng xã hội tại Việt Nam, hỗ trợ phân loại xu thế phát triển kinh tế, chính trị, xã hội, và làm tài liệu tham khảo cho giảng dạy, học tập. Hướng phát triển trong tương lai bao gồm vận dụng kỹ thuật mạng nơ ron và học sâu, phối hợp mô hình thống kê, và nghiên cứu xử lý song song để nâng cao hiệu quả thuật toán.