Nghiên cứu các thuật toán rút gọn đồ thị và ứng dụng để phát hiện cộng đồng trên mạng xã hội

Abstract

Các đóng góp chính của luận án: • Đề xuất thuật toán REG (Reduce Equivalence Graph) rút gọn đồ thị dựa vào lớp tương đương của các đỉnh theo độ đo trung tâm trung gian. Thực hiện các thực nghiệm đánh giá tính hiệu quả và thời gian thực hiện của thuật toán đề xuất so với thuật toán điển hình sử dụng độ đo trung tâm trung gian. • Đề xuất thuật toán FBC (Fast algorithm for Betweenness Centrality) cải tiến thời gian tính độ đo trung tâm trung gian và đề xuất thuật toán CDAB (Community Detection Algorithm based on Betweenness centrality) cải tiến thời gian phát hiện các cộng đồng trên đồ thị mạng xã hội rút gọn dựa vào độ đo trung tâm trung gian. Thực hiện các thực nghiệm đánh giá tính hiệu quả và thời gian thực hiện của thuật toán đề xuất CDAB so với thuật toán gốc Girvan-Newman (GN) và thuật toán điển hình gần đây. • Đề xuất thuật toán LREN (Label based Reduce Equivalence Nodes) rút gọn đồ thị dựa vào lớp đỉnh tương đương theo nguyên lý lan truyền nhãn và phát triển thuật toán LPAA (Label Propagation3 Algorithm on Abridged graph) cải tiến thời gian phát hiện các cộng đồng dựa vào nguyên lý lan truyền nhãn. Thực hiện các thực nghiệm đánh giá tính hiệu quả và thời gian thực hiện của thuật toán LPAA so với thuật toán gốc Label Propagation Algorithm (LPA) và thuật toán điển hình gần đây. 7. Bố cục của luận án Luận án được tổ chức thành 3 chương: Chương 1. Tổng quan rút gọn đồ thị và phát hiện cộng đồng trên mạng xã hội Chương 2. Thuật toán rút gọn đồ thị mạng xã hội dựa vào độ đo trung tâm trung gian và nguyên lý lan truyền nhãn. Chương 3. Áp dụng thuật toán rút gọn đồ thị để phát hiện cộng đồng trên mạng xã hội. Cuối cùng là kết luận và các hướng phát triển tiếp theo.