ỨNG DỤNG PHƯƠNG PHÁP PHÂN CỤM PHỔ TRONG BÀI TOÁN PHÁT HIỆN CỘNG ĐỒNG

Tóm tắt

Ngày nay, phát hiện cộng đồng trên một mạng xã hội đang là hướng nghiên cứu quan trọng trong lĩnh vực khoa học máy tính. Mạng xã hội thường được biểu diễn dưới dạng cấu trúc dữ liệu đồ thị. Chính vì vậy, phát hiện cộng đồng trên mạng xã hội chủ yếu gắn liền với bài toán phân cụm trên đồ thị. Để giải quyết bài toán, đã có rất nhiều thuật toán được quan tâm nghiên cứu. Trong bài báo này, nhóm tác giả sẽ trình bày các kết quả nghiên cứu mới theo hướng tiếp cận sử dụng khái niệm spectrum (phổ) để đưa bài toán phân cụm đồ thị tổng quát về bài toán phân cụm trên véc tơ riêng số thực nhằm giảm số chiều của tập dữ liệu, đồng thời kết hợp kỹ thuật tối ưu hóa hàm Min-cut nhờ sử dụng ma trận Laplace. Hướng tiếp cận này sẽ giảm độ phức tạp tính toán của thuật toán phát hiện cấu trúc cộng đồng trên mạng xã hội. Các kết quả thực nghiệm chạy trên các bộ số liệu thực tế đã khẳng định tính hữu hiệu của thuật toán đề xuất.