Thuật toán Xếp hạng Đồ thị Liên kết PageRank với Power Iteration

Mục tiêu kiến thức

• Hiểu sâu mô hình chuỗi Markov và thuật toán PageRank kinh điển của Larry Page và Sergey Brin.
• Xử lý hiện tượng Nút cụt (Dangling Nodes / Dead Ends) - các trang web không có liên kết trỏ ra ngoài làm rò rỉ xác suất.
• Kết hợp Hệ số giảm xóc (Damping Factor d) mô phỏng hành vi ngẫu nhiên của người duyệt web (Random Surfer Model).
• Triển khai phương pháp Lặp lũy thừa (Power Iteration) vector hóa bằng NumPy cho tới khi hội tụ sai số chuẩn L₁.

Mô tả bài toán

Trong đồ thị web, một liên kết từ trang A tới trang B được coi là một "phiếu bầu" tín nhiệm cho trang B. Tuy nhiên, phiếu bầu từ các trang có uy tín cao sẽ có trọng số lớn hơn phiếu bầu từ các trang ít tên tuổi.

Công thức lặp PageRank cho đồ thị gồm N đỉnh: r^(t+1) = d · ( r^(t) P ) + 1 - dN 1 Trong đó:

• r^(t) ∈ R^{1 × N}: Vector phân phối xác suất tại bước t.
• d: Hệ số giảm xóc (thường chọn d = 0.85).
• P: Ma trận chuyển trạng thái ngẫu nhiên (Row-Stochastic Transition Matrix).
• Nếu đỉnh i có bậc ra k_i > 0: P_ij = A_ijk_i.
• Nếu đỉnh i là nút cụt (k_i = 0): P_ij = 1N cho mọi j (người dùng ngẫu nhiên chọn một trang bất kỳ trên toàn bộ mạng).

Hãy viết hàm: compute_pagerank(adj_matrix: np.ndarray, damping: float = 0.85, max_iter: int = 100, tol: float = 1e-6) -> np.ndarray

Yêu cầu thực hiện:

• Kiểm tra đầu vào:
• adj_matrix phải là mảng 2D hình vuông kích thước N × N (N ≥ 1). Nếu không, ném ValueError("adj_matrix must be a 2D square matrix").
• damping phải thỏa mãn 0.0 < damping < 1.0. Nếu không, ném ValueError("damping must be in (0, 1)").
• Khởi tạo:
• Khởi tạo vector PageRank ban đầu phân phối đều: r⁽⁰⁾ = [ 1N, 1N, …, 1N ].
• Xây dựng Ma trận Chuyển trạng thái P:
• Tính bậc ra của từng hàng: k_i = ∑_j=1^N A_ij.
• Với hàng k_i > 0: chia từng phần tử cho k_i.
• Với hàng k_i == 0 (nút cụt): gán toàn bộ hàng bằng 1N.
• Vòng lặp Power Iteration:
• Ở mỗi bước lặp, tính vector mới:

r_new = damping × (r · P) + 1.0 - dampingN

• Kiểm tra điều kiện hội tụ: ∑_i=1^N |r_new[i] - r[i]| < tol.
• Nếu thỏa mãn, dừng lặp sớm.
• Nếu chưa hội tụ, gán r = r_new và lặp tiếp tối đa max_iter lần.
• Chuẩn hóa đầu ra:
• Đảm bảo ∑_i=1^N r[i] == 1.0 (chia cho tổng nếu có sai số dấu phẩy động).
• Trả về mảng 1D np.ndarray kích thước N kiểu np.float64.

Ràng buộc

• Số lượng đỉnh đồ thị: 1 ≤ N ≤ 2000.
• Các giá trị trong adj_matrix là các số thực không âm ≥ 0.