I. Tổng quan về luận án
Luận án tập trung vào thuật toán rút gọn đồ thị và ứng dụng trong phát hiện cộng đồng trên mạng xã hội. Nghiên cứu này nhằm giải quyết thách thức về quy mô lớn của các mạng xã hội hiện đại, nơi các thuật toán truyền thống không còn hiệu quả. Mạng xã hội (Social Networks) đã trở thành một phần không thể thiếu trong cuộc sống, với các ứng dụng như Facebook, Twitter, và LinkedIn. Phân tích mạng xã hội (Social Network Analysis) là một lĩnh vực quan trọng, giúp hiểu rõ các mối quan hệ và cấu trúc xã hội. Phát hiện cộng đồng (Community Detection) là một nhiệm vụ trọng tâm, có ứng dụng rộng rãi trong nhiều lĩnh vực như xã hội học, sinh học, và kinh tế.
1.1. Tính cấp thiết của luận án
Sự phát triển nhanh chóng của mạng xã hội đã tạo ra các đồ thị có quy mô khổng lồ, gây khó khăn cho việc phân tích và phát hiện cộng đồng. Các thuật toán truyền thống không thể xử lý hiệu quả các đồ thị lớn do độ phức tạp tính toán cao. Luận án đề xuất các phương pháp rút gọn đồ thị để giảm thiểu kích thước đồ thị mà vẫn bảo toàn các tính chất quan trọng, từ đó cải thiện hiệu suất của các thuật toán phát hiện cộng đồng.
1.2. Mục tiêu của luận án
Mục tiêu chính của luận án là phát triển các thuật toán rút gọn đồ thị dựa trên độ đo trung tâm trung gian (Betweenness Centrality) và nguyên lý lan truyền nhãn (Label Propagation). Các thuật toán này nhằm giảm thiểu số lượng đỉnh và cạnh của đồ thị, đồng thời cải tiến các thuật toán phát hiện cộng đồng để hoạt động hiệu quả trên đồ thị rút gọn.
II. Các thuật toán rút gọn đồ thị
Luận án đề xuất hai thuật toán chính để rút gọn đồ thị: REG (Reduce Equivalence Graph) và LREN (Label based Reduce Equivalence Nodes). REG dựa trên độ đo trung tâm trung gian, trong khi LREN sử dụng nguyên lý lan truyền nhãn. Cả hai thuật toán đều nhằm mục đích giảm thiểu kích thước đồ thị bằng cách kết hợp các đỉnh tương đương thành một đỉnh đại diện, từ đó giảm độ phức tạp tính toán.
2.1. Thuật toán REG
Thuật toán REG tập trung vào việc rút gọn đồ thị dựa trên độ đo trung tâm trung gian. Các đỉnh có cùng giá trị độ đo này được coi là tương đương và được kết hợp thành một đỉnh đại diện. Phương pháp này giúp giảm đáng kể số lượng đỉnh và cạnh của đồ thị, đồng thời bảo toàn các tính chất quan trọng của cộng đồng.
2.2. Thuật toán LREN
Thuật toán LREN sử dụng nguyên lý lan truyền nhãn để xác định các đỉnh tương đương. Các đỉnh có cùng nhãn được kết hợp thành một đỉnh đại diện, giúp rút gọn đồ thị mà vẫn duy trì cấu trúc cộng đồng. Phương pháp này đặc biệt hiệu quả trong việc xử lý các đồ thị lớn với cấu trúc phức tạp.
III. Ứng dụng phát hiện cộng đồng
Luận án cũng đề xuất các thuật toán phát hiện cộng đồng hiệu quả trên đồ thị rút gọn, bao gồm CDAB (Community Detection Algorithm based on Betweenness centrality) và LPAA (Label Propagation Algorithm on Abridged graph). Các thuật toán này được thiết kế để hoạt động hiệu quả trên các đồ thị đã được rút gọn, giúp giảm thời gian tính toán mà vẫn đảm bảo chất lượng phát hiện cộng đồng.
3.1. Thuật toán CDAB
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. Phương pháp này cải tiến thời gian tính toán so với các thuật toán truyền thống như Girvan-Newman, đồng thời duy trì độ chính xác trong việc xác định cộng đồng.
3.2. Thuật toán LPAA
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. Phương pháp này giúp giảm thiểu thời gian tính toán so với thuật toán LPA truyền thống, đồng thời đảm bảo chất lượng phát hiện cộng đồng thông qua các độ đo như đơn thể mô đun Q và NMI (Normalized Mutual Information).
