giatu1112
06-06-2011, 07:29
1. GIỚI THIỆU
ABSTRACT
Là một trong những giải thuật phân tích liên kết, PageRank ra đời sau HITS nhưng những gì mà nó đóng góp là không nhỏ. Dựa vào giải thuật PageRank mà Google đã thay đổi quan niệm của mọi người về ứng dụ tìm kiếm, cũng như tầm quan trọng của nó ngày nay. Tuy đã hơn 10 năm trôi qua và đã xuất hiện hàng loạt các phát triển hay các thuật toán tương tự như TrustRank của Yahoo! Hay BrowseRank của Microsoft, nhưng vị trí số một của cỗ máy tìm kiếm Google trong cộng đồng vẫn chưa tỏ ra bị lung lay.
1.1. Khái niệm
Google đã mô tả về PageRank như sau:
(*) “PageRank dựa vào những tính chất dân chủ tự nhiên riêng biệt của web bằng cách sử dụng cấu trúc liên kết rộng lớn như là một dụng cụ đo giá trị cá nhân của trang web. Trên thực tế, Google sẽ xem một liên kết từ trang A đến trang B như một bình chọn (vote), A sẽ là nhân tố để bình chọn cho B. Tuy nhiên, Google xem xét nhiều hơn là chỉ dựa trên khối lượng bình chọn, hoặc số liên kết mà trang nhận được; nó còn phân tích về trang tác động (thực hiện) đến bình chọn. Bình chọn được thực hiện (vote cast) bởi các trang càng ‘quan trọng’ thì trọng số càng ‘nặng’ và làm cho các trang khác cũng trở nên ‘quan trọng’.”
Hình 1.1. Mô hình đồ thị có hướng với các trang được xem là đỉnh và có trọng số PageRank và khả năng web surfer tại mỗi đỉnh.
Ở hình trên (trích từ [1]), trang C có PageRank cao hơn trang E mặc dù có ít liên kết trỏ đến nó hơn bởi liên kết trỏ đến C có giá trị cao hơn rất nhiều. Web surfer chọn một liên kết ngẫu nhiên trên mỗi trang nhảy đến trang E là 8.1%. Khả năng nhảy đến một trang trong toàn bộ trang một cách ngẫu nhiên là 15%; 15% hay 85% (xem mục 2.5.1) này được xem như một nhân tố hãm (damping factor) bởi không có nó, quá trình duyệt ngẫu nhiên (random web surfer) sẽ kết thúc ngay trên trang A, B, hay C; điều này khiến cho các trang khác sẽ có giá trị PageRank là 0. Ngoài ra, trang A được giả định liên kết tất cả các trang bởi nó không có outgoing link (xem mục 2.4.1).
Đây chính xác là ý tưởng về Rank Prestige trong Social Network.
Nói cách khác, kết quả của PageRank từ một “lá phiếu” (ballot) giữa tất cả các trang khác trong World Wide Web cho biết độ quan trọng của một trang web như thế nào. Một liên kết trỏ đến một trang tính như một bình chọn hỗ trợ. PageRank của một trang web được định nghĩa bởi sự đệ quy và phụ thuộc vào số lượng và độ đo PageRank của tất cả các trang liên kết đến nó, còn gọi là các liên kết nội (incoming link). Một trang được liên kết với nhiều trang khác với giá trị PageRank cao sẽ có một thứ hạng cao. Nếu không có liên kết nào đến trang web, sẽ không có bất kì sự hỗ trợ đánh giá nào cho trang web đó. Google sẽ gán một trọng số trong khoảng từ 0 đến 10 cho mỗi trang web trên internet; dựa vào đó PageRank sẽ cho biết tầm quan trọng của một site trong con mắt của Google.
PageRank bắt nguồn từ lý thuyết xác suất (theoretical probability) định giá trên Logarithmic Scale, tương tự như Richter Scale.
Ngoài ra, một liên kết từ một trang này đến các trang khác còn mang hàm ý về authority của các trang mà nó liên kết đến. Hay nói cách khác, càng nhận nhiều incoming link thì độ prestige của trang web càng tăng. Bất kì một trang nào cũng có độ prestige riêng, do đó bất kì một trang nào liên kết đến các trang khác cũng đều sở hữu độ prestige riêng của nó. Như vậy, một trang A có độ prestige cao hơn khi trỏ đến trang C nào đó sẽ “quan trọng” hơn một trang B nào đó cũng trỏ đến C nhưng có độ prestige thấp hơn A. Nói cách khác, một trang sẽ là “quan trọng” nếu nó được trỏ đến bởi một trang “quan trọng” khác. Nhờ cơ chế đánh giá này nên PageRank tránh được nguy cơ bị spamdexing và spoofing so với HITS.
ABSTRACT
Là một trong những giải thuật phân tích liên kết, PageRank ra đời sau HITS nhưng những gì mà nó đóng góp là không nhỏ. Dựa vào giải thuật PageRank mà Google đã thay đổi quan niệm của mọi người về ứng dụ tìm kiếm, cũng như tầm quan trọng của nó ngày nay. Tuy đã hơn 10 năm trôi qua và đã xuất hiện hàng loạt các phát triển hay các thuật toán tương tự như TrustRank của Yahoo! Hay BrowseRank của Microsoft, nhưng vị trí số một của cỗ máy tìm kiếm Google trong cộng đồng vẫn chưa tỏ ra bị lung lay.
1.1. Khái niệm
Google đã mô tả về PageRank như sau:
(*) “PageRank dựa vào những tính chất dân chủ tự nhiên riêng biệt của web bằng cách sử dụng cấu trúc liên kết rộng lớn như là một dụng cụ đo giá trị cá nhân của trang web. Trên thực tế, Google sẽ xem một liên kết từ trang A đến trang B như một bình chọn (vote), A sẽ là nhân tố để bình chọn cho B. Tuy nhiên, Google xem xét nhiều hơn là chỉ dựa trên khối lượng bình chọn, hoặc số liên kết mà trang nhận được; nó còn phân tích về trang tác động (thực hiện) đến bình chọn. Bình chọn được thực hiện (vote cast) bởi các trang càng ‘quan trọng’ thì trọng số càng ‘nặng’ và làm cho các trang khác cũng trở nên ‘quan trọng’.”
Hình 1.1. Mô hình đồ thị có hướng với các trang được xem là đỉnh và có trọng số PageRank và khả năng web surfer tại mỗi đỉnh.
Ở hình trên (trích từ [1]), trang C có PageRank cao hơn trang E mặc dù có ít liên kết trỏ đến nó hơn bởi liên kết trỏ đến C có giá trị cao hơn rất nhiều. Web surfer chọn một liên kết ngẫu nhiên trên mỗi trang nhảy đến trang E là 8.1%. Khả năng nhảy đến một trang trong toàn bộ trang một cách ngẫu nhiên là 15%; 15% hay 85% (xem mục 2.5.1) này được xem như một nhân tố hãm (damping factor) bởi không có nó, quá trình duyệt ngẫu nhiên (random web surfer) sẽ kết thúc ngay trên trang A, B, hay C; điều này khiến cho các trang khác sẽ có giá trị PageRank là 0. Ngoài ra, trang A được giả định liên kết tất cả các trang bởi nó không có outgoing link (xem mục 2.4.1).
Đây chính xác là ý tưởng về Rank Prestige trong Social Network.
Nói cách khác, kết quả của PageRank từ một “lá phiếu” (ballot) giữa tất cả các trang khác trong World Wide Web cho biết độ quan trọng của một trang web như thế nào. Một liên kết trỏ đến một trang tính như một bình chọn hỗ trợ. PageRank của một trang web được định nghĩa bởi sự đệ quy và phụ thuộc vào số lượng và độ đo PageRank của tất cả các trang liên kết đến nó, còn gọi là các liên kết nội (incoming link). Một trang được liên kết với nhiều trang khác với giá trị PageRank cao sẽ có một thứ hạng cao. Nếu không có liên kết nào đến trang web, sẽ không có bất kì sự hỗ trợ đánh giá nào cho trang web đó. Google sẽ gán một trọng số trong khoảng từ 0 đến 10 cho mỗi trang web trên internet; dựa vào đó PageRank sẽ cho biết tầm quan trọng của một site trong con mắt của Google.
PageRank bắt nguồn từ lý thuyết xác suất (theoretical probability) định giá trên Logarithmic Scale, tương tự như Richter Scale.
Ngoài ra, một liên kết từ một trang này đến các trang khác còn mang hàm ý về authority của các trang mà nó liên kết đến. Hay nói cách khác, càng nhận nhiều incoming link thì độ prestige của trang web càng tăng. Bất kì một trang nào cũng có độ prestige riêng, do đó bất kì một trang nào liên kết đến các trang khác cũng đều sở hữu độ prestige riêng của nó. Như vậy, một trang A có độ prestige cao hơn khi trỏ đến trang C nào đó sẽ “quan trọng” hơn một trang B nào đó cũng trỏ đến C nhưng có độ prestige thấp hơn A. Nói cách khác, một trang sẽ là “quan trọng” nếu nó được trỏ đến bởi một trang “quan trọng” khác. Nhờ cơ chế đánh giá này nên PageRank tránh được nguy cơ bị spamdexing và spoofing so với HITS.