PageRank และ HITS แตกต่างกันอย่างไร

PageRank คำนวณคะแนนความสำคัญที่ไม่ขึ้นกับคำค้นหาเพียงค่าเดียวสำหรับทุกหน้าจากกราฟเว็บทั้งหมดล่วงหน้า ในขณะที่ HITS คำนวณคะแนนฮับและอำนาจที่ขึ้นกับคำค้นหาบนกราฟย่อยขนาดเล็กที่สร้างขึ้นรอบ ๆ คำค้นหาในขณะที่เรียกใช้ PageRank สามารถปรับขนาดได้ง่ายกว่าสำหรับการให้บริการบนเว็บ

เหตุใด PageRank จึงต้องมีปัจจัยการลดทอน

หากไม่มีปัจจัยนี้ นักท่องเว็บสุ่มอาจติดอยู่ในหน้าเว็บที่ไม่มีลิงก์ขาออกหรือติดอยู่ในวงจร และการแจกแจงสถานะคงที่อาจไม่ซ้ำกันหรือไม่ถูกกำหนดไว้อย่างดี ความน่าจะเป็นของการลดทอน (การเทเลพอร์ต) ทำให้นักท่องเว็บสามารถกระโดดไปยังหน้าสุ่มได้เป็นครั้งคราว ซึ่งรับประกันคะแนนที่ไม่ซ้ำกันและมีพฤติกรรมที่ดี

อัลกอริทึม PageRank และ HITS

PageRank และ HITS เป็นอัลกอริทึมวิเคราะห์ลิงก์ที่ประมาณความสำคัญหรืออำนาจของหน้าเว็บจากโครงสร้างของกราฟไฮเปอร์ลิงก์ มากกว่าที่จะพิจารณาจากเนื้อหาของหน้าเว็บเพียงอย่างเดียว

ค้นหาหัวข้อด้วย PaperMindเร็ว ๆ นี้Find papers & topics

Tools & resources

ดาวน์โหลดสไลด์

Learn & explore

วิดีโอเร็ว ๆ นี้

Definition

PageRank กำหนดคะแนนความสำคัญที่ไม่ขึ้นกับคำค้นหาให้กับแต่ละหน้า ซึ่งเท่ากับความน่าจะเป็นสถานะคงที่ (stationary probability) ภายใต้แบบจำลองนักท่องเว็บสุ่มที่ติดตามลิงก์ขาออกด้วยความน่าจะเป็นการลดทอน และเทเลพอร์ตในกรณีอื่น ๆ ในขณะที่ HITS คำนวณคะแนนอำนาจสำหรับหน้าที่มีเนื้อหาที่มีคุณค่าและคะแนนฮับสำหรับหน้าเว็บที่เชื่อมโยงไปยังแหล่งอำนาจที่ดี สำหรับกราฟย่อยที่ขึ้นกับคำค้นหา โดยแต่ละคะแนนจะเสริมซึ่งกันและกัน

Scope

หัวข้อนี้ครอบคลุมอัลกอริทึมพื้นฐานสองตัวในการวิเคราะห์ลิงก์ ได้แก่ PageRank ซึ่งเป็นการวัดความสำคัญของหน้าเว็บที่ไม่ขึ้นกับคำค้นหา โดยอิงจากแบบจำลองนักท่องเว็บสุ่มที่มีการเทเลพอร์ต (teleportation) และ HITS ซึ่งเป็นแผนการที่ขึ้นกับคำค้นหาที่คำนวณคะแนนฮับ (hub) และอำนาจ (authority) ที่เสริมซึ่งกันและกัน หัวข้อนี้จะกล่าวถึงการเดินสุ่ม (random-walk) และการกำหนดสูตรเวกเตอร์ลักษณะเฉพาะ (eigenvector formulations) ที่เป็นพื้นฐาน บทบาทของการลดทอน (damping) และการเทเลพอร์ต การลู่เข้า (convergence) และรูปแบบที่ไวต่อหัวข้อ (topic-sensitive variants) อย่างไรก็ตาม จะไม่รวมถึงวิธีการรวมคะแนนเหล่านี้เข้ากับคุณสมบัติของข้อความเพื่อจัดอันดับขั้นสุดท้าย ซึ่งเป็นส่วนหนึ่งของการจัดอันดับการค้นหาบนเว็บ

Core questions

แบบจำลองนักท่องเว็บสุ่มกำหนด PageRank เป็นการแจกแจงสถานะคงที่ได้อย่างไร
เหตุใดจึงต้องมีปัจจัยการลดทอนหรือการเทเลพอร์ตเพื่อให้ PageRank ถูกกำหนดไว้อย่างดี
คะแนนฮับและอำนาจใน HITS เสริมซึ่งกันและกันได้อย่างไร
คะแนนเหล่านี้คำนวณซ้ำ ๆ ได้อย่างไร และจะลู่เข้าเมื่อใด
PageRank และ HITS แตกต่างกันอย่างไรในการเป็นแบบไม่ขึ้นกับคำค้นหาเทียบกับแบบขึ้นกับคำค้นหา

