PageRank

Pagerank là thuật toán phân tích các liên kết được dùng trong Google Search để xếp hạng các trang web.

• Thuật toán này chỉ định giá trị nhất định cho mỗi thành phần của một tập hợp các văn bản liên kết với nhau, ví dụ như World Wide Web.
• Mục đích "đo" tầm quan trọng tương đối của các liên kết trong tập hợp đó.
• Áp dụng cho bất kỳ tập hợp văn bản nào có trích dẫn đối ứng và liên kết cụ thể.
• giá trị (weight) mà nó gán cho bất kỳ thành phần E được gọi là PageRank của E và ký hiệu là $PR(E).$

Thuật toán toán học PageRanks đối với một hệ thống liên kết đơn giản, sẽ được hiển thị tỷ lệ bằng %. Trang C có một PageRank cao hơn so với trang E, mặc dù có ít liên kết (links) đến trang C; một link duy nhất dẫn tới C từ một trang quan trọng và chính vì thế mà C có giá trị cao. Nếu như một người lướt web bắt đầu từ một trang bất kỳ thì có 85% xác suất chọn một link ngẫu nhiên trên trang mà họ đang xem, và 15% họ sẽ chọn chuyển sang một trang web bất kỳ từ toàn bộ hệ thống các liên kết. Người dùng sẽ truy cập vào trang E với xác suất 8.1%. (Xác suất 15% truy cập tới một trang bất kỳ tương ứng với yếu tố damping là 85%.) Nếu không có yếu tố damping, người dùng cuối cùng cũng sẽ kết thúc quá trình lướt web tại trang A, B, hoặc C, và các trang khác sẽ có PageRank bằng 0. Nếu như tính cả yếu tố damping, trang A vẫn liến kết đến tất cả các trang trong hệ thống, mặc dù chỉ có 1 link trỏ đi.

Mô tả

Giá trị Pagerank hình thành từ thuật toán toán học dựa trên webgraph: các trang world wide web được coi như các đỉnh và các đường link là các cạnh. Khi hình thành webgraph người ta có tính đến những trang của các cơ quan có thẩm quyền như cnn.com hay usa.gov. Giá trị xếp hạng cho thấy tầm quan trọng của từng trang cụ thể. Mỗi đường link tới trang web sẽ được tính như 1 sự hỗ trợ làm tăng thêm giá trị Pagerank. Giá trị Pagerank của trang được định nghĩa đệ quy và phụ thuộc vào số lượng và giá trị của các trang mà có link dẫn đến trang đó (incoming links). Một trang web có chứa nhiều link liên kết từ các trang web có giá trị PageRank cao thì giá trị PageRank của trang đó cũng sẽ cao. Có rất nhiều bài viết đã được xuất bản ra công chúng dựa trên nghiên cứu gốc của Page và Brin. Trên thực tế khái niệm PageRank rất khó để thao tác. Đã có nhiều nghiên cứu tiến hành xác định những ảnh hưởng sai tới PageRank ranking. Mục đích là tìm một cách loại bỏ hiệu quả những link từ các văn bản với những ảnh hưởng sai tới PageRank.

Thuật toán

Pagerank là phân bố xác suất, được sử dụng để thể hiện khả năng khi một người click chuột ngẫu nhiên vào đường link và sẽ tới được trang web cụ thể. Pagerank có thể được tính cho các tập văn bản với tài liệu có độ dài bất kỳ. Khi bắt đầu tính toán thì sự phân bổ đó được chia đều cho tất cả những văn bản trong tập văn bản. Các tính toán Pagerank cần một số lần "lặp đi lặp lại" qua các văn bản trong tập để có thể đạt được giá trị thực tế một cách thiết thực hơn. Xác suất có giá trị từ 0 đến 1. Với giá trị 0.5, thường được hiểu là "50% cơ hội" của một việc gì đó có thê xảy ra. Trong Pagerank, 0.5 có nghĩa là 50% cơ hội một người nào đó click vào một link ngẫu nhiên để được chuyển đến văn bản đó (giá trị pagerank = 0.5)

Thuật toán được đơn giản hóa

