PageRank

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

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

Giới thiệu

Giá trị PageRank được xác định từ thuật toán toán học dựa trên đồ thị web: các trang web trên World Wide Web được xem như các đỉnh và các liên kết giữa chúng được coi là các cạnh. Khi xây dựng đồ thị web, các trang của các cơ quan uy tín như cnn.com hoặc usa.gov được đưa vào tính toán. Giá trị xếp hạng phản ánh tầm quan trọng của từng trang cụ thể. Mỗi liên kết đến trang web được xem như một yếu tố nâng cao giá trị PageRank của nó. Giá trị PageRank của một trang được định nghĩa theo đệ quy và phụ thuộc vào số lượng và chất lượng các trang liên kết đến nó (liên kết đến). Một trang có nhiều liên kết từ các trang có PageRank cao sẽ có PageRank cao hơn. Có nhiều bài viết công bố dựa trên nghiên cứu của Page và Brin. Tuy nhiên, việc thao tác với khái niệm PageRank rất phức tạp. Nhiều nghiên cứu đã chỉ ra các ảnh hưởng sai lệch đến xếp hạng PageRank và tìm cách loại bỏ hiệu quả các liên kết có ảnh hưởng sai.

Thuật toán

PageRank là một phân bố xác suất dùng để thể hiện khả năng mà một người có thể nhấp chuột ngẫu nhiên vào liên kết và đến một trang web cụ thể. PageRank có thể được tính cho các tập văn bản có độ dài khác nhau. Khi bắt đầu tính toán, phân bố được chia đều cho tất cả các văn bản trong tập. Để đạt được giá trị thực tế, cần phải thực hiện nhiều lần 'lặp lại' qua các văn bản trong tập. 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' một sự kiện có thể xảy ra. Trong PageRank, giá trị 0.5 có nghĩa là 50% cơ hội một người nhấp vào liên kết ngẫu nhiên để đến được văn bản đó (PageRank = 0.5).

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

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

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

Khác với ví dụ trước, B liên kết đến các trang C và A, trong khi D có liên kết đến tất cả các trang. Do đó, trong bước tiếp theo, trang B sẽ phân bổ một nửa giá trị của mình, tức là 0.125 cho trang A và 0.125 cho trang C. Trang D, với 3 liên kết ra, sẽ phân bổ 1/3 giá trị của mình, tương đương với 0.083 cho trang A.

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

PageRank của một liên kết ra được tính bằng cách chia điểm PageRank của tài liệu cho số lượng liên kết ra L().

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

Công thức tổng quát để tính giá trị PageRank của bất kỳ trang web u có thể được mô tả như sau:

$PR\left(u\right)=\underset{v\in <!--\; \in \; -->B_u}{\sum <!--\; \sum \; -->}\frac{PR\left(v\right)}{L\left(v\right)}$,

Giá trị PageRank của trang u được xác định dựa trên giá trị PageRank của các trang v trong tập hợp B_u (các trang có liên kết đến u), được chia cho số lượng liên kết ra L (v) từ trang v.

Yếu tố giảm giá

Lý thuyết PageRank cho rằng, ngay cả khi người dùng nhấp vào các trang web một cách ngẫu nhiên, họ cũng sẽ dừng lại sau một thời gian. Xác suất người dùng tiếp tục nhấp chuột trong bất kỳ bước nào được gọi là yếu tố giảm giá. Các nghiên cứu đã thử nghiệm với nhiều giá trị khác nhau cho yếu tố giảm giá, trong đó giá trị thường sử dụng là 0.85, có nghĩa là người dùng sẽ tiếp tục duyệt web với xác suất 85%. Công thức tính PageRank với yếu tố giảm giá xem xét rằng người dùng có thể cảm thấy chán sau một số lần nhấp và chọn chuyển đến các trang web khác một cách ngẫu nhiên. Do đó:

$PR\left(A\right)=\frac{1-<!--\; -\; -->d}{N}+d\left(\frac{PR\left(B\right)}{L\left(B\right)}+\frac{PR\left(C\right)}{L\left(C\right)}+\frac{PR\left(D\right)}{L\left(D\right)}+\cdots <!--\; \cdots \; -->\right).$

Công thức này áp dụng mô hình khi người dùng ngẫu nhiên cảm thấy chán và được chuyển hướng đến các trang khác một cách ngẫu nhiên. Giá trị Pagerank cho biết khả năng mà người dùng sẽ chuyển đến một trang cụ thể bằng cách nhấp vào các liên kết. Mô hình này có thể được coi là một chuỗi Markov, với các trang web là các trạng thái và các liên kết giữa chúng là các chuyển tiếp với xác suất đồng đều. Nếu một trang không có liên kết nào đến các trang khác, nó sẽ trở thành một ngõ cụt và người dùng sẽ ngừng truy cập. Tuy nhiên, nếu người dùng đến một trang không có liên kết ra, họ sẽ ngẫu nhiên chọn một trang khác để tiếp tục. Khi tính toán Pagerank, những trang không có liên kết ra sẽ được giả định có liên kết đến tất cả các trang trong tập hợp văn bản, và do đó giá trị Pagerank sẽ được phân phối đều cho tất cả các trang. Nói cách khác, để công bằng với những trang có liên kết ra, các lượt truy cập ngẫu nhiên sẽ được phân bổ đều cho tất cả các trang web với xác suất d=0.85, ước lượng từ tần suất trung bình mà người dùng nhấp vào các tính năng của trình duyệt.

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

$p_1,p_2,...,p_N$ - là các trang web được xem xét, $M\left(p_i\right)$ - là tập hợp các trang có liên kết đến $p_i$, $L\left(p_j\right)$ - số lượng liên kết ra trong $p_j$, N – tổng số trang web.

Chú thích

Liên kết bên ngoài

• Tìm kiếm của chúng tôi: Công nghệ Google do Google cung cấp
• Cách Google tìm kim trong đống rơm trên web bởi Hội Toán học Mỹ