Ma trận Markov và PageRank

~4 giờ · cần xong bài 7 (eigenvector, eigenvalue, phương trình đặc trưng) trước

Bài 7 dạy bạn eigenvector là vector không đổi hướng qua phép biến đổi. Bài 8 chỉ ra một eigenvector cụ thể — cái ứng với λ = 1 — chính là thứ Google dùng để xếp hạng cả web.

Một câu duy nhất cần mang theo suốt bài: phân phối dừng của một chuỗi Markov = eigenvector với eigenvalue 1 — vector duy nhất mà lan truyền thêm một bước nữa cũng không làm nó đổi. Đó là toàn bộ lý do PageRank hội tụ.

🧭 Làm theo thứ tự này

1. Làm ô ⚡ bên dưới (bài toán retry OK/LỖI, chưa cần video).
2. Đọc §1-4: ma trận Markov, phân phối dừng là eigenvector λ = 1, vì sao nó luôn tồn tại.
3. Tự tính tay §5 (đồ thị A—B—C—D, seed A, d = 1/2) trước khi xem đáp án.
4. Đọc §6-7: damping (d = 1 hỏng ở đâu), PageRank và Personalized PageRank.
5. Code: tự cài PageRank, đối chiếu với nx.pagerank. Tự viết xong mới mở code mẫu trong bài.
6. Làm 4 việc ở mục "Bài tập về nhà" cuối bài (thêm cạnh A—D, thêm cạnh A—C, quét d, tính tay v₅).
7. Tự kiểm.
8. Sau cùng: xem lại tập 14 và tập 15 (không có video mới cho bài này). Đọc thêm Taubes ch.16-18.

Xong bài khi: trả lời được "vì sao λ = 1 luôn tồn tại" và "d = 1 hỏng ở đâu". Câu 6 của phần tự kiểm là câu sâu nhất của bài.

⚡ 30 phút đầu — làm trước, đọc sau

Một request có hai trạng thái: OK và LỖI. Vòng retry chạy mãi. Câu hỏi: về lâu dài bao nhiêu phần trăm thời gian hệ thống ở trạng thái OK?

import numpy as np
M = np.array([[0.9, 0.2],
              [0.1, 0.8]])          # cột = trạng thái HIỆN TẠI
v = np.array([1.0, 0.0])            # chắc chắn đang OK
for t in range(200):
    v = M @ v
print(v)                            # đích: [0.66666667 0.33333333]
print(M @ v - v)                    # đích: [0. 0.]  ← thêm một bước cũng không đổi

Đổi v ban đầu thành [0, 1], [0.5, 0.5], [0.13, 0.87] — vẫn ra đúng (2/3, 1/3). Rồi chạy np.linalg.eigvals(M) → ra [1. 0.7].

Ba quan sát đó là cả bài 8:

1. Có một vector mà M·v = v (đó là λ = 1).
2. Xuất phát từ đâu cũng trôi về nó.
3. Con số 0.7 — eigenvalue thứ hai — quyết định trôi nhanh cỡ nào.

⚠️ Đây KHÔNG phải ma trận của bài 7 §7. Bài 7 dùng [[0.9,0.5],[0.1,0.5]] (λ = 1, 0.4, π = (5/6,1/6)); ở đây là [[0.9,0.2],[0.1,0.8]] (λ = 1, 0.7, π = (2/3,1/3)). Cố ý đổi số, để bạn làm lại từ đầu chứ không nhớ lại đáp án. Cùng một câu chuyện, hai bộ số — nếu bạn ra (5/6,1/6) ở đây thì bạn đang chép chứ không tính.

1. Ma trận Markov: mỗi CỘT tổng bằng 1

Định nghĩa: ma trận Markov (còn gọi ma trận ngẫu nhiên) là ma trận vuông, mọi phần tử ≥ 0, và mỗi cột cộng lại đúng bằng 1.

M = [ 0.9   0.2 ]        cột 1: 0.9 + 0.1 = 1  ✓
    [ 0.1   0.8 ]        cột 2: 0.2 + 0.8 = 1  ✓

Đọc ma trận này theo cột — và bài 2 đã dạy bạn phải đọc ma trận theo cột:

Cột j = "nếu đang ở trạng thái j, bước tiếp theo đi đâu, với xác suất bao nhiêu".

Cột 1 nói: đang OK → 90% ở lại OK, 10% rơi sang LỖI. Cột 2 nói: đang LỖI → 20% hồi phục về OK, 80% vẫn LỖI.

Cột phải tổng 1 vì xác suất đi đâu đó phải bằng 100% — không có request nào bốc hơi.

Hệ quả trực tiếp: nếu v là một phân phối (các phần tử ≥ 0, tổng = 1) thì M·v cũng là một phân phối. Tổng luôn được bảo toàn. Bạn sẽ thấy tổng = 1.0000000000 ở mọi bước lặp trong bài này — đó không phải trùng hợp, đó là tính chất cột.

Ẩn dụ backend: chuỗi Markov là một vòng retry chạy mãi. M là bảng xác suất chuyển trạng thái sau mỗi lần retry. v là phân bố hiện tại của toàn bộ request đang trong hệ thống. Nhân M một lần = cho cả hệ thống chạy thêm một vòng.

BẪY quy ước: nửa thế giới viết ma trận Markov theo hàng (v·M, hàng tổng 1), nửa còn lại viết theo cột (M·v, cột tổng 1). Taubes và bài này dùng cột. Khi đọc tài liệu khác, việc đầu tiên là kiểm M.sum(axis=0) hay M.sum(axis=1) bằng 1 — sai quy ước thì mọi con số sau đó đều sai, và bug này rất khó thấy vì code vẫn chạy.

2. Phân phối dừng CHÍNH LÀ eigenvector với λ = 1

Phân phối dừng π là phân phối mà chạy thêm một vòng cũng không đổi:

M · π = π

Nhìn lại định nghĩa eigenvector ở bài 7: A·v = λ·v. Đặt λ = 1 — hai phương trình là một.

Phân phối dừng không "giống" eigenvector. Nó LÀ eigenvector, ứng với eigenvalue đúng bằng 1. Không có phép ẩn dụ nào ở đây. Chỉ là cùng một phương trình viết bằng hai từ vựng khác nhau.

