Thuật toán PageRank và HITS

PageRank và HITS là các thuật toán phân tích liên kết ước tính tầm quan trọng hoặc quyền hạn của các trang web từ cấu trúc của đồ thị siêu liên kết chứ không chỉ từ nội dung trang.

Definition

PageRank gán cho mỗi trang một điểm quan trọng độc lập với truy vấn bằng xác suất dừng của nó dưới một người lướt ngẫu nhiên theo các liên kết đi với xác suất giảm xóc và dịch chuyển tức thời nếu không, trong khi HITS tính toán, cho một đồ thị con phụ thuộc vào truy vấn, điểm quyền hạn cho các trang có nội dung giá trị và điểm trung tâm cho các trang liên kết đến các quyền hạn tốt, mỗi điểm củng cố lẫn nhau.

Scope

Chủ đề này bao gồm hai thuật toán phân tích liên kết nền tảng: PageRank, một thước đo độc lập với truy vấn về tầm quan trọng của trang dựa trên mô hình người lướt ngẫu nhiên có dịch chuyển tức thời, và HITS, một sơ đồ phụ thuộc vào truy vấn tính toán các điểm số trung tâm (hub) và quyền hạn (authority) củng cố lẫn nhau. Nó đề cập đến các công thức đi bộ ngẫu nhiên và vector riêng cơ bản, vai trò của việc giảm xóc và dịch chuyển tức thời, sự hội tụ, và các biến thể nhạy cảm với chủ đề. Nó không bao gồm cách các điểm số này được kết hợp với các tính năng văn bản thành một xếp hạng cuối cùng, điều này thuộc về xếp hạng tìm kiếm web.

Core questions

• Mô hình người lướt ngẫu nhiên định nghĩa PageRank như một phân phối dừng như thế nào?
• Tại sao cần có yếu tố giảm xóc hoặc dịch chuyển tức thời để PageRank được định nghĩa rõ ràng?
• Các điểm số trung tâm và quyền hạn trong HITS củng cố lẫn nhau như thế nào?
• Các điểm số này được tính toán lặp lại như thế nào và khi nào chúng hội tụ?
• PageRank và HITS khác nhau như thế nào về việc độc lập với truy vấn so với phụ thuộc vào truy vấn?

Key concepts

• PageRank
• mô hình người lướt ngẫu nhiên
• hệ số giảm xóc và dịch chuyển tức thời
• phân phối dừng / vector riêng chính
• HITS
• trung tâm (hubs) và quyền hạn (authorities)
• chấm điểm độc lập với truy vấn so với phụ thuộc vào truy vấn
• lặp lại lũy thừa và hội tụ

Key theories

Mô hình người lướt ngẫu nhiên PageRank

Mô hình hóa một người lướt theo các liên kết với xác suất bằng một hệ số giảm xóc và nếu không thì nhảy đến một trang ngẫu nhiên tạo ra một chuỗi Markov mà phân phối dừng duy nhất của nó chấm điểm các trang theo lượt truy cập dài hạn, đưa ra một thước đo tầm quan trọng ổn định, độc lập với truy vấn.

Trung tâm và quyền hạn của HITS

Trong một đồ thị con tập trung vào truy vấn, HITS gán cho mỗi trang một điểm quyền hạn tỷ lệ với điểm trung tâm của các trang liên kết đến nó và một điểm trung tâm tỷ lệ với điểm quyền hạn của các trang mà nó liên kết đến, được tính toán bằng cách lặp lại các mối quan hệ củng cố lẫn nhau này cho đến khi hội tụ.

Clinical relevance

PageRank là trung tâm của sự phát triển tìm kiếm web quy mô lớn và vẫn là một điểm tham chiếu khái niệm về tầm quan trọng và quyền hạn trên các đồ thị. Các ý tưởng phân tích liên kết tổng quát hóa vượt ra ngoài web đến các mạng trích dẫn, ảnh hưởng mạng xã hội, phát hiện gian lận và đề xuất, bất cứ nơi nào các liên kết giống như sự chứng thực mang thông tin.

History

Vào năm 1998 và 1999, hai đề xuất gần như đồng thời đã chỉ ra rằng các siêu liên kết mã hóa quyền hạn: HITS của Kleinberg và PageRank của Page và Brin. Các điểm số độc lập với truy vấn, được tính toán toàn cầu của PageRank đã chứng tỏ rất phù hợp cho việc phục vụ quy mô web và là nền tảng của một công cụ tìm kiếm hàng đầu, trong khi HITS đã ảnh hưởng đến việc chắt lọc chủ đề và nghiên cứu xếp hạng đồ thị sau này.

Key figures

• Larry Page
• Sergey Brin
• Jon Kleinberg
• Rajeev Motwani

Seminal works

• page1999
• kleinberg1999
• brin1998

Frequently asked questions

Sự khác biệt giữa PageRank và HITS là gì?

PageRank tính toán một điểm quan trọng duy nhất độc lập với truy vấn cho mọi trang từ toàn bộ đồ thị web trước, trong khi HITS tính toán các điểm trung tâm và quyền hạn phụ thuộc vào truy vấn trên một đồ thị con nhỏ được xây dựng xung quanh truy vấn tại thời điểm truy xuất. PageRank mở rộng dễ dàng hơn để phục vụ web.

Tại sao PageRank cần một hệ số giảm xóc?

Nếu không có nó, người lướt ngẫu nhiên có thể bị mắc kẹt trong các trang không có liên kết đi hoặc trong các chu kỳ, và phân phối dừng có thể không duy nhất hoặc không được định nghĩa rõ ràng. Xác suất giảm xóc (dịch chuyển tức thời) cho phép người lướt thỉnh thoảng nhảy đến một trang ngẫu nhiên, đảm bảo một điểm số duy nhất, hoạt động tốt.