PageRank – Thuật Toán Xếp Hạng Trang Web Bằng Power Iteration

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

PageRank tính điểm uy tín của mỗi nút trong đồ thị có hướng. Công thức: PR(u) = 1-dN + d ∑_{v ∈ Bu} PR(v)L(v)

Trong đó:

• d = 0.85: damping factor
• N: số nút
• B_u: tập nút trỏ vào u
• L(v): số cạnh ra của v

Dangling nodes (nút không có cạnh ra): phân phối đều PR sang tất cả nút.

Yêu cầu

def pagerank(adjacency_matrix: np.ndarray, d=0.85, max_iter=100, tol=1e-6) -> np.ndarray:
    # adjacency_matrix[i][j] = 1 if edge i -> j
    # Returns normalized PageRank scores summing to 1.0
    pass

Ràng buộc

• Thời gian chạy tối đa: 3000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào hợp lệ theo đúng kiểu dữ liệu và miền giá trị được mô tả.