Kiểm bằng số, ma trận retry ở trên:

M · (2/3, 1/3) = ( 0.9·2/3 + 0.2·1/3 ,  0.1·2/3 + 0.8·1/3 )
                = ( 0.6 + 0.0667      ,  0.0667 + 0.2667   )
                = ( 2/3 , 1/3 )   ✓ đứng yên

np.linalg.eigvals(M) cho [1.0, 0.7], và eigenvector ứng với λ=1, chuẩn hoá cho tổng bằng 1, ra đúng [0.666667, 0.333333].

Tự kiểm bằng mẹo 2×2 của 3B1B tập 15 (làm được trên giấy): m = trace/2 = 1.7/2 = 0.85, p = det = 0.9·0.8 − 0.2·0.1 = 0.7 λ = m ± √(m² − p) = 0.85 ± √0.0225 = 0.85 ± 0.15 → 1.0 và 0.7 ✓

Ý nghĩa "dừng": không phải hệ thống ngừng chạy. Request vẫn liên tục nhảy OK↔LỖI. Cái đứng yên là tỉ lệ tổng thể — cứ 3 request thì 2 đang OK, mãi mãi. Giống một cache đã ấm: entry vẫn vào ra không ngừng, nhưng hit rate đứng im ở một con số.

3. Vì sao eigenvalue = 1 LUÔN tồn tại — chứng minh 3 dòng

Đây là chỗ đáng dừng lâu nhất bài. Nó là lý do PageRank không bao giờ "không tìm được đáp án".

Với ma trận thường, chẳng có gì đảm bảo λ = 1 xuất hiện. Với ma trận Markov thì luôn luôn. Chứng minh:

Bước 1. Gọi 1 = (1,1,...,1) là vector toàn số một. "Mỗi cột của M tổng bằng 1" viết lại bằng ma trận chính là:

1ᵀ · M = 1ᵀ

(phần tử thứ j của 1ᵀM đúng bằng tổng cột j.)

Bước 2. Chuyển vị hai vế: Mᵀ · 1 = 1. Vậy Mᵀ có eigenvector 1 với eigenvalue 1 — hiển nhiên, không cần tính gì.

Bước 3. M và Mᵀ có cùng đa thức đặc trưng (vì det(A) = det(Aᵀ), nên det(M − λI) = det(Mᵀ − λI)). Cùng đa thức đặc trưng → cùng tập eigenvalue. Vậy M cũng có λ = 1. ∎

Có λ = 1 nghĩa là det(M − I) = 0, nghĩa là hệ (M − I)v = 0 có nghiệm khác 0 — phân phối dừng tồn tại.

Kiểm bằng số trên ma trận Markov ngẫu nhiên (cột đã chuẩn hoá):

(các số e-17 là sai số làm tròn máy — tức bằng 0.)

Chú ý cột cuối bảng. Ba dòng đầu có |λ₂| < 1. Dòng cuối — đồ thị của bài này — có |λ₂| = 1. Đó là quả bom sẽ nổ ở §6.

Điểm thứ hai, cũng miễn phí: mọi eigenvalue của ma trận Markov đều có |λ| ≤ 1. Trực giác: M bảo toàn tổng và không cho phần tử âm, nên nó không thể phóng to vector phân phối. Nếu tồn tại |λ| > 1 thì lặp mãi sẽ cho tổng nổ ra vô cực — mâu thuẫn.

Gộp lại: λ = 1 là eigenvalue lớn nhất, và nó luôn có mặt. Đó là lý do phép lặp có đích để đi tới.

4. Khi t → ∞: vì sao lặp mãi thì trôi về phân phối dừng

Bài 7 cho công cụ: viết vector ban đầu theo cơ sở eigenvector rồi lặp.

v₀ = c₁·u₁ + c₂·u₂ + ... + cₙ·uₙ            (uᵢ là eigenvector, λᵢ là eigenvalue)

Mᵗ·v₀ = c₁·λ₁ᵗ·u₁ + c₂·λ₂ᵗ·u₂ + ... + cₙ·λₙᵗ·uₙ

Với λ₁ = 1 và mọi |λᵢ| < 1 khác:

1ᵗ = 1              → thành phần u₁ ĐỨNG YÊN
λᵢᵗ → 0             → mọi thành phần khác CHẾT DẦN

Lặp ma trận là một bộ lọc. Mỗi vòng lặp nhân thành phần thứ i với λᵢ. Thành phần λ = 1 sống sót nguyên vẹn; mọi thứ khác teo lại theo cấp số nhân. Sau đủ nhiều vòng, chỉ còn eigenvector của λ = 1 — bất kể xuất phát từ đâu.

Đó là lý do ở §0 bạn xuất phát từ (1,0), (0,1), (0.5,0.5), (0.13,0.87) đều rơi về (2/3, 1/3).

Tốc độ hội tụ = |λ₂|. Sai số giảm như |λ₂|ᵗ. Với ma trận retry, λ₂ = 0.7, xuất phát v₀ = (1,0):

v₀ − π = (1/3)·(1, −1)   ⟹   ‖v_t − π‖₁ = (2/3)·0.7ᵗ     (hằng số 2/3 tính một lần, xong)

bước 37:  (2/3)·0.7³⁷ = 1.24e-06     chưa đạt
bước 38:  (2/3)·0.7³⁸ = 8.66e-07  ✓  lần đầu < 1e-6

Số bước cần ≈ log(tol) / log(|λ₂|). Đây là Big-O của thuật toán, và nó không phụ thuộc kích thước ma trận — chỉ phụ thuộc khoảng cách giữa λ₁ và λ₂. Chi tiết đó sẽ quay lại cắn bạn ở §6.

5. Ví dụ tính tay: đồ thị A—B—C—D, seed = A, d = 1/2

Đồ thị vô hướng, 4 node xếp thành đường thẳng:

A —— B —— C —— D          deg(A)=1   deg(B)=2   deg(C)=2   deg(D)=1

Luật lan truyền (chính là công thức PageRank):

v(x) = d · Σ_{y kề x}  v(y)/deg(y)   +   (1−d) · teleport(x)