Giả sử một nhóm gồm 4 trang web: A, B, C, D. những liên kết từ một trang đến chính nó không được tính, mỗi trang web có 1 đường dẫn duy nhất đến 1 trang web khác. Giá trị Pagerank của các trang ban đầu được cho là bằng nhau. Tổng giá trị Pagerank trên tất cả các trang là tổng số trang web tại thời điểm đó, do đó mỗi trang trong ví dụ này sẽ có một pagerank ban đầu tương đương với 1. Tuy nhiên trong phần còn lại và các ví dụ của bài này sẽ có giá trị tương đối từ 0 đến 1. Do đó giá trị ban đầu cho mỗi trang là 0.25. Pagerank chuyển từ một trang đến các trang khác bằng các đường link, trong những bước tính tiếp theo giá trị sẽ được chia đều cho tất cả các liên kết đi. Nếu các liên kết duy nhất trong hệ thống từ các trang B, C và D tới A, mỗi liên kết sẽ chuyển giá trị bằng 0.25 Pagerank A khi tính trong lần tiếp theo, tổng cộng là 0,75.

$PR(A)=PR(B)+PR(C)+PR(D).\,$

Khác với ví dụ trên, B có liên kết đến trang C và A, trong khi D có các link đến cả ba trang. Như vậy trong bước tiếp theo, trang B sẽ chuyển tải một nửa giá trị của mình, tương đương với 0.125 tới trang A và 0.125 tới trang C. Khi trang D có 3 liên kết trỏ đi, có nghĩa nó sẽ chuyển 1/3 giá trị của mình, tương đương với 0.083 tới A.

$PR(A)={\frac {PR(B)}{2}}+{\frac {PR(C)}{1}}+{\frac {PR(D)}{3}}.\,$

PageRank được tính cho 1 outbound link sẽ bằng số score pagerank của document đó chia cho số outbound link L()

$PR(A)={\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}.\,$

Công thức chung, giá trị Pagerank đối với bất kỳ trang u có thể tính như sau:

$PR(u)=\sum _{v\in B_{u}}{\frac {PR(v)}{L(v)}}$,

Giá trị PageRank đối với trang u phụ thuộc vào giá trị Pagerank của từng trang v có chứa trong set B_u (tập hợp có chứa các trang có link đến trang u), chia cho số L (v) các link từ trang v.

Yếu tố damping

Lý thuyết PageRank cho rằng, ngay cả một người dùng giả thiết click ngẫu nhiên vào các trang web cuối cùng cũng sẽ dừng lại. Xác suất người dùng tiếp tục click trong bất cứ bước nào được gọi là yếu tố damping. Có nhiều nghiên cứu đã thử các giá trị yếu tố damping, giá trị ước lượng bằng 0.85 là người dùng sẽ tiếp tục lướt web. Công thức tính Pagerank có tính đến yếu tố damping sử dụng mô hình khi người dùng bất kỳ sẽ cảm thấy chán sau một vài lần click và chuyển đến vài trang web khác một cách ngẫu nhiên. Như vậy:

$PR(A)={1-d \over N}+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right).$

Công thức trên sử dụng mô hình khi người dùng ngẫu nhiên cảm thấy chán sau khi click và được chuyển đến một số trang ngẫu nhiên. Giá trị Pagerank thể hiện những cơ hội mà người dùng ngẫu nhiên sẽ được chuyển đến trang đó bằng cách click vào các đường link. Mô hình này có thể được hiểu tương tự như Markov chain, trong đó các tỉnh là các trang web, quá trình di chuyển có xác suất ngang nhau được coi như các link giữa các trang web. Nếu như trang web không có đường link đến các trang khác, nó sẽ thành ngõ cụt và việc truy cập ngẫu nhiên sẽ dừng lại. Nhưng nếu người dùng đến trang không có các link khác, thì người dùng sẽ chọn ngẫu nhiên một trang khác để tiếp tục truy cập. Khi tính Pagerank, những trang không có link trỏ đi các trang khác sẽ được giả định có link trỏ đến tất cả các trang trong tập văn bản. Và như vậy giá trị Pagerank sẽ được chia đều cho các trang khác. Nói một cách khác, để công bằng với những trang web có outbound link, thì các truy cập ngẫu nhiên sẽ được thêm vào tất cả những trang trong Web, với xác suất d=0.85, được ước tính từ tần số trung bình mà người dùng sử dụng khi đánh dấu một tính năng bằng trình duyệt.

$PR(A)=1-d+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right).$

$p_{1},p_{2},...,p_{N}$ - là các trang được cân nhắc, $M(p_{i})$ - tập hợp những trang có link đến $p_{i}$, $L(p_{j})$ - số lượng link trỏ ra trong $p_{j}$, N– tổng số trang web.

Liên kết ngoài

• Our Search: Google Technology by Google
• How Google Finds Your Needle in the Web's Haystack by the American Mathematical Society