Thuật toán PageRank và triển khai Python

PageRank (Google) tính độ quan trọng của trang web dựa trên cấu trúc liên kết. Web = đồ thị có hướng (node=trang, edge=link).

Ý tưởng cốt lõi

• Trang quan trọng nếu nhiều trang quan trọng khác trỏ đến nó.
• Điểm PageRank = xác suất surfer ngẫu nhiên đang ở trang đó (0-1).
• Công thức lặp: PR(p) = (1-d)/N + d × Σ PR(q)/L(q)

Trong đó: d = damping factor (thường 0.85), N = tổng số trang, L(q) = số link ra từ trang q.

Triển khai với NumPy (ví dụ 3 trang)

import numpy as np
from fractions import Fraction

def display_format(vec, dec=3):
    return np.round(vec.astype(float), dec)

# Ma trận chuyển tiếp (column-stochastic)
# Trang 0 → 2, Trang 1 → 0, Trang 2 → 0,1
Mat = np.matrix([[0,     0,   1],
                 [1/2,   0,   0],
                 [1/2,   1,   0]])

# Ma trận teleport (random jump)
dp = Fraction(1,3)
Ex = np.full((3,3), dp)

beta = 0.7
Al = beta * Mat + (1-beta) * Ex

# Vector rank ban đầu
r = np.matrix([dp, dp, dp]).T

for i in range(100):
    prev = r.copy()
    r = Al * r
    print(f"Iter {i+1}:", display_format(r, 3))
    if np.allclose(prev, r):
        break

print("Final:", display_format(r, 3))
print("Sum:", np.sum(r))

Kết quả

Iter 1: [[0.333] [0.217] [0.45 ]]
Iter 2: [[0.415] [0.217] [0.368]]
...
Iter 14: [[0.375] [0.231] [0.393]]
Final: [[0.375] [0.231] [0.393]]
Sum: 1.0

Ứng dụng thực tế

• Dùng networkx.pagerank() cho đồ thị lớn.
• Xếp hạng bài viết,推荐系统, phân tích mạng xã hội.
• Xử lý dangling nodes (trang không link ra).