SỬ DỤNG ĐỘ TRUNG GIAN CỦA CÁC CẠNH PHÁT HIỆN CỘNG ĐỒNG GỐI NHAU

Tóm tắt

Bài báo đề xuất một phương pháp cải tiến nhằm phát hiện các cộng đồng gối nhau trên đồ thị mạng xã hội dựa trên độ trung gian của cạnh. Nghiên cứu giới thiệu các khái niệm liên quan đến đồ thị mạng xã hội, độ đo trung tâm của đỉnh, của đồ thị, độ trung gian của cạnh, phần thực hiện thuật toán GN (Girvan-Newman) với phép duyệt BFS (Breadth-First Search) và cải tiến GN sử dụng độ đo trung gian cạnh để tỉa dần các đỉnh/cạnh không cần thiết và tối ưu hóa trình tự lựa chọn đỉnh để phát hiện các cộng đồng gối nhau trên đồ thị mạng hiệu quả.