Đọc bằng lời: mỗi node chia đều điểm của mình cho các hàng xóm (v(y)/deg(y)), giữ lại tỉ lệ d; phần (1−d) còn lại được bơm mới vào seed. Ở đây d = 1/2, teleport = A.

Viết ra bốn phương trình, thay d = 1/2 và deg vào:

v(A) = ½·( v(B)/2 )                + ½        ← A chỉ kề B; A là seed nên nhận ½
v(B) = ½·( v(A)/1 + v(C)/2 )                  ← B kề A và C
v(C) = ½·( v(B)/2 + v(D)/1 )                  ← C kề B và D
v(D) = ½·( v(C)/2 )                           ← D chỉ kề C

5.1 Lặp bằng tay — số nguyên trên mẫu chung

Bắt đầu từ v₀ = (1, 0, 0, 0). Mỗi bước thay số vào bốn phương trình trên.

Bước 1: v(A) = ½·0 + ½ = ½ · v(B) = ½·1 = ½ · v(C) = 0 · v(D) = 0 Bước 2: v(A) = ½·(½/2) + ½ = ⅛ + ½ = ⅝ · v(B) = ½·½ = ¼ · v(C) = ½·(½/2) = ⅛ · v(D) = 0

Ba điều đọc được ngay từ bảng:

• Tổng luôn đúng bằng 1 ở mọi dòng (1/1, 2/2, 8/8, 32/32, 128/128...). Đây là tính chất cột ở §1, và là cách kiểm bug rẻ nhất — lệch tổng thì bạn cài sai, không cần tìm đâu xa.
• Giá trị dao động rồi thắt lại: v(A) đi 1 → 0.5 → 0.625 → 0.5625 → 0.5859 → 0.5742 → ... hai bên kẹp dần vào 0.5778. Dao động vì λ₂ âm (−0.5, xem bảng phổ ở §6).
• v(D) chỉ khác 0 từ bước 3 trở đi — đúng bằng số hop từ A tới D. Điểm phải đi bộ qua đồ thị, không teleport được.

5.2 Giải hệ ra phân số chính xác — khử từ đuôi lên

Đừng giải ma trận 4×4. Đồ thị là đường thẳng nên khử từ D ngược về A là ra ngay.

(1) v(D) = ½·(v(C)/2) = v(C)/4

(2) v(C) = ½·(v(B)/2 + v(D))          thay (1) vào:
         = v(B)/4 + v(C)/8
    ⟹  v(C) − v(C)/8 = v(B)/4
    ⟹  (7/8)·v(C) = v(B)/4
    ⟹  v(C) = (2/7)·v(B)

(3) v(B) = ½·(v(A) + v(C)/2)          thay (2) vào:
         = v(A)/2 + (1/4)·(2/7)·v(B) = v(A)/2 + v(B)/14
    ⟹  (13/14)·v(B) = v(A)/2
    ⟹  v(B) = (7/13)·v(A)

(4) v(A) = ½·(v(B)/2) + ½ = v(B)/4 + ½    thay (3) vào:
         = (1/4)·(7/13)·v(A) + ½ = (7/52)·v(A) + ½
    ⟹  (1 − 7/52)·v(A) = ½
    ⟹  (45/52)·v(A) = ½
    ⟹  v(A) = 52/90 = 26/45

Thế ngược lên:

v(B) = (7/13)·(26/45) = 14/45
v(C) = (2/7)·(14/45)  =  4/45
v(D) = (1/4)·(4/45)   =  1/45

Kiểm miễn phí: (26 + 14 + 4 + 1)/45 = 45/45 = 1 ✓ — không hề áp đặt tổng ở đâu, nó tự ra. Đó là dấu hiệu bạn giải đúng.

5.3 Đối chiếu với thư viện — bắt buộc, không được bỏ

nx.pagerank(G, alpha=0.5, personalization={'A': 1.0, 'B': 0, 'C': 0, 'D': 0},
            tol=1e-14, max_iter=10_000)

(phải siết tol — mặc định tol=1e-6 chỉ cho 6 chữ số đúng, cột dưới sẽ ra 0.5777776 chứ không phải 0.5777777778.)

Lệch tối đa 3.16e-15 — sai số float, tức khớp hoàn toàn. Khớp tới 4 chữ số thập phân: ✓

5.4 Tỉ lệ 26 : 14 : 4 : 1 — điểm tụt thế nào theo hop

Vì sao tụt nhanh vậy? Khai triển nghiệm thành chuỗi (kiểm bằng số, hội tụ đúng về (26,14,4,1)/45):

v = (1−d)·( e_A  +  d·M·e_A  +  d²·M²·e_A  +  d³·M³·e_A  + ... )

Đóng góp của các đường đi độ dài t bị nhân với dᵗ. Với d = 1/2:

Hai lớp suy giảm chồng nhau: hệ số dᵗ phạt theo độ dài đường đi, và phép chia 1/deg(y) phạt theo độ "đông hàng xóm". Node xa seed vừa cần đường dài hơn, vừa bị pha loãng nhiều lần.

Đây chính là điều làm Personalized PageRank hữu ích cho retrieval: nó tự động ưu tiên vùng lân cận của seed, và d là cái núm chỉnh "nhìn xa bao nhiêu hop". d nhỏ = bám sát seed; d lớn = lan rộng.

5.5 ⭐ Aˡ đếm đường đi — vì sao "ℓ hop" nghĩa là luỹ thừa ℓ (bổ sung từ VMLS — 2026-10)

(nguồn: VMLS tr.186-188, §10.3)

Bảng ở §5.4 có cột "đóng góp của các đường đi độ dài t", nhưng chưa nói đường đi được đếm bằng gì. Câu trả lời là luỹ thừa của ma trận kề. Gọi A là ma trận kề với Aᵢⱼ = 1 nếu có cạnh từ j tới i (cùng quy ước cột với M):

(A²)ᵢⱼ = Σₖ Aᵢₖ Aₖⱼ        mỗi số hạng = 1 đúng khi có cạnh j→k VÀ k→i: một đường đi độ dài 2 qua k

