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 BULLET 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 BULLET 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 đó BULLET Á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ể BULLET 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à formula _ 1 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_hoá 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 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 PageRank được tính cho 1 outbound link sẽ bằng số score pagerank của document đó chia cho số outbound link L Công_thức chung giá_trị Pagerank đối_với bất_kỳ trang u có_thể tính như sau 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 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 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 formula _ 8 là các trang được cân_nhắc formula _ 9 tập_hợp những trang có link đến formula _ 10 formula _ 11 số_lượng link trỏ ra trong formula _ 12 N tổng_số trang_web Liên_kết ngoài BULLET Our_Search_Google_Technology by Google BULLET How_Google_Finds_Your Needle in the Web s Haystack by the American_Mathematical_Society
PageRank