KẾT QUẢ ĐỀ XUẤT THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI

Tóm tắt

Hiện nay, phát hiện cộng đồng trên mạng xã hội là một hướng nghiên cứu đang được nhiều nhà khoa học quan tâm. Đã có rất nhiều thuật toán được đề xuất, nhưng một trong những vấn đề cần phải khắc phục đối với các mạng xã hội là trong thực tế số lượng đỉnh và cạnh của đồ thị cực kỳ lớn dẫn tới khối lượng tính toán trong các thuật toán rất lớn, khó đáp ứng được với yêu cầu thực tiễn. Trong bài báo này, chúng tôi đề xuất một giải pháp mới dựa trên tính chất của một số đỉnh đặc biệt có trên đồ thị, từ đó đưa ra thuật toán biến đổi đồ thị ban đầu về dạng rút gọn tương đương nhằm giảm kích thước của đồ thị, đồng thời kết hợp với kỹ thuật lan truyền nhãn, xây dựng hàm heuristic để tăng tốc độ xử lý cho thuật toán phát hiện cộng đồng. Kết quả thực nghiệm trên các bộ dữ liệu chuẩn cho thấy so với phương pháp lan truyền nhãn gốc LPA thời gian xử lý trung bình giảm xuống còn 85,5%  trong khi đó chất lượng cộng đồng tăng lên trung bình là 1,145 lần, từ đó đã khẳng định được tính hiệu quả của thuật toán đề xuất.