Cộng theo k là đếm hết các đường độ dài 2 từ j tới i. Quy nạp: (Aˡ⁺¹)ᵢⱼ = Σₖ Aᵢₖ(Aˡ)ₖⱼ, vì mỗi đường độ dài ℓ+1 là một đường độ dài ℓ cộng một cạnh cuối. Vậy (Aˡ)ᵢⱼ = số đường đi độ dài ℓ từ j tới i.

Tính tay trên A—B—C—D (vô hướng nên A đối xứng). Từ A, độ dài 2: A-B-A và A-B-C, nên cột A của A² là (1,0,1,0). Độ dài 3: A-B-A-B và A-B-C-B (hai đường tới B), A-B-C-D (một đường tới D), nên (0,2,0,1).

⚠️ Phạm vi (quy tắc 4): "đường đi" ở đây cho phép lặp lại nút. A-B-A được tính là một đường đi độ dài 2 từ A về A. Đó không phải đường đi đơn.

Nối với bài này.

• Chuỗi PPR là tổng các đường đi. M = A·D⁻¹: mỗi bước rời nút y nhân thêm 1/deg(y). Tính tay M²e_A = (½, 0, ½, 0): A-B-A có trọng số 1·½, A-B-C có trọng số 1·½. Nhân (1−d)d² = 0.125 ra đúng hàng t = 2 của bảng §5.4, (0.0625, 0, 0.0625, 0). Mỗi đường bị phạt dᵗ theo độ dài và 1/deg theo từng bước.
• Dao động của §6 (kiểu 1) đọc được bằng phép đếm. Đồ thị hai phía nên mọi đường độ dài lẻ từ A kết thúc ở phía bên kia: (Aˡ)[A,A] = 0 với mọi ℓ lẻ. Đường chéo của Aˡ ở ℓ = 2, 4, 6 là (1,2,2,1), (2,5,5,2), (5,13,13,5). Không cần eigenvalue −1 mới thấy chu kỳ 2; đó là hai cách đọc cùng một sự thật.
• Knowledge graph. "Hai thực thể cách nhau ℓ bước có bao nhiêu đường nối" là (Aˡ)ᵢⱼ. Mạng nơ-ron đồ thị ℓ lớp chỉ thấy hàng xóm trong ℓ bước (bài 10 §5c) vì cùng lý do.

import numpy as np
# đồ thị 5 nút của sách (VMLS hình 10.1)
A5 = np.array([[0,1,0,0,1],[1,0,1,0,0],[0,0,1,1,1],[1,0,0,0,0],[0,0,0,1,0]])
A2_sach = np.array([[1,0,1,1,0],[0,1,1,1,2],[1,0,1,2,1],[0,1,0,0,1],[1,0,0,0,0]])
assert (A5 @ A5 == A2_sach).all()           # khớp ma trận in trong sách

P = np.array([[0,1,0,0],[1,0,1,0],[0,1,0,1],[0,0,1,0]])     # A—B—C—D
M = P / P.sum(0)                            # M = P·D⁻¹, mỗi cột tổng 1
mp = np.linalg.matrix_power
assert (mp(P, 2)[:, 0] == [1, 0, 1, 0]).all() and (mp(P, 3)[:, 0] == [0, 2, 0, 1]).all()
e_A = np.array([1., 0, 0, 0])
assert np.allclose((1 - 0.5) * 0.5**2 * (mp(M, 2) @ e_A), [0.0625, 0, 0.0625, 0])   # hàng t=2 của §5.4
assert all((np.diag(mp(P, l)) == 0).all() for l in (1, 3, 5, 7))     # hai phía: số bước lẻ không về chỗ cũ
print([np.diag(mp(P, l)).tolist() for l in (2, 4, 6)])               # [[1,2,2,1], [2,5,5,2], [5,13,13,5]]

6. Damping factor: d = 1 hỏng ở đâu

Nếu bỏ teleport (d = 1), luật trở thành v ← M·v thuần tuý. Nghe sạch sẽ hơn. Nó hỏng theo hai kiểu, và cả hai đều là hỏng thật.

Kiểu 1 — DAO ĐỘNG mãi mãi (xảy ra ngay trên đồ thị của bài này)

Nhớ cột |λ₂| ở bảng §3: đồ thị A—B—C—D có |λ₂| = 1. Cụ thể:

eigenvalues của M  =  [ 1,  −1,  0.5,  −0.5 ]
                            ↑
                       thủ phạm

Theo §4, thành phần ứng với λ = −1 bị nhân (−1)ᵗ — đổi dấu mỗi bước, không bao giờ teo đi. Chạy thử với d = 1:

v0 = [1.     0.      0.      0.    ]
v1 = [0.     1.      0.      0.    ]
v2 = [0.5    0.      0.5     0.    ]
v3 = [0.     0.75    0.      0.25  ]
v4 = [0.375  0.      0.625   0.    ]
v5 = [0.     0.6875  0.      0.3125]
v6 = [0.3438 0.      0.6562  0.    ]
...
bước 1000 = [0.333333, 0,        0.666667, 0       ]
bước 1001 = [0,        0.666667, 0,        0.333333]

Toàn bộ khối lượng nhảy qua lại giữa {A,C} và {B,D} — vĩnh viễn. Sau 1000 bước vẫn dao động y như bước 4.

Nguyên nhân cấu trúc: đồ thị đường thẳng là hai phía (bipartite) — hai phía là {A, C} và {B, D}, mọi cạnh đều nối phía này sang phía kia. Đi một bước là chắc chắn đổi phía. Không có cách nào dừng lại.

Chiều ngược — để KIỂM được, không chỉ nhận ra (bổ sung từ MCS §12.8.2 tr.522–523, 2026-10). §5.5 cho chiều hai phía ⇒ diag(Aˡ) = 0 với ℓ lẻ. Chiều ngược cũng đúng: đồ thị là hai phía ⇔ không có chu trình độ dài lẻ. Chứng minh là một thuật toán: BFS tô hai màu xen kẽ; tô được hết thì hai phía, gặp một cạnh hai đầu cùng màu thì cạnh đó đóng một chu trình lẻ.

from collections import deque
def two_color(adj):                              # trả (màu, None) hoặc (None, cạnh vi phạm)
    c = [-1] * len(adj)
    for s in range(len(adj)):
        if c[s] >= 0: continue
        c[s] = 0; q = deque([s])
        while q:
            u = q.popleft()
            for v in np.flatnonzero(adj[u]):
                if c[v] < 0: c[v] = 1 - c[u]; q.append(v)
                elif c[v] == c[u]: return None, (u, v)
    return c, None
