Giới thiệu tài liệu
Luận văn này nghiên cứu về bài toán phát hiện cộng đồng mạng thông qua việc tối ưu hóa hàm modularity, một thước đo quan trọng đánh giá chất lượng phân cụm trong mạng. Modularity cao phản ánh cấu trúc phân chia cộng đồng rõ ràng. Luận văn tập trung vào các thuật toán tối ưu hóa modularity cục bộ (Louvain, Leiden) và toàn cục (phương pháp phổ của Newman cho đồ thị vô hướng và đề xuất phương pháp mới cho đồ thị có hướng). Mục tiêu là tìm hiểu, xây dựng và đề xuất các thuật toán tối ưu hóa modularity hiệu quả cho cả đồ thị vô hướng và có hướng, ứng dụng trong phân tích cấu trúc nhóm trong nhiều lĩnh vực như mạng xã hội và sinh học.
Đối tượng sử dụng
Luận văn này phù hợp với các nhà nghiên cứu và sinh viên trong lĩnh vực khoa học máy tính, toán học ứng dụng và các ngành khoa học liên quan, những người quan tâm đến việc phân tích mạng lưới và phát hiện cộng đồng trong dữ liệu lớn.
Nội dung tóm tắt
Luận văn gồm ba chương chính: Chương 1 trình bày kiến thức nền tảng về lý thuyết đồ thị, quá trình ngẫu nhiên trên đồ thị, hàm modularity và phương pháp nhân tử Lagrange. Chương 2 tập trung vào các thuật toán tối ưu hóa modularity cục bộ, bao gồm thuật toán Louvain và Leiden, cùng với các thí nghiệm đánh giá hiệu quả của chúng trên cả đồ thị thực và đồ thị ngẫu nhiên. Các thí nghiệm này so sánh chất lượng phân cụm (thông qua giá trị modularity và chỉ số Jaccard), độ kết nối trong cộng đồng và thời gian chạy của thuật toán. Chương 3 trình bày các thuật toán tối ưu hóa modularity toàn cục, bao gồm phương pháp phổ của Newman cho đồ thị vô hướng và đề xuất một phương pháp mới cho đồ thị có hướng dựa trên quá trình bước đi ngẫu nhiên và phân phối dừng. Các thí nghiệm đánh giá hiệu quả của các phương pháp này trên cả đồ thị ngẫu nhiên và đồ thị thực, so sánh với các thuật toán khác như oPCA và rPCA, cũng như thuật toán Louvain có hướng. Luận văn đóng góp vào việc phát triển các thuật toán tìm kiếm cộng đồng mạng hiệu quả và có tính ứng dụng cao trong nhiều lĩnh vực.
