Luận văn thạc sĩ: Nghiên cứu hiệu năng thuật toán Personalized PageRank

• Tác giả: Nguyễn Tuấn Minh
• Người hướng dẫn: PGS. Thoại Nam
• Trường học: Đại học Quốc gia TP. HCM
• Chuyên ngành: Khoa học Máy tính
• Đề tài: Nghiên cứu hiệu năng giải thuật Personalized PageRank
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2022
• Địa điểm: TP. Hồ Chí Minh

• LỜI CẢM ƠN
• TÓM TẮT LUẬN VĂN
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: GIỚI THIỆU
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 2.1. Giải thuật PageRank
• 2.2. Giải thuật Personalized PageRank
• 2.3. Giải thuật Personalized PageRank trong Spark
• 2.4. Thực hiện cho bài toán thực tiễn
• 3. CHƯƠNG 3: BÀI TOÁN PHÂN TÍCH ẢNH HƯỞNG TRÊN ĐỒ THỊ
• 3.1. Giới thiệu phân tích bài toán và giải thuật Personalized PageRank
• 3.2. Bài toán phân tích ảnh hưởng trên đồ thị
• 4. CHƯƠNG 4: TRIỂN KHAI VÀ ĐÁNH GIÁ
• 4.1. Môi trường thực nghiệm sử dụng Spark
• 4.2. Bộ dữ liệu thực hiện
• 4.3. Kịch bản đánh giá
• 4.3.1. Kịch bản 1: Thực hiện tính toán trên một nút nguồn
• 4.3.2. Kịch bản 2: Thực hiện đo trên một tập nút nguồn
• 4.3.3. Kịch bản 3: Thực hiện lựa chọn hai tập nút nguồn con khác nhau (ba nút nguồn VSR (xanh) và hai nút nguồn VSR(đỏ))
• 4.3.4. Kịch bản 4: Đánh giá thời gian thực hiện giai đoạn 1
• 4.3.5. Kịch bản 5: Thực hiện đánh giá trên tổ hợp trên ba nút nguồn VSR(xanh) và hai nút nguồn VSR(đỏ)
• 4.3.6. Kịch bản 6: Thực hiện đánh giá thay đổi tốc độ ở tập nút nguồn VSR(đỏ)
• 4.3.7. Phân tích sự thay đổi về VInterfering theo từng bước lan truyền
• 5. CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG MỞ RỘNG
• TÀI LIỆU THAM KHẢO
• PHẦN LÝ LỊCH TRÍCH NGANG

I. Giới thiệu về thuật toán PageRank

Thuật toán PageRank là một trong những thuật toán quan trọng trong lĩnh vực khoa học máy tính, đặc biệt là trong tìm kiếm thông tin và phân tích mạng xã hội. Nó được phát triển bởi Google để xếp hạng các trang web dựa trên độ quan trọng của các liên kết. Hiệu năng thuật toán này được đo bằng cách xác định số lượng và chất lượng các liên kết đến một trang, từ đó xác định vị trí của nó trong kết quả tìm kiếm. Theo nghiên cứu, trang có PageRank cao thường xuất hiện ở vị trí cao hơn trong kết quả tìm kiếm, tạo ra tác động lớn đến lưu lượng truy cập và danh tiếng của trang web. Việc áp dụng thuật toán PageRank không chỉ giới hạn trong lĩnh vực tìm kiếm mà còn mở rộng ra nhiều lĩnh vực khác như phân tích mạng xã hội, khai thác dữ liệu và công nghệ thông tin.

II. Giải thuật Personalized PageRank

Giải thuật Personalized PageRank (PPR) là một biến thể của PageRank, cho phép đo lường mức độ quan trọng của các nút trong một đồ thị dựa trên một nút nguồn cụ thể. PPR được sử dụng rộng rãi trong các ứng dụng như tìm kiếm thông tin, giới thiệu sản phẩm và phân tích mạng xã hội. Khác với PageRank truyền thống, PPR chỉ tính toán khoảng cách giữa nút nguồn và các nút khác trong đồ thị, từ đó xác định mức độ tương tác và ảnh hưởng giữa các nút. Điều này giúp cải thiện độ chính xác trong việc tìm kiếm thông tin liên quan và tối ưu hóa các thuật toán đề xuất. Một trong những thách thức lớn của PPR là tính toán hiệu quả trong các đồ thị lớn, nơi mà số lượng nút và liên kết có thể lên đến hàng triệu.

III. Phân tích hiệu năng thuật toán Personalized PageRank trong Spark

Trong môi trường Apache Spark, việc triển khai Personalized PageRank mang lại nhiều lợi ích về hiệu suất tính toán. Spark cho phép xử lý song song các tác vụ, giúp giảm thời gian thực hiện cho các bài toán lớn. Tuy nhiên, việc triển khai này cũng gặp một số hạn chế, như chỉ cho phép chỉ định một nút nguồn duy nhất và không thể gán trọng số cho các nút nguồn. Điều này hạn chế khả năng mô hình hóa các mối quan hệ phức tạp trong đồ thị. Dù vậy, PPR trong Spark vẫn có thể được áp dụng hiệu quả cho nhiều bài toán thực tiễn, từ phân tích mạng xã hội đến phát hiện cộng đồng trong dữ liệu lớn. Việc tối ưu hóa thuật toán và cải thiện khả năng mở rộng sẽ là những hướng nghiên cứu quan trọng trong tương lai.

IV. Ứng dụng và giá trị thực tiễn của thuật toán Personalized PageRank

Giải thuật Personalized PageRank đã được áp dụng trong nhiều lĩnh vực khác nhau, từ khoa học máy tính đến sinh học. Nó cho phép các nhà nghiên cứu phân tích mối quan hệ giữa các thực thể trong một hệ thống phức tạp, giúp hiểu rõ hơn về cấu trúc và sự tương tác của các nút trong đồ thị. Các ứng dụng cụ thể bao gồm phát hiện cộng đồng trong mạng xã hội, tối ưu hóa quảng cáo trực tuyến và phân tích dữ liệu lớn. Việc sử dụng PPR không chỉ giúp cải thiện độ chính xác trong việc tìm kiếm thông tin mà còn hỗ trợ đưa ra các quyết định thông minh hơn trong nhiều lĩnh vực khác nhau. Điều này chứng tỏ giá trị thực tiễn của thuật toán Personalized PageRank trong việc giải quyết các vấn đề phức tạp trong đời sống hàng ngày.