Q = P.copy(); Q[0, 2] = Q[2, 0] = 1              # thêm MỘT cạnh A—C → tam giác A-B-C
print(two_color(P), two_color(Q))                # ([0,1,0,1], None)   (None, (1, 2))

Đồ thị	tô 2 màu	eigenvalue của M	d = 1 sau 60 bước
A—B—C—D	[0,1,0,1]	[−1, −0.5, 0.5, 1]	dao động mãi
+ cạnh A—C	vi phạm ở (B, C)	[−0.7287, −0.5, 0.2287, 1]	hội tụ (0.25, 0.25, 0.375, 0.125) = bậc/2|E|

Một cạnh tạo chu trình lẻ là đủ để −1 biến mất (với đồ thị liên thông). Với memory: KG entity–entity (như đồ thị của luận văn) gần như luôn có tam giác nên không hai phía; đồ thị passage/episode–entity thuần (kiểu phần passage của HippoRAG) thì hai phía theo cấu trúc — random walk không damping trên nó dao động. two_color là một assert rẻ để biết đồ thị của bạn đang ở trường hợp nào, trước khi đọc bất kỳ con số hội tụ nào. Nối môn 11 bài 7 §5b: null model phải giữ đúng tính chất này.

(Nếu lấy trung bình hai bước liên tiếp thì được (1/6, 1/3, 1/3, 1/6) — nhưng đó là bạn tự tay vá, không phải thuật toán hội tụ.)

Kiểu 2 — SPIDER TRAP: một node hút hết điểm

Đồ thị có hướng: A → B, B → C, C → C (C tự trỏ vào mình, không có đường ra).

v0 = [0.333333, 0.333333, 0.333333]
v1 = [0,        0.333333, 0.666667]
v2 = [0, 0, 1]        ← xong. A và B = 0 vĩnh viễn
v3 = [0, 0, 1]

C là cái hố. Điểm vào được, không ra được. Với d → 1, networkx cho {A: 0.0, B: 1e-06, C: 0.999999} — cả đồ thị chỉ còn một node có điểm, xếp hạng vô nghĩa. Đây đúng là mánh spam mà Google phải chống: dựng một cụm trang chỉ trỏ lẫn nhau, không trỏ ra ngoài, để giam PageRank lại.

Bật damping d = 0.85 lên: {A: 0.05, B: 0.0925, C: 0.8575}. C vẫn cao nhất — đúng, nó thực sự được trỏ nhiều — nhưng A và B không còn bị xoá sổ.

Damping vá cả hai lỗ bằng một hằng số

Ma trận thực sự đang được lặp không phải M mà là ma trận Google:

G = d·M + (1−d)·teleport·1ᵀ

Với teleport đều, số hạng thứ hai làm mọi phần tử của G dương thật sự — không còn hố, không còn hai phía tách bạch, và Perron–Frobenius đảm bảo hội tụ.

Nhưng ví dụ của bài dùng teleport dồn vào A, nên G vẫn còn đầy số 0 — nhìn ma trận dưới đây. Nó vẫn hội tụ. Vì sao? Lý do thật không phải tính dương, mà là điều ở bảng ngay sau. Với d = 0.5, seed A:

G = [ 0.5   0.75  0.5   0.5  ]        cột tổng = [1. 1. 1. 1.]  ✓ vẫn Markov
    [ 0.5   0     0.25  0    ]
    [ 0     0.25  0     0.5  ]
    [ 0     0     0.25  0    ]

Và eigenvalue đổi hẳn:

Quan hệ không phải ngẫu nhiên — kiểm bằng số thì khớp tập hợp chính xác:

spec(G) = {1} ∪ { d·λ : λ ∈ spec(M), λ ≠ 1 }

d·{−1, 0.5, −0.5} = {−0.5, 0.25, −0.25}   ✓ đúng bằng ba eigenvalue còn lại của G

Đã kiểm với d = 0.5 và d = 0.85, teleport đều / dồn seed / ngẫu nhiên — khớp trong cả 6 trường hợp. Định lý này không quan tâm teleport là vector nào, miễn nó là một phân phối. Đó là lý do Personalized PageRank hội tụ nhanh y hệt PageRank thường: đổi teleport không đụng gì tới |λ₂|.

Đây là toàn bộ vai trò của damping factor, gói trong một dòng: nó bóp mọi eigenvalue phụ xuống d lần — |λ₂| từ 1 tụt xuống d < 1 — và đó là thứ ép hội tụ. d không phải "tham số cho đẹp" — nó là thứ trực tiếp mua lấy sự hội tụ, và giá phải trả là tốc độ.

Chú ý thứ tự nhân quả: λ = 1 luôn tồn tại (§3, miễn phí, nhờ cột tổng 1). Cái d mua không phải sự tồn tại của đích, mà là việc lặp có tới được đích hay không.

Cái giá: d càng lớn, chạy càng lâu

Vì |λ₂| = d, sai số giảm đúng d lần mỗi bước. Đo trên đồ thị của bài:

 t |  ‖v_t − v_∞‖₁  |  tỉ lệ với bước trước
 1 |   3.778e-01    |    —
 2 |   1.667e-01    |  0.4412
 3 |   8.333e-02    |  0.5000
 4 |   4.167e-02    |  0.5000
 5 |   2.083e-02    |  0.5000
10 |   6.510e-04    |  0.5000
20 |   6.358e-07    |  0.5000
25 |   1.987e-08    |  0.5000

Từ bước 3 trở đi, đúng 0.5000 mỗi bước — không phải xấp xỉ, đó là |λ₂| = d.

Số bước để ‖Δv‖₁ < tol:

d = 0.99 tốn gấp 69 lần d = 0.5 cho cùng độ chính xác. Đây là đánh đổi kinh điển kiểu backend: nới timeout thì kết quả "đúng" hơn nhưng p99 latency nổ. Google chọn d = 0.85 — đủ xa 1 để hội tụ nhanh, đủ gần 1 để cấu trúc link vẫn chi phối kết quả.

