NGHIÊN CỨU CÁC THUẬT TOÁN ĐỂ XÁC ĐỊNH CÁC CỘNG ĐỒNG TRONG MẠNG

Tóm tắt

Việc phát hiện cấu trúc nhóm trong các liên kết mạng đóng vai trò quan trọng và được ứng dụng trong nhiều lĩnh vực thực tiễn chẳng hạn như việc nhóm và phân loại các proteins có cấu trúc, chức năng tương tự với nhau hoặc nhóm những người có cùng sở thích hoặc mối quan hệ nào đó trên mạng xã hội một cách tự động để giúp các nhà phân tích, quản lý đưa ra các phương pháp chiến lược, hoạch định đối với từng nhóm. Tuy nhiên, việc tự động phát hiện cấu trúc trên vẫn còn gặp nhiều khó khăn do cấu trúc mạng vô cùng lớn cũng như mối quan hệ phức tạp giữa các thực thể với nhau. Một cá nhân có thể tham gia nhiều nhóm cùng lúc trong mạng. Trong bài báo này, tác giả nghiên cứu một số thuật toán tự động phát hiện cấu trúc nhóm trong mạng dựa trên phân tích các mối quan hệ giữa các nút mạng (hay còn gọi là edge betweenness centrality). Tiêu chí để so sánh các thuật toán với nhau dự trên giá trị mođun (Modularity), giá trị này dùng để đánh giá chất lượng việc tự động phân nhóm. Ngoài ra, tác giả cũng đánh giá ưu điểm, nhược điểm của từng thuật toán đối với mỗi mạng có cấu trúc khác nhau và đưa ra gợi ý để lựa chọn thuật toán phù hợp. Để làm rõ tính ưu việt của từng thuật toán, nhóm tác giả tiến hành chạy từng thuật toán trên các tập dữ liệu khác nhau, bao gồm dữ liệu Les Misérables của Victor Hugo, dữ liệu về mạng lưới các diễn viên trong một bộ phim, dữ liệu về các tác giả trong cùng một bài báo và dữ liệu về mạng tương tác giữa các protein.