อัลกอริธึมอันดับเพจในการทำเหมืองเว็บคืออะไร?

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

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

กลไกของเว็บขึ้นอยู่กับกราฟที่มีประมาณ 150 ล้านโหนด (หน้าเว็บ) และ 1.7 พันล้านขอบ (ไฮเปอร์ลิงก์) หากหน้าเว็บ A และ B เชื่อมโยงไปยังหน้า C, A และ B เรียกว่าลิงก์ย้อนกลับของ C โดยทั่วไป หน้าที่เชื่อมโยงอย่างมากมีความสำคัญมากกว่า ดังนั้นพวกเขาจึงมีลิงก์ย้อนกลับมากขึ้นและลิงก์ย้อนกลับที่สำคัญมีปริมาณน้อยลง

ตัวอย่างเช่น หน้าเว็บที่มีลิงก์ย้อนกลับส่วนบุคคลจาก Yahoo จะต้องอยู่ในอันดับที่สูงกว่าหน้าที่มีลิงก์ย้อนกลับหลายรายการจากไซต์ที่ไม่รู้จักหรือไซต์ส่วนตัว หน้าเว็บจะมีอันดับที่สูงหากอันดับของลิงก์ย้อนกลับมีขนาดใหญ่เกินไป

ต่อไปนี้เป็นเวอร์ชันย่อของ PageRank:Let u, v be Web pages ดังนั้นให้บูเป็นกลุ่มของเพจที่ชี้มาที่คุณ ยิ่งกว่านั้น ให้ Nv เป็นลิงค์หลายอันจาก v. ให้ c <1 เป็นปัจจัยในการทำให้เป็นมาตรฐาน สามารถอธิบายการจัดอันดับ R อย่างง่าย ซึ่งเป็นการตีความอันดับเพจอย่างง่าย -

$$\mathrm{R(u)\:=\:c\displaystyle\sum\limits_{u\in{Bu}}\frac{R(v)}{N_v}}$$

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

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

อัลกอริธึม Page Rank เริ่มต้นด้วยการแปลง URL ทุกรายการจากฐานข้อมูลเป็นตัวเลข ขั้นต่อไปคือการบันทึกไฮเปอร์ลิงก์แต่ละรายการในฐานข้อมูลโดยใช้รหัสจำนวนเต็มเพื่อจดจำเว็บเพจ การวนซ้ำเริ่มต้นหลังจากจัดเรียงโครงสร้างลิงก์ตาม ID พาเรนต์และลบลิงก์ที่ห้อยอยู่

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