Luận án Tiến sĩ Kỹ thuật: 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

Mục tiêu của luận án nhằm nghiên cứu phát triển và thực nghiệm thuật toán rút gọn đồ thị dựa vào lớp tương đương của các đỉnh trên đồ thị theo độ đo trung tâm trung gian và phương pháp rút gọn đồ thị theo nguyên lý lan truyền nhãn; phát triển thuật toán phát hiện nhanh các cộng đồng trên mạng xã hội sử dụng độ đo trung tâm trung gian và thuật toán phát hiện nhanh các cộng đồng trên mạng xã hội dựa trên tính chất của các lớp đỉnh tương đương theo nguyên lý lan truyền nhãn.

Nội dung trích xuất từ tài liệu:
Luận án Tiến sĩ Kỹ thuật: 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 BỘ THÔNG TIN VÀ TRUYỀN THÔNG HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG NGUYỄN XUÂN DŨNG 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 LUẬN ÁN TIẾN SĨ HỆ THỐNG THÔNG TIN HÀ NỘI - 2021 BỘ THÔNG TIN VÀ TRUYỀN THÔNG HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG NGUYỄN XUÂN DŨNG 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 CHUYÊN NGÀNH : HỆ THỐNG THÔNG TIN MÃ SỐ: 9.48.01.04 LUẬN ÁN TIẾN SĨ KỸ THUẬT NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS.TS Đoàn Văn Ban 2. TS. Đỗ Thị Bích Ngọc HÀ NỘI - 2021 LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong luận án là trung thực và chưa từng đượccông bố trong bất cứ công trình nào. TÁC GIẢ Nguyễn Xuân Dũng LỜI CẢM ƠN Qua luận án này tôi xin chân thành cảm ơn PGS.TS Đoàn Văn Ban vàTS. Đỗ Thị Bích Ngọc đã tận tình giúp đỡ, động viên, định hướng, hướng dẫntôi nghiên cứu và hoàn thành luận án này. Tôi xin chân thành cảm ơn các Thầy, Cô giáo trong Học viện Công nghệBưu chính Viễn thông đã tận tình giảng dạy và giúp đỡ tôi trong suốt khóa học.Tôi cũng xin cảm ơn PGS.TS Lê Nhật Thăng - Trưởng Khoa Đào tạo Sau Đạihọc của Học viện công nghệ bưu chính viễn thông, TS. Nguyễn Duy Phương -Trưởng Khoa Công nghệ thông tin của Học viện công nghệ bưu chính viễnthông và PGS.TS Phạm Thọ Hoàn - Giám đốc Trung tâm Khoa học Tính toáncủa Trường Đại học Sư phạm Hà Nội đã giúp đỡ tôi trong quá trình thực hiệnluận án. Tác giả chân thành mong nhận được những ý kiến đóng góp từ các Thầy,Cô giáo, các nhà khoa học và bạn bè đồng nghiệp. Trân trọng cám ơn. i MỤC LỤCMỤC MỤC............................................................................................................................................... iDANH MỤC CÁC CHỮ VIẾT TẮT................................................................................................. ivDANH MỤC CÁC KÍ HIỆU TOÁN HỌC........................................................................................ vDANH MỤC CÁC THUẬT NGỮ..................................................................................................... viDANH MỤC HÌNH VẼ.....................................................................................................................viiiDANH MỤC CÁC BẢNG.................................................................................................................. ixMỞ ĐẦU ................................................................................................................................................. 11. Tính cấp thiết của luận án.................................................................................................................... 12. Mục tiêu của luận án............................................................................................................................ 43. Đối tượng nghiên cứu của luận án...................................................................................................... 54. Phạm vi nghiên cứu của luận án ......................................................................................................... 55. Phương pháp nghiên cứu của luận án ................................................................................................ 56. Các đóng góp của luận án ................................................................................................................... 67. Bố cục của luận án ............................................................................................................................... 6CHƯƠNG 1. TỔNG QUAN RÚT GỌN ĐỒ THỊ VÀ PHÁT HIỆN CỘNG ĐỒNG TRÊNMẠNG XÃ HỘI ................................................................................................................................... 81.1. Mạng xã hội.......................................................................................................................81.2. Một số hệ số đo quan trọng trên đồ thị mạng xã hội .............................................. 10 1.2.1. Hệ số cố kết mạng............................................................................... 12 1.2.2. Các hệ số đo tính trung tâm của tác nhân ............................................ 121.3. Bài toán phát ...