Luận văn Thạc sĩ Toán ứng dụng: Tìm hiểu về các thuật toán phân cụm cho các đồ thị lớn hai phần

Luận văn được chia thành bốn chương: Chương 1 Kiến thức chuẩn bị; Chương 2 Thuật toán phân cụm trên đồ thị lớn; Chương 3 Thuật toán phân cụm trên đồ thị lớn hai phần; Chương 4 Một số thí nghiệm.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Toán ứng dụng: Tìm hiểu về các thuật toán phân cụm cho các đồ thị lớn hai phầnBỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌCVÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ Nguyễn Hương Quỳnh TÌM HIỂU VỀ CÁC THUẬT TOÁN PHÂN CỤM CHO CÁC ĐỒ THỊ LỚN HAI PHẦN LUẬN VĂN THẠC SĨ TOÁN ỨNG DỤNG Hà Nội - 2023 ii LỜI CẢM ƠN Đầu tiên, tôi xin được tỏ lòng biết ơn sâu sắc nhất của mình tới PGS.TSKH. Phan ThịHà Dương, cô đã trực tiếp hướng dẫn và giúp đỡ tôi tìm ra đề tài luận văn cũng như địnhhình hướng nghiên cứu. Không chỉ là người hướng dẫn khoa học tận tâm, cô còn cho tôinhững lời khuyên, động viên, khích lệ giúp tôi trưởng thành hơn trong cuộc sống. Tôi xin chân thành cảm ơn TS. Đỗ Duy Hiếu - Viện Toán học đã hướng dẫn, góp ý vàgiúp đỡ tôi rất nhiều trong quá trình tôi đọc tài liệu và làm luận văn. Tôi xin chân thành cảm ơn nhóm seminar đã đồng hành cùng trong việc tìm hiểu vềkiến thức liên quan đến bài toán phân cụm cho đồ thị và góp ý cho tôi trong quá trình hoànthành luận văn. Tôi xin chân thành cảm ơn sự hỗ trợ của Công ty Cổ phần Tập đoàn Vingroup đã tàitrợ cho quá trình học tập của tôi trong hai năm qua. Tôi được hỗ trợ bởi Chương trình họcbổng Thạc sĩ, Tiến sĩ của Quỹ đổi mới sáng tạo Vingroup (VINIF), Viện Dữ liệu lớn, mã sốVINIF.2021.ThS.VTH.02 và VINIF.2022.ThS.076. Trong thời gian học tập tại Viện Toán học, tôi đã nhận được nhiều sự quan tâm, góp ý,hỗ trợ quý báu của các thầy cô, anh chị và bạn bè. Tôi xin được chân thành chân thành bàytỏ lòng biết ơn sâu sắc đến các thầy cô, anh chị và bạn bè. Tôi cũng xin trân trọng cảm ơn Viện Toán học và cơ sở đào tạo là Học viện Khoa họcvà Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã giúp đỡ và tạo điều kiệnthuận lợi về môi trường học tập cho tôi trong suốt quá trình thực hiện Luận văn này. Cuối cùng, tôi xin tỏ lòng biết ơn vô hạn tới gia đình tôi, bố mẹ luôn kiên nhẫn và thươngyêu tôi vô điều kiện. iiiMục lụcLời cam đoan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iLời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiMục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivMở đầu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1CHƯƠNG 1. KIẾN THỨC CHUẨN BỊ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Một số khái niệm về lý thuyết đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Khoa học mạng và cộng đồng mạng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.1. Khoa học mạng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.2. Cộng đồng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3. Nội dung chính của luận văn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8CHƯƠNG 2. CÁC THUẬT TOÁN PHÂN CỤM CHO ĐỒ THỊ LỚN . . 10 2.1. Động lực khoảng cách so với tiêu chí cộng đồng do người dùng xác định . . . . 10 2.2. Kiến thức liên quan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3. Mô hình tương tác địa phương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4. Thuật toán Attractor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5. Phân tích độ phức tạp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18CHƯƠNG 3. CÁC THUẬT TOÁN PHÂN CỤM CHO ĐỒ THỊ LỚN HAIPHẦN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1. Phát hiện cộng đồng trong mạng hai phần bằng động lực học khoảng cách . 19 3.1.1. Động lực khoảng cách trong Unipartite Networks . . . . . . . . . . . . . . . . . . . . 19 3.1.2. Động lực khoảng cách trong mạng hai phần . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2. Thuật toán phát hiện cộng đồng trên mạng hai phần: ComSim . . . . . . . . . . . . . 29 3.2.1. Hàm tương tự . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2.2. Thuật toán COMSIM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2.3. Cải tiến thuật toán COMSIM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 ivCHƯƠNG 4. MỘT SỐ THÍ NGHIỆM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.1. So sánh thuật toán Attractor với một số thuật toán khác . . . . . . . . . . . . . . . . . . . 34 4.1.1. Mạng tổng hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.1.2. Dữ liệu thực . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.1.3. Phát hiện cộ ...