BỎ QUA được: việc chứng minh chặt chẽ định lý Perron–Frobenius (rằng ma trận dương thực sự có λ₁ = 1 duy nhất và |λᵢ| < 1 với mọi i ≥ 2). Bạn cần biết kết luận và biết nó đến từ tính dương của G. Chứng minh đầy đủ là việc của môn giải tích ma trận, không trả cổ tức gì cho bạn lúc này.

7. PageRank và Personalized PageRank — khác đúng một vector

Cả hai chạy cùng một vòng lặp, cùng một d. Khác duy nhất ở vector teleport:

Chạy trên cùng đồ thị A—B—C—D:

PageRank (teleport đều):

Kết quả đối xứng — hợp lý, đồ thị đối xứng và teleport không thiên vị ai. Và khi d → 1, nó tiến về đúng deg(x)/(2·|E|) = (1, 2, 2, 1)/6: PageRank của đồ thị vô hướng với d → 1 chỉ còn là bậc của node. Một kết quả đáng nhớ — nó nói rằng thông tin thú vị của PageRank nằm ở chỗ d chưa bằng 1.

Personalized PageRank, d = 0.5, đổi seed:

Bốn seed, bốn bảng xếp hạng hoàn toàn khác nhau, cùng một đồ thị. Hàng D là gương lật của hàng A — đúng như đối xứng của đồ thị đòi hỏi. Đó là kiểm tra sanity miễn phí thứ hai.

Ẩn dụ backend: PageRank là ORDER BY popularity — tính một lần, cache toàn cục, ai vào cũng thấy như nhau. Personalized PageRank là ORDER BY relevance_to(:seed) — kết quả phụ thuộc tham số truy vấn, nên không cache toàn cục được. Đó chính là lý do PPR đắt hơn hẳn PageRank khi triển khai thật, và là lý do có cả một dòng nghiên cứu về xấp xỉ PPR nhanh.

7.1. Ba bài báo gốc — biết để trích, không chỉ để dùng

Bạn có thể cài PPR mà không đọc bài nào. Nhưng viết một trang Related Work mà ghi "PPR" trơn, không trích nguồn, thì phản biện sẽ hỏi ngay — và đây là ba nguồn đúng, đã kiểm tận bản gốc:

Chi tiết đáng nhớ nhất, và là bài học đọc paper: bài 1998 không chứa công thức PPR. Nó nhắc ý tưởng trong một đoạn rồi trỏ sang một tài liệu khác mà chính nó liệt kê là "Manuscript in Progress" — Page, Brin, Motwani & Winograd, "The PageRank Citation Ranking: Bringing Order to the Web" (Stanford InfoLab tech report). Nghĩa là trích Brin & Page 1998 cho công thức PPR là trích sai nguồn — lỗi rất phổ biến vì ai cũng trích bài nổi tiếng nhất.

Tự kiểm bằng chính bản gốc, không tin bảng trên:

pdftotext google.pdf - | grep -i -B4 -A4 "personaliz"

Vì sao mục này đứng ở môn 2 chứ không phải môn 11: vì đây là chỗ bạn vừa mới tự tay tính ra (26, 14, 4, 1)/45. Trích dẫn dính vào trí nhớ khi nó gắn với một con số bạn đã tự làm ra, chứ không phải khi nó nằm trong một danh mục tài liệu tham khảo đọc rời.

Code — tự cài, KHÔNG dùng hàm có sẵn

Chạy được ngay. Mọi assert phải pass.

import numpy as np
import networkx as nx

NODES = ["A", "B", "C", "D"]
EDGES = [("A", "B"), ("B", "C"), ("C", "D")]
DAMPING = 0.5
TOL = 1e-12
MAX_ITER = 10_000


def ma_tran_chuyen(nodes, edges):
    """M[i][j] = 1/deg(j) nếu có cạnh j—i. Mỗi CỘT tổng bằng 1."""
    n = len(nodes)
    idx = {x: i for i, x in enumerate(nodes)}
    ke = {x: [] for x in nodes}
    for u, w in edges:                  # VÔ HƯỚNG → thêm cả hai chiều
        ke[u].append(w)
        ke[w].append(u)
    M = np.zeros((n, n))
    for y in nodes:
        bac = len(ke[y])
        if bac == 0:
            raise ValueError(f"node {y} không có cạnh nào (dangling)")
        for x in ke[y]:
            M[idx[x], idx[y]] += 1.0 / bac
    assert np.allclose(M.sum(axis=0), 1.0), "cột không tổng bằng 1"
    return M


def pagerank_lap(M, teleport, d=DAMPING, tol=TOL, max_iter=MAX_ITER):
    """Lặp  v ← d·M·v + (1−d)·teleport  cho tới khi đứng yên."""
    v = teleport.copy()
    for buoc in range(1, max_iter + 1):
        v_moi = d * (M @ v) + (1.0 - d) * teleport
        if np.abs(v_moi - v).sum() < tol:
            return v_moi, buoc
        v = v_moi
    raise RuntimeError(f"không hội tụ sau {max_iter} bước")


M = ma_tran_chuyen(NODES, EDGES)
teleport = np.array([1.0, 0.0, 0.0, 0.0])          # seed = A
v, buoc = pagerank_lap(M, teleport)

print("M =\n", M)
print(f"hội tụ sau {buoc} bước")
for x, s in zip(NODES, v):
    print(f"  {x}: {s:.6f}")
print("tổng =", v.sum())

# (1) ĐÚNG phân phối dừng: thêm một bước lan truyền KHÔNG làm nó đổi
G_google = DAMPING * M + (1 - DAMPING) * np.outer(teleport, np.ones(len(NODES)))
assert np.allclose(G_google.sum(axis=0), 1.0)
assert np.abs(G_google @ v - v).max() < 1e-9
print("G@v = v  → v là eigenvector, eigenvalue = 1  OK")

# (2) để numpy tự tìm eigenvector: phải ra đúng vector đó
w, V = np.linalg.eig(G_google)
k = int(np.argmin(np.abs(w - 1.0)))
v_eig = np.real(V[:, k]); v_eig = v_eig / v_eig.sum()
assert abs(w[k].real - 1.0) < 1e-9, "không có eigenvalue = 1"
assert np.allclose(v_eig, v, atol=1e-9)
print("khớp np.linalg.eig  OK   |λ| =", np.round(np.sort(np.abs(w))[::-1], 6))

