Giới thiệu sơ về thuật toán PageRank 1998

Giới thiệu về PageRank

Giới thiệu sơ về thuật toán PageRank 1998

Về lịch sử hay các chi tiết khác về thuật toán này có thể xem rõ hơn tại Wikipedia about PageRank Google 1998
Mình sẽ đi thẳng vào việc giải thích PageRank là gì và thuật toán tính cụ thể:
PageRank xuất hiện nhằm trả lời cho câu hỏi: "Xác suất để một người truy cập một trang web cụ thể nào đó là bao nhiêu?".
Nói về cách thức truy cập một trang web, ví dụ như tôi muốn đi tới trang uit.edu.vn thì có hai cách:

1. Đi từ một liên kết nào đó dẫn tới uit.edu.vn, ví dụ như trên kết quả tìm kiếm uit edu của google có liên kết dẫn tới.
2. Gõ trực tiếp vào thanh địa chỉ và tới uit.edu.vn

Trước khi đi tiếp, thì chúng ta thống nhất sẽ lấy trang uit.edu.vn làm ví dụ, và đi đến việc tính PageRank cho nó.
Bây giờ thế này, giả sử trong thế giới web của chúng ta có N trang web, và uit.edu.vn là một trong số đó, như vậy xác suất để một người tới trang uit.edu.vn chỉ là 1/N (đồng đều với các trang web khác nhau, đây là trước khi tính PageRank, và khi ta tính PageRank thì xác suất này sẽ khác đi đấy).
Nói về cách 1 ở trên, một người ở trang web khác và nhấn vào liên kết dẫn tới uit.edu.vn, xác suất này phải là tổng cộng mọi trường hợp mà người đó đang ở trang web khác và nhấn vào liên kết dẫn tới tới uit.edu.vn, đơn cử như:
[xác suất đứng tại trang hcmussh.edu.vn và nhấn vào liên kết dẫn tới uit.edu.vn] + [xác suất đứng tại trang hcmus.edu.vn và nhấn vào liên kết dẫn tới uit.edu.vn] + [xác suất đứng tại trang ktx.vnuhcm.edu.vn và nhấn vào liên kết dẫn tới uit.edu.vn] + ...

Giờ thì, ta gọi p(i) là xác suất người lướt web đứng tại trang i, L(i) là xác suất người đó nhấn vào một liên kết ở chính trang i đó và dẫn tới uit.edu.vn. Như vậy xác suất để một người ở trang i và nhấn vào liên kết trong đó dẫn tới uit.edu.vn đơn giản là phép nhân: p(i)*L(i). Với qui ước mới này, biểu thức trên được diễn đạt lại như sau:
p(hcmussh.edu.vn).L(hcmussh.edu.vn) + p(hcmus.edu.vn).L(hcmus.edu.vn) + p(ktx.vnuhcm.edu.vn).L(ktx.vnuhcm.edu.vn) + ...
Dĩ nhiên cũng có một số trang có L(i) = 0, vì trang đó không có liên kết nào dẫn tới uit.edu.vn. Các bạn nhớ nhé chúng ta đang lấy uit.edu.vn làm ví dụ điển hình, và cách tôi gọi L(i) xin hãy chú ý dùm cho để tránh nhầm lẫn. 
Như vậy nếu có N trang web trong thế giới web của chúng ta, và chúng ta biết có k trang web có liên kết dẫn tới uit.edu.vn, biểu thức trên sẽ gọn hơn là:
p(1).L(1) + p(2).L(2) + p(3).L(3) + ... + p(k).L(k)
(đặt nhãn các trang web từ 1 đến k cho gọn)
Gọi tổng trên là I, I = p(1).L(1) + p(2).L(2) + p(3).L(3) + ... + p(k).L(k)

Gọi D là xác suất truy cập uit.edu.vn trực tiếp bằng cách gõ vào thanh địa chỉ: D = 1/N,
gọi d là xác suất một người lướt web đang đứng ở một trang web và quyết định đi theo một liên kết nào đó trên trang web đó, vậy xác suất để người đó không đi theo các liên kết hiện có mà bắt đầu lại từ đầu (New Tab,...) và gõ địa chỉ trực tiếp là (1-d). (Tổng xác suất lại = 1 mà)
Vậy xác suất để một người đi tới trang uit.edu.vn sẽ là:
(xác suất người đó quyết định không đi theo các liên kết hiện có mà gõ truy cập trực tiếp uit.edu.vn) + (xác suất nhấn vào liên kết dẫn tới uit.edu.vn từ một trang web nào khác)
Tổng quát hơn, sẽ là:
(1-d).D + dI
Triển khai D và I ra, ta được:
(1-d).(1/N) + d[p(1).L(1) + p(2).L(2) + p(3).L(3) + ... + p(k).L(k)]

Giờ đây, L(i) là xác suất  người đó nhấn vào một liên kết ở chính trang i đó và dẫn tới uit.edu.vn, và được tính là (1/tổng số liên kết của trang i đó). Và p(i) là xác suất người đó đứng tại trang i, và đây chính là PageRank của chúng ta, xác suất này chính là độ nổi trội của trang web đó so với các trang web khác. Thử triển khai nữa nhé:
(1-d).(1/N) + d[PageRank(1).(1/tổng số liên kết của trang 1) + PageRank(2).(1/tổng số liên kết của trang 2) + PageRank(3).(1/tổng số liên kết của trang 3) + ... + PageRank(k).(1/tổng số liên kết của trang k)]

Ái chà chà, tôi quên nói một điều dễ nhận ra nhất của PageRank thực chất chính là việc phân tích các liên kết, có thể cho rằng một trang web có PageRank cao khi nó có nhiều link từ các trang web khác dẫn tới nó (đừng cho là tôi sai nhé, hãy tưởng tượng về mối quan hệ, tôi quen anh bí thư khóa trên A, tôi lại quen bí thư lớp tôi N, anh N lại quen anh A, tôi lại quen bạn gái anh A, tôi quen một vài người X, Y, Z ở các khoa khác, trong đó X và Y cũng quen anh A, ồ vậy anh A nổi tiếng nhỉ, đó đó là PageRank nôm na đó, chú ý các trang khác có dẫn tới uit.edu.vn PageRank cũng phải tương đối được được thì gộp vào tính PageRank của uit.edu.vn mới cao)
Cái PageRank ở trên không phải là PageRank hiện tại, mà là PageRank có được từ lần duyệt trước đó (khi ta khai phá một trang web, ta sẽ duyệt lần lượt các liên kết của nó một cách tuần tự và cập nhật PageRank ở mỗi lần), ta đang đi tìm PageRank hiện tại mà:
(1-d).(1/N) + d[PriorPageRank(1).(1/tổng số liên kết của trang 1) + PriorPageRank(2).(1/tổng số liên kết của trang 2) + PriorPageRank(3).(1/tổng số liên kết của trang 3) + ... + PriorPageRank(k).(1/tổng số liên kết của trang k)]

Prior: trước

Xin hết.!.
Bài viết tham khảo:
PageRank Clarified(?)