1. Ý tưởng cốt lõi của PageRank
Web được biểu diễn dưới dạng đồ thị hữu hướng, trong đó:
+ Nút: Trang web.
+ Cạnh: Liên kết giữa các trang.
Tầm quan trọng (Rank): Một trang nhận nhiều liên kết từ các trang uy tín sẽ có rank cao. Rank được lan truyền qua các liên kết.
PageRank của trang A, ký hiệu PR(A) được tính bằng:
PR(A)=N1−d+d(i=1∑nC(Ti)PR(Ti))
N: Tổng số trang web.
d (Damping factor, thường là 0.85): Xác suất người dùng tiếp tục click liên kết (thay vì nhảy ngẫu nhiên đến trang khác).
T1,T2,...,Tn: Các trang liên kết đến A
C(Ti): Số liên kết ra từ trang Ti.
3. Quy trình tính toán
Khởi tạo: Gán giá trị ban đầu PR = 1/N cho mọi trang
Lập cập nhật:
+ Tính PageRank mới cho từng trang dựa trên công thức.
+ Kiểm tra độ hội tụ (sai số giữa các lần lặp < ngưỡng cho phép, ví dụ 10−6)
Dừng: Khi hội tụ hoặc đạt số lần lặp tối đa.
Ví dụ minh họa: PageRank hoạt động thông qua một đồ thị đơn giản gồm 3 trang web: A, B, và C với các liên kết như sau
+ Trang A liên kết đến B và C.
+ Trang B liên kết đến C.
+ Trang C liên kết đến A.
Bước 1: Mô hình hóa đồ thị
Biểu diễn đồ thị liên kết:
+ A → B, C
+ B → C
+ C → A
Bước 2: Khởi tạo giá trị PageRank ban đầu
Giả sử giá trị ban đầu của mỗi trang là:
PR(A)=PR(B)=PR(C)=31≈0.3333
Do tổng số trang có N = 3
Bước 3: Áp dụng công thức PageRank
Công thức tổng quát:
PR(u)=N1−d+d⋅v∈trang lieˆn keˆˊt đeˆˊn u∑C(v)PR(v)
Với d =0.85 (damping factor).
Lần lặp 1:
PR(A) nhận giá trị từ C (vì chỉ có C liên kết đến A):
PR(A)=31−0.85+0.85⋅(1PR(C))=30.15+0.85⋅0.3333≈0.05+0.2833=0.3333
PR(B) nhận giá trị từ A:
PR(B)=30.15+0.85⋅(2PR(A))=0.05+0.85⋅(20.3333)≈0.05+0.1417=0.1917
PR(C) nhận giá trị từ A và B:
PR(C)=30.15+0.85⋅(2PR(A)+1PR(B))≈0.05+0.85⋅(0.1667+0.1917)≈0.05+0.3042=0.3542Lần lặp 2:
Sử dụng giá trị mới từ lần lặp 1:
PR(A) = 0.3333
PR(B) = 0.1917
PR(C) = 0.3542
PR(A):
PR(A)=0.05+0.85⋅10.3542≈0.05+0.3011=0.3511
PR(B):
PR(B)=0.05+0.85⋅20.3511≈0.05+0.1493=0.1993
PR(C):
PR(C)=0.05+0.85⋅(20.3511+10.1993)≈0.05+0.85⋅(0.1756+0.1993)≈0.05+0.3183=0.3683
Lần lặp 3:
Sử dụng giá trị mới từ lần lặp 2:
PR(A) = 0.3511
PR(B) = 0.1993
PR(C) = 0.3683
PR(A):
PR(A)=0.05+0.85⋅10.3683≈0.05+0.3131=0.3631
PR(B):
PR(B)=0.05+0.85⋅20.3631≈0.05+0.1543=0.2043
PR(C):
PR(C)=0.05+0.85⋅(20.3631+10.2043)≈0.05+0.85⋅(0.1816+0.2043)≈0.05+0.3277=0.3777
Tiếp tục lặp cho đến khi gần điểm hội tụ:
Sau khoảng 10–20 lần lặp, các giá trị sẽ dần ổn định. Kết quả hội tụ cuối cùng có thể gần:
PR(A) ≈ 0.37
PR(B) ≈ 0.20
PR(C) ≈ 0.43
Bước 4: Giải thích kết quả
+ Trang C có PageRank cao nhất vì nhận được liên kết từ cả A và B.
+ Trang A nhận PageRank từ C (trang có uy tín cao).
+ Trang B có PageRank thấp nhất vì chỉ nhận liên kết từ A, và A chia sẻ rank cho cả B và C.
4. Xác định điểm hội tụ trong thuật toán PageRank
Thuật toán PageRank sử dụng phương pháp lặp để cập nhật giá trị PageRank. Quá trình dừng lại khi sự thay đổi giữa các lần lặp liên tiếp đủ nhỏ, đạt ngưỡng hội tụ (thường ký hiệu là ϵ). Công thức kiểm tra:
∥PRnew−PRold∥<ϵ
Trong đó:
: Chuẩn (norm) để đo độ sai lệch (thường dùng L1, L2, hoặc chuẩn vô cùng).
: Giá trị ϵ thường được chọn trong khoảng 10^-6 đến 10^-10 cho độ chính xác cao. Google sử dụng ϵ ≈ 10^-8 để cân bằng giữa độ chính xác và tốc độ.
4.1. Các loại chuẩn phổ biến
+ Chuẩn L1 (Tổng tuyệt đối)
∥PRnew−PRold∥1=i=1∑N∣PRnew(i)−PRold(i)∣
Dừng khi tổng sai lệch tuyệt đối < ϵ
+ Chuẩn L2 (Euclidean)
∥PRnew−PRold∥2=i=1∑N(PRnew(i)−PRold(i))2
Dừng khi căn bậc hai tổng bình phương sai lệch < ϵ
+ Chuẩn vô cùng (Max norm)
∥PRnew−PRold∥∞=imax∣PRnew(i)−PRold(i)∣
Dừng khi sai lệch lớn nhất giữa các trang < ϵ
4.2. Ví dụ minh họa
Giả sử sau 2 lần lặp, giá trị PageRank của 3 trang A, B, C thay đổi như sau:
Lần lặp 1: PR(A) = 0.3333, PR(B) = 0.1917, PR(C) = 0.3542
Lần lặp 2: PR(A) = 0.3511, PR(B) = 0.1993, PR(C) = 0.3683
Tính chuẩn L1:
∣0.3511 − 0.3333∣ + ∣0.1993 − 0.1917∣ + ∣0.3683 − 0.3542∣ = 0.0178 + 0.0076 + 0.0141 = 0.0395
Nếu ϵ = 0.01, quá trình lặp tiếp tục vì 0.0395 > 0.01.
