I. Tổng quan về thuật toán rút gọn đồ thị và phát hiện cộng đồng mạng xã hội
Luận án tập trung vào việc nghiên cứu các thuật toán rút gọn đồ thị và ứng dụng của chúng trong việc phát hiện cộng đồng mạng xã hội. Mạng xã hội đã trở thành một phần không thể thiếu trong cuộc sống hiện đại, với sự phát triển mạnh mẽ của các nền tảng như Facebook, Twitter, và Instagram. Phân tích mạng xã hội (SNA) là một lĩnh vực quan trọng, giúp hiểu rõ cấu trúc và mối quan hệ giữa các thực thể trong mạng. Phát hiện cộng đồng là một nhiệm vụ then chốt trong SNA, giúp xác định các nhóm có mối liên kết chặt chẽ trong mạng. Tuy nhiên, với quy mô ngày càng lớn của các mạng xã hội, việc áp dụng các thuật toán đồ thị truyền thống trở nên kém hiệu quả. Do đó, việc rút gọn đồ thị để giảm thiểu độ phức tạp tính toán là cần thiết.
1.1. Cộng đồng mạng xã hội và tầm quan trọng
Cộng đồng mạng xã hội là nhóm các thực thể có mối liên kết chặt chẽ, chia sẻ sở thích, mục tiêu hoặc đặc điểm chung. Việc phát hiện các cộng đồng này giúp hiểu rõ cấu trúc mạng và hỗ trợ các ứng dụng trong xã hội học, kinh tế, và khoa học máy tính. Các thuật toán phát hiện cộng đồng truyền thống thường gặp khó khăn khi xử lý các mạng có quy mô lớn, dẫn đến nhu cầu phát triển các phương pháp mới hiệu quả hơn.
1.2. Bài toán rút gọn đồ thị
Rút gọn đồ thị là quá trình giảm thiểu số lượng đỉnh và cạnh trong đồ thị mà vẫn bảo toàn các tính chất quan trọng. Điều này giúp tăng hiệu quả tính toán trong các bài toán như phát hiện cộng đồng. Các thuật toán rút gọn đồ thị thường dựa trên các độ đo như độ đo trung tâm trung gian hoặc nguyên lý lan truyền nhãn để xác định các đỉnh tương đương và kết hợp chúng thành một đỉnh đại diện.
II. Thuật toán rút gọn đồ thị dựa trên độ đo trung tâm trung gian
Chương này tập trung vào việc đề xuất và thực nghiệm các thuật toán rút gọn đồ thị dựa trên độ đo trung tâm trung gian. Độ đo trung tâm trung gian là một chỉ số quan trọng trong việc xác định vai trò của các đỉnh trong mạng. Các đỉnh có cùng giá trị độ đo này được coi là tương đương và có thể kết hợp thành một đỉnh đại diện. Thuật toán REG (Reduce Equivalence Graph) được đề xuất để thực hiện quá trình này, giúp giảm đáng kể kích thước đồ thị mà vẫn bảo toàn cấu trúc cộng đồng.
2.1. Tính chất của độ đo trung tâm trung gian
Độ đo trung tâm trung gian đo lường mức độ quan trọng của một đỉnh trong việc kết nối các đỉnh khác trong mạng. Các đỉnh có giá trị độ đo cao thường đóng vai trò trung gian trong các đường đi ngắn nhất. Việc xác định các đỉnh tương đương dựa trên độ đo này giúp tạo ra các lớp đỉnh có thể kết hợp mà không làm mất đi tính chất cộng đồng của mạng.
2.2. Thuật toán REG và thực nghiệm
Thuật toán REG được thiết kế để rút gọn đồ thị bằng cách kết hợp các đỉnh tương đương dựa trên độ đo trung tâm trung gian. Các thực nghiệm được thực hiện trên các bộ dữ liệu mạng xã hội lớn cho thấy thuật toán này giảm đáng kể số lượng đỉnh và cạnh mà vẫn duy trì được cấu trúc cộng đồng ban đầu. Kết quả so sánh với các thuật toán truyền thống cũng cho thấy sự cải thiện về hiệu suất tính toán.
III. Ứng dụng thuật toán rút gọn đồ thị trong phát hiện cộng đồng
Chương này trình bày việc áp dụng các thuật toán rút gọn đồ thị vào bài toán phát hiện cộng đồng mạng xã hội. Các thuật toán như CDAB (Community Detection Algorithm based on Betweenness centrality) và LPAA (Label Propagation Algorithm on Abridged graph) được đề xuất để cải thiện hiệu suất phát hiện cộng đồng trên các đồ thị đã được rút gọn. Các thực nghiệm cho thấy các thuật toán này không chỉ giảm thời gian tính toán mà còn duy trì được chất lượng của các cộng đồng được phát hiện.
3.1. Thuật toán CDAB và hiệu quả
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. Kết quả thực nghiệm cho thấy thuật toán này cải thiện đáng kể thời gian tính toán so với các thuật toán truyền thống như Girvan-Newman (GN), đồng thời duy trì được độ chính xác trong việc phát hiện cộng đồng.
3.2. Thuật toán LPAA và ứng dụng
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. Các thực nghiệm cho thấy thuật toán này không chỉ giảm thời gian tính toán mà còn đạt được kết quả tương đương hoặc tốt hơn so với các thuật toán truyền thống như Label Propagation Algorithm (LPA). Điều này khẳng định tính hiệu quả của việc áp dụng rút gọn đồ thị trong bài toán phát hiện cộng đồng.
