Tên luận án:
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
Ngành:
Hệ thống thông tin (Mã số: 9.48.01.04)
Tóm tắt nội dung tài liệu:
Luận án này tập trung giải quyết thách thức về việc phát hiện cộng đồng hiệu quả trong các mạng xã hội lớn và phức tạp, nơi các thuật toán truyền thống thường gặp khó khăn về chi phí tính toán và thời gian thực hiện. Để khắc phục hạn chế này, nghiên cứu đề xuất các kỹ thuật rút gọn đồ thị mới nhằm giảm thiểu kích thước đồ thị trong khi vẫn bảo toàn các tính chất cấu trúc quan trọng của mạng xã hội.
Các đóng góp chính của luận án bao gồm:
- Đề xuất thuật toán **REG (Reduce Equivalence Graph)** để rút gọn đồ thị dựa trên việc xác định và kết hợp các lớp đỉnh tương đương theo độ đo trung tâm trung gian. Thuật toán này giúp giảm đáng kể số đỉnh và cạnh của đồ thị mà vẫn duy trì các tính chất cơ bản.
- Phát triển thuật toán **FBC (Fast algorithm for Betweenness Centrality)** nhằm cải thiện đáng kể thời gian tính toán độ đo trung tâm trung gian trên đồ thị mạng xã hội, đặc biệt hiệu quả trên các mạng có kích thước lớn.
- Đề xuất thuật toán **CDAB (Community Detection Algorithm based on Betweenness centrality)** để phát hiện cộng đồng nhanh chóng trên đồ thị đã được rút gọn, dựa trên độ đo trung tâm trung gian. Thuật toán này cho thấy hiệu suất vượt trội so với các thuật toán hiện có như Girvan-Newman và MAA.
- Giới thiệu thuật toán **LREN (Label based Reduce Equivalence Nodes)** để rút gọn đồ thị dựa vào nguyên lý lan truyền nhãn, giúp gom nhóm các đỉnh có nhãn tương đồng thành một đỉnh đại diện.
- Phát triển thuật toán **LPAA (Label Propagation Algorithm on Abridged graph)** để phát hiện cộng đồng nhanh và hiệu quả trên đồ thị đã rút gọn theo nguyên lý lan truyền nhãn, thể hiện ưu thế so với LPA và OLP.
Các thực nghiệm trên nhiều bộ dữ liệu mạng xã hội lớn (Com-Amazon, Com-DBLP, Com-Youtube) đã chứng minh rằng các thuật toán được đề xuất không chỉ nhanh hơn mà còn hiệu quả hơn trong việc phát hiện cộng đồng, đồng thời bảo toàn chất lượng cộng đồng được phát hiện thông qua các độ đo như Modularity Q, F-measure và NMI. Luận án mở ra hướng phát triển cho việc xử lý dữ liệu lớn, phát hiện cộng đồng chồng chéo và sử dụng các thuật toán song song trong tương lai.
Mục lục chi tiết:
- 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.