# (3) giải thẳng hệ (I − d·M)·v = (1−d)·teleport
v_solve = np.linalg.solve(np.eye(len(NODES)) - DAMPING * M, (1 - DAMPING) * teleport)
assert np.allclose(v_solve, v, atol=1e-9)
print("khớp np.linalg.solve  OK")

# (4) đối chiếu networkx — trọng tài cuối cùng
Gnx = nx.Graph(); Gnx.add_nodes_from(NODES); Gnx.add_edges_from(EDGES)
pr = nx.pagerank(Gnx, alpha=DAMPING,
                 personalization={x: (1.0 if x == "A" else 0.0) for x in NODES},
                 tol=1e-13, max_iter=10_000)
assert np.allclose([pr[x] for x in NODES], v, atol=1e-9)
print("khớp networkx  OK  →", {x: round(pr[x], 4) for x in NODES})

# (5) đúng số phân số 26/14/4/1 trên 45
assert np.allclose(v * 45, [26, 14, 4, 1], atol=1e-8)
print("v × 45 =", np.round(v * 45, 6), " → tỉ lệ 26:14:4:1  OK")

Output phải ra:

hội tụ sau 41 bước
  A: 0.577778     B: 0.311111     C: 0.088889     D: 0.022222
tổng = 1.0
G@v = v  → v là eigenvector, eigenvalue = 1  OK
khớp np.linalg.eig  OK   |λ| = [1.   0.5  0.25 0.25]
khớp np.linalg.solve  OK
khớp networkx  OK  → {'A': 0.5778, 'B': 0.3111, 'C': 0.0889, 'D': 0.0222}
v × 45 = [26. 14.  4.  1.]  → tỉ lệ 26:14:4:1  OK

Ba đường tính hoàn toàn khác nhau ra cùng một vector — lặp (1), phân tích eigen (2), giải hệ tuyến tính (3) — rồi networkx (4) làm trọng tài. Đó không phải dư thừa: nó chứng minh bằng code rằng ba phát biểu M·π = π, "eigenvector của λ = 1", và "nghiệm hệ (I − dM)v = (1−d)·teleport" là cùng một thứ viết bằng ba thứ tiếng.

BẪY khi tự cài — ba lỗi này chiếm gần hết số bug thực tế:

1. Nhầm hàng/cột. M[i][j] phải là "từ j sang i". Cài ngược thì code vẫn chạy, vẫn hội tụ, ra số sai. Bắt bằng assert M.sum(axis=0) == 1.
2. Quên cạnh ngược với đồ thị vô hướng. Một dòng ke[w].append(u) bị thiếu là đồ thị thành có hướng, và D sẽ thành dangling node.
3. Dangling node (node không có cạnh ra) làm cột toàn 0 → tổng không còn bằng 1 → khối lượng rò rỉ dần về 0. Code trên raise thẳng; thư viện thật thì phân phối lại khối lượng đó theo teleport.

Bài tự cài thứ hai — chạy pagerank_lap với d = 0.5, seed = node đầu tiên, trên nx.gnp_random_graph(200, 0.05, seed=42) (liên thông, 942 cạnh) rồi đối chiếu networkx. Đã kiểm: hội tụ sau 24 bước, lệch tối đa 4.6e-15 — trong khi đồ thị 4 node ở trên cần 41 bước. Số node tăng 50 lần mà số bước còn giảm: vì |λ₂(G)| = d·|λ₂(M)| ≤ d, số bước bị chặn trên bởi d chứ không phụ thuộc n. Ở đây |λ₂(M)| = 0.602 nên |λ₂(G)| = 0.301 — nhanh hơn cả đồ thị đường thẳng, vốn là trường hợp xấu nhất (|λ₂(M)| = 1 ⟹ |λ₂(G)| = d = 0.5). Đó chính là lý do PageRank chạy được trên cả web.

Bài tự cài thứ ba — ma trận THƯA, cầu bắt sang dữ liệu luận văn (bổ sung 2026-08-24). Hai bài trên dùng np.zeros((n, n)) — với KG 50.000 node, riêng ma trận đó là 50 000² × 8 byte = 20 GB (18.6 GiB): không cấp phát nổi. Nhưng câu O(số cạnh) ở bảng dưới có nghĩa đen: đồ thị thật gần như toàn số 0, chỉ cần lưu cạnh:

import numpy as np, networkx as nx
from scipy.sparse import diags

d  = 0.5
Gr = nx.gnp_random_graph(50_000, 4/50_000, seed=2)   # đồ thị thưa: 50.000 node
# muốn kiểm khớp bản dày đặc: đổi dòng trên thành nx.gnp_random_graph(200, 0.05, seed=42)
n  = Gr.number_of_nodes()
v  = np.zeros(n); v[0] = 1.0                          # teleport dồn hết vào node đầu
A  = nx.to_scipy_sparse_array(Gr, format='csr', dtype=np.float64)
deg = np.asarray(A.sum(1)).ravel(); deg[deg == 0] = 1
M  = (diags(1/deg) @ A).T.tocsr()          # cột-stochastic, vẫn là công thức cũ
p  = v.copy()
for _ in range(100): p = d*(M @ p) + (1-d)*v   # KHÔNG đổi một ký tự nào của vòng lặp

Đã kiểm: (1) trên đồ thị 200 node, bản thưa khớp bản dày đặc tới max|Δp| = 3.5e-18 — cùng một phép toán, chỉ khác cách lưu; (2) trên nx.gnp_random_graph(50_000, 4/n, seed=2): nnz = 200 338 phần tử khác 0 (networkx 3.6.1) = 0.008% của n², và 100 vòng lặp chạy hết 0.03 giây trên máy thường. 20 GB so với 0.03 giây — đó là khoảng cách giữa "đã đọc câu O(số cạnh)" và "đã cài nó". Capstone PPR của môn này chỉ đạt chuẩn dùng được cho luận văn khi qua bước này.

Nối vào AI

Cần trích dẫn PPR (không chỉ cài nó)? → §7.1. Cần đối chứng cho một tuyên bố về cấu trúc đồ thị? → môn 11 bài 7.

Điểm nối liên bài đáng nhớ nhất: một hàng của ma trận attention sau softmax cũng tổng bằng 1. Nghĩa là mỗi bước attention cũng là một bước lan truyền kiểu Markov trên đồ thị đầy đủ các token, với trọng số cạnh do QKᵀ (tích vô hướng — bài 1) sinh ra. Xếp L lớp transformer chính là lặp phép lan truyền đó L lần. Cấu trúc toán học bạn vừa học không chỉ là chuyện của Google năm 1998.

Tự kiểm — trả lời được mới sang bài 9

1. Vì sao ma trận Markov luôn có eigenvalue bằng 1? Trình bày lại chứng minh 3 dòng ở §3, và nói rõ bước nào dùng tới det(A) = det(Aᵀ).
2. "Phân phối dừng" và "eigenvector với λ = 1" — nêu một lý do vì sao chúng không chỉ liên quan mà là cùng một vật.
3. Vì sao xuất phát từ bất kỳ phân phối nào cũng trôi về cùng một π? Câu trả lời phải nhắc tới λ₂ và tới việc λᵢᵗ → 0.
4. d = 1 hỏng theo hai kiểu khác nhau. Kể tên cả hai, và nói eigenvalue nào là thủ phạm của kiểu nào.
5. Đồ thị A—B—C—D là hai phía (bipartite). Điều đó ép M phải có eigenvalue nào, và vì sao? (Gợi ý: đi một bước là chắc chắn đổi phía.) Muốn phá tính hai phía đó, phải thêm cạnh loại nào — và điều kiện về độ dài chu trình mới tạo ra là gì?
6. Damping làm gì với phổ eigenvalue của ma trận? Từ đó suy ra vì sao d = 0.99 chậm hơn d = 0.5 khoảng 69 lần, mà không cần chạy code.
7. Với d → 1 và teleport đều, PageRank trên đồ thị vô hướng rút gọn thành deg(x)/(2|E|). Vậy toàn bộ giá trị của PageRank nằm ở khoảng d nào? Điều đó nói gì về việc chọn d?
8. Vì sao Google dùng power iteration chứ không gọi np.linalg.eig, dù cả hai đều tìm cùng một eigenvector? So sánh độ phức tạp và giải thích vì sao số bước lặp không phụ thuộc số node.

Câu 6 là câu sâu nhất — nó là chỗ duy nhất trong bài mà một tham số kỹ thuật (d), một tính chất phổ (|λ₂| = d) và một chi phí vận hành (số bước lặp) hợp nhất thành một phát biểu. Trả lời được câu 6 nghĩa là bạn đã hiểu vì sao damping tồn tại, chứ không phải nhớ rằng nó tồn tại.

Câu 5 là câu dễ bị bỏ qua nhất nhưng đắt thứ hai — nó nối một tính chất tổ hợp của đồ thị (bipartite) sang một con số trong phổ (λ = −1). Đó là kiểu suy luận sẽ dùng lại suốt phần graph của ML.

Bài tập về nhà trước bài 9

3Blue1Brown — Essence of Linear Algebra:

Bốn việc phải LÀM (không phải đọc):

1. Thêm cạnh A—D (đồ thị thành vòng tròn 4 node). Chạy lại pagerank_lap, seed A, d = 0.5. Đích: (7, 2, 1, 2)/12 = (0.583333, 0.166667, 0.083333, 0.166667). Rồi câu hỏi thật: đồ thị này còn hai phía nữa không? Kiểm np.linalg.eigvals(M) — bạn sẽ thấy [1, 0, 0, −1], tức λ = −1 vẫn còn, d = 1 vẫn dao động. Vì sao thêm cạnh mà không phá được? Trả lời được câu này là bạn đã hiểu bipartite thật sự là gì.

2. Thêm cạnh A—C thay vì A—D. Bây giờ eigvals(M) = [1, 0.228714, −0.5, −0.728714] — λ = −1 biến mất, |λ₂| tụt từ 1.0 xuống 0.728714. Đối chiếu với việc 1 ở trên: khác biệt giữa cạnh A—D và cạnh A—C là gì, xét theo độ dài chu trình mà mỗi cạnh vừa tạo ra?

3. Quét d từ 0.1 đến 0.95, vẽ v(D) theo d (seed A, đồ thị đường thẳng gốc). Vài mốc để đối chiếu:

   d	0.1	0.3	0.5	0.7	0.85	0.95
   v(A)	0.904534	0.733819	0.577778	0.423999	0.302224	0.213986
   v(D)	0.000228	0.005312	0.022222	0.057483	0.101284	0.141947

   (tổng luôn bằng 1, nên v(D) đọc thẳng ra phần trăm tổng điểm.)

   Bạn vừa vẽ ra đường cong "tầm nhìn xa" của thuật toán: d = 0.1 thì node cách 3 hop gần như vô hình (0.02% tổng điểm); d = 0.95 thì nó đã chiếm 14%. Đây là cách chọn d khi triển khai thật — không phải chép 0.85 từ paper.

4. Tính tay v₅ từ v₄ = (75, 38, 13, 2)/128 bằng bốn phương trình ở §5. Đích: (294, 163, 42, 13)/512. Không dùng máy tính, chỉ dùng phân số.

Đọc thêm (nguồn giấy): Taubes — chương 16 Eigenvalues, chương 17 Markov matrices, chương 18 behavior as t → ∞. Chương 17 và 18 là đúng §1-§4 của bài này, viết chặt chẽ hơn.

Bài 9 sẽ là: SVD — phân tích giá trị kỳ dị. Bài 8 tìm eigenvector, nhưng eigenvector chỉ tồn tại cho ma trận vuông. Ma trận embedding 100000 × 768 thì sao? Không vuông → không có eigenvector → toàn bộ công cụ của bài 7-8 vô dụng. SVD là câu trả lời: nó thay eigenvalue bằng giá trị kỳ dị, dùng được cho mọi ma trận, và cho biết nên vứt bỏ chiều nào khi nén. Đó là nền toán trực tiếp của xấp xỉ hạng thấp và của LoRA.