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

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

Tác giả: Nguyễn Hải Tuấn

Lĩnh vực: Toán học (Luận văn Thạc sĩ Toán học)

Nội dung tài liệu:

Luận văn tập trung nghiên cứu các thuật toán tìm kiếm cộng đồng mạng cho đồ thị có hướng, một lĩnh vực có nhiều ứng dụng thực tế nhưng còn ít nghiên cứu so với đồ thị vô hướng. Luận văn đề xuất và phân tích hai phương pháp tiếp cận chính: sử dụng bước đi ngẫu nhiên để định nghĩa khoảng cách giữa các đỉnh và sử dụng phương pháp phổ. Cụ thể, luận văn đi sâu vào các thuật toán như Walktrap và K-Means dựa trên khái niệm thời điểm chạm và khoảng cách Euclid, cũng như các phương pháp dựa trên phân tích giá trị kỳ dị (SVD) và phương pháp phổ. Một phần quan trọng của luận văn là khám phá mối liên hệ giữa các phương pháp này, nhằm đánh giá tính hiệu quả và đưa ra các cải tiến. Ngoài ra, luận văn còn đề cập đến các mô hình sinh đồ thị ngẫu nhiên như l-planted và Gaussian để đánh giá chất lượng của thuật toán.

Mục lục chi tiết:

• Mở đầu
• Chương 1: Kiến thức chuẩn bị
• Chương 2: Tìm kiếm cộng đồng mạng cho đồ thị có hướng sử dụng bước đi ngẫu nhiên
• Chương 3: Tìm kiếm cộng đồng mạng cho đồ thị có hướng sử dụng phương pháp phổ
• Chương 4: Mối liên hệ giữa khoảng cách sử dụng bước đi ngẫu nhiên và phương pháp phổ
• Kết luận