Luận văn Thạc sĩ Toán học: Một số thuật toán tìm kiếm cộng đồng mạng cho mạng có hướng sử dụng phương pháp phổ và bước đi ngẫu nhiên

Luận văn này tập trung vào vấn đề quan trọng là tìm kiếm cộng đồng trong các mạng có hướng, một lĩnh vực ít được nghiên cứu so với mạng vô hướng. Nghiên cứu khám phá các thuật toán sử dụng phương pháp phổ và bước đi ngẫu nhiên để xác định cấu trúc cộng đồng trong các hệ thống phức tạp này.

Luận văn này hướng đến các nhà nghiên cứu, học viên cao học và chuyên gia trong các lĩnh vực toán ứng dụng, khoa học máy tính, khoa học mạng và phân tích dữ liệu, những người quan tâm đến các thuật toán tiên tiến để tìm kiếm cộng đồng, đặc biệt trong cấu trúc đồ thị có hướng.

Luận văn "MỘT SỐ THUẬT TOÁN TÌM KIẾM CỘNG ĐỒNG MẠNG CHO MẠNG CÓ HƯỚNG SỬ DỤNG PHƯƠNG PHÁP PHỔ VÀ BƯỚC ĐI NGẪU NHIÊN" của Nguyễn Hải Tuấn, một luận văn Thạc sĩ Toán học tại Học viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam (năm 2024), đi sâu vào các kỹ thuật tiên tiến để xác định cấu trúc cộng đồng trong đồ thị có hướng. Nghiên cứu bắt đầu bằng việc trình bày các kiến thức nền tảng về lý thuyết đồ thị, đại số tuyến tính và các mô hình sinh đồ thị ngẫu nhiên. Sau đó, luận văn tập trung khám phá hai hướng tiếp cận chính để tìm kiếm cộng đồng trong mạng có hướng: các phương pháp dựa trên bước đi ngẫu nhiên và các phương pháp phổ. Phần các phương pháp dựa trên bước đi ngẫu nhiên trình bày chi tiết các thuật toán như Walktrap và K-Means, sử dụng khái niệm "thời điểm chạm" và khoảng cách "Thời gian chuyển Euclid (ECT)". Ý tưởng cốt lõi là các đỉnh thuộc cùng một cộng đồng sẽ có thời điểm chạm tương tự hoặc khoảng cách ECT ngắn hơn. Kết quả thực nghiệm trên cả mạng tổng hợp (mô hình Gaussian và Planted-l) và mạng thực tế cho thấy hiệu quả của các thuật toán này, đặc biệt là K-Means với khoảng cách ECT thể hiện hiệu suất ổn định và vượt trội hơn so với các phương pháp khác, nhất là đối với các mạng thưa. Đối với các phương pháp phổ, luận văn giới thiệu thuật toán Phân tích thành phần chính phi tuyến (NL-PCA), áp dụng các tính chất phổ (giá trị riêng và vector riêng) của ma trận Diplacian để ánh xạ các đỉnh vào không gian chiều thấp hơn, từ đó thực hiện phân cụm bằng thuật toán K-Means. Các thí nghiệm cho thấy NL-PCA đạt hiệu suất tốt, đặc biệt khi số lượng cộng đồng tăng lên, và nhìn chung vượt trội so với các thuật toán dựa trên phương pháp phổ khác cho đồ thị có hướng. Một đóng góp quan trọng của luận văn là việc nghiên cứu mối liên hệ phức tạp giữa các khoảng cách dựa trên bước đi ngẫu nhiên và các phương pháp phổ. Luận văn chứng minh toán học cách các thời điểm chạm và khoảng cách ECT có thể được biểu diễn thông qua các giá trị và vector kỳ dị của ma trận Diplacian, từ đó thiết lập một liên kết lý thuyết giữa hai hướng tiếp cận tưởng chừng khác biệt này. Điều này mang lại cái nhìn sâu sắc hơn về cơ chế cơ bản của việc tìm kiếm cộng đồng trong mạng có hướng. Các đánh giá thực nghiệm, được tiến hành trên nhiều bộ dữ liệu tổng hợp và thực tế với các kích thước khác nhau (nhỏ, trung bình, lớn), đã liên tục chỉ ra điểm mạnh và hạn chế của từng thuật toán. Chẳng hạn, Walktrap hoạt động tốt trên đồ thị Gaussian cỡ nhỏ, trong khi K-Means với ECT vượt trội trên mô hình Planted-l và các mạng thực thưa. NL-PCA cũng cho thấy kết quả đầy hứa hẹn, đặc biệt trên các mạng lớn, dày đặc hơn. Hàm Modularity được sử dụng làm tiêu chí đánh giá chính. Luận văn kết thúc bằng cách tóm tắt các phát hiện này và đề xuất các hướng nghiên cứu trong tương lai, nhấn mạnh tiềm năng phát triển các thuật toán tìm kiếm cộng đồng mới và mạnh mẽ hơn cho đồ thị có hướng bằng cách khai thác sâu hơn sự kết hợp giữa các tính chất của bước đi ngẫu nhiên và phương pháp phổ.