Key concepts

PageRank
แบบจำลองนักท่องเว็บสุ่ม
ปัจจัยการลดทอนและการเทเลพอร์ต
การแจกแจงสถานะคงที่ / เวกเตอร์ลักษณะเฉพาะหลัก
HITS
ฮับและแหล่งอำนาจ
การให้คะแนนแบบไม่ขึ้นกับคำค้นหาเทียบกับแบบขึ้นกับคำค้นหา
การวนซ้ำกำลังและการลู่เข้า

Key theories

แบบจำลองนักท่องเว็บสุ่มของ PageRank: การจำลองนักท่องเว็บที่ติดตามลิงก์ด้วยความน่าจะเป็นเท่ากับปัจจัยการลดทอน และมิฉะนั้นจะกระโดดไปยังหน้าสุ่ม ทำให้เกิดลูกโซ่มาร์คอฟ (Markov chain) ซึ่งมีการแจกแจงสถานะคงที่ที่ไม่ซ้ำกันที่ให้คะแนนหน้าเว็บโดยการเยี่ยมชมในระยะยาว ซึ่งให้การวัดความสำคัญที่เสถียรและไม่ขึ้นกับคำค้นหา
ฮับและแหล่งอำนาจของ HITS: ภายในกราฟย่อยที่เน้นคำค้นหา HITS กำหนดคะแนนอำนาจให้กับแต่ละหน้าตามสัดส่วนของคะแนนฮับของหน้าเว็บที่เชื่อมโยงมายังหน้าดังกล่าว และคะแนนฮับตามสัดส่วนของคะแนนอำนาจของหน้าเว็บที่เชื่อมโยงไปถึง โดยคำนวณโดยการวนซ้ำความสัมพันธ์ที่เสริมซึ่งกันและกันเหล่านี้จนกว่าจะลู่เข้า

Clinical relevance

PageRank เป็นหัวใจสำคัญของการเติบโตของการค้นหาบนเว็บขนาดใหญ่ และยังคงเป็นจุดอ้างอิงเชิงแนวคิดสำหรับความสำคัญและอำนาจบนกราฟ แนวคิดการวิเคราะห์ลิงก์สามารถนำไปประยุกต์ใช้ได้นอกเหนือจากเว็บ เช่น เครือข่ายการอ้างอิง อิทธิพลในเครือข่ายสังคม การตรวจจับการฉ้อโกง และการแนะนำ ในทุกที่ที่ลิงก์ที่คล้ายกับการรับรองมีข้อมูล

History

ในปี 1998 และ 1999 มีข้อเสนอสองข้อที่เกิดขึ้นเกือบพร้อมกันซึ่งแสดงให้เห็นว่าไฮเปอร์ลิงก์เข้ารหัสอำนาจไว้ ได้แก่ HITS ของ Kleinberg และ PageRank ของ Page และ Brin คะแนนที่ไม่ขึ้นกับคำค้นหาและคำนวณทั่วโลกของ PageRank พิสูจน์แล้วว่าเหมาะสมอย่างยิ่งสำหรับการให้บริการบนเว็บขนาดใหญ่และเป็นรากฐานของเครื่องมือค้นหาชั้นนำ ในขณะที่ HITS มีอิทธิพลต่อการกลั่นกรองหัวข้อ (topic-distillation) และการวิจัยการจัดอันดับกราฟในภายหลัง

Key figures

Larry Page
Sergey Brin
Jon Kleinberg
Rajeev Motwani

Seminal works

page1999
kleinberg1999
brin1998

Frequently asked questions

PageRank และ HITS แตกต่างกันอย่างไร: PageRank คำนวณคะแนนความสำคัญที่ไม่ขึ้นกับคำค้นหาเพียงค่าเดียวสำหรับทุกหน้าจากกราฟเว็บทั้งหมดล่วงหน้า ในขณะที่ HITS คำนวณคะแนนฮับและอำนาจที่ขึ้นกับคำค้นหาบนกราฟย่อยขนาดเล็กที่สร้างขึ้นรอบ ๆ คำค้นหาในขณะที่เรียกใช้ PageRank สามารถปรับขนาดได้ง่ายกว่าสำหรับการให้บริการบนเว็บ
เหตุใด PageRank จึงต้องมีปัจจัยการลดทอน: หากไม่มีปัจจัยนี้ นักท่องเว็บสุ่มอาจติดอยู่ในหน้าเว็บที่ไม่มีลิงก์ขาออกหรือติดอยู่ในวงจร และการแจกแจงสถานะคงที่อาจไม่ซ้ำกันหรือไม่ถูกกำหนดไว้อย่างดี ความน่าจะเป็นของการลดทอน (การเทเลพอร์ต) ทำให้นักท่องเว็บสามารถกระโดดไปยังหน้าสุ่มได้เป็นครั้งคราว ซึ่งรับประกันคะแนนที่ไม่ซ้ำกันและมีพฤติกรรมที่ดี