PageRank Algorithm

อัลกอริทึม PageRank ใช้จัดอันดับเว็บและช่วยให้ได้ผลลัพธ์ของ search engine ที่ดียิ่งขึ้น คิดค้นโดย Sergey Brin และ Larry Page ปี 1998 สมัยเป็นนักศึกษาอยู่ที่ Standford University หรือที่หลายๆท่านรู้จักในฐานะผู้ก่อตั้ง Google หลักการของมันคือ เว็บไซต์จะมีความสำคัญหรือลำดับที่ดีก็ตื่อเมือถูกชี้โดยเหล่าบรรดาเว็บไซต์ที่สำคัญหรือลำดับที่ดีเช่นกัน
ตัวอย่างจากภาพด้านบนเป็น Directed Graph ที่ใช้แทนโครงสร้างของเว็บไซต์
เว็บไซต์เบอร์ 1 มีลิงค์เชื่อมไปยัง เว็บไซต์เบอร์ 2 และเว็บไซต์เบอร์ 3เว็บไซต์เบอร์ 2 ไม่มีลิงค์เชื่อมไปยังเว็บไซต์ใดๆเลย
เว็บไซต์เบอร์ 3 มีลิงค์เชื่อมไปยัง เว็บไซต์เบอร์ 1 เว็บไซต์เบอร์ 2 และเว็บไซต์เบอร์ 5
เว็บไซต์เบอร์ 4 มีลิงค์เชื่อมไปยัง เว็บไซต์เบอร์ 5 และเว็บไซต์เบอร์ 6
เว็บไซต์เบอร์ 5 มีลิงค์เชื่อมไปยัง เว็บไซต์เบอร์ 4 และเว็บไซต์เบอร์ 6
เว็บไซต์เบอร์ 6 มีลิงค์เชื่อมไปยัง เว็บไซต์เบอร์ 4 เพียบเว็บไซต์เดียว
ปล. หัวลูกศรคือแท่งหนาๆทึบ ไม่ค่อยสวยเท่าไร

ความสำคัญของเว็บไซต์ i เกิดจากผลรวมค่าความสำคัญของเว็บไซต์ใดๆที่ชี้มายังเว็บไซต์ i

  1. เมตริกซ์ H จะใช้เก็บอัตราส่วนค่าของความสำคัญ คำนวณโดย
    H_{i j}=\frac{1}{|P_{i}|}
    |P_{i}| คือจำนวนลิงค์ที่พุ่งออกจากเวอร์เท็กซ์ i
    ถ้ามีลิงค์จากเวอร์เท็กซ์ i ไปเวอร์เท็กซ์ j ถ้าไม่มีลิงค์ให้เป็น 0 ดังนั้นจากกราฟด้านบนจะได้เมตริกซ์ H ดังนี้
    H=\begin{bmatrix}0&\frac{1}{2}&\frac{1}{2}&0&0&0\\  0&0&0&0&0&0\\  \frac{1}{3}&\frac{1}{3}&0&0&\frac{1}{3}&0\\  0&0&0&0&\frac{1}{2}&\frac{1}{2}\\  0&0&0&\frac{1}{2}&0&\frac{1}{2}\\  0&0&0&1&0&0\\  \end{bmatrix}
    สังเกตได้ว่าถ้ามีลิงค์พุ่งออกมามากอัตราส่วนความสำคัญที่จะกำหนดให้แก่บรรดาเวอร์เท็กซ์ที่ถูกชี้ก็จะถูกทอนให้น้อยลงตามไปด้วยในตอนเริ่มต้นจะให้ทุกๆเวอร์เท็กซ์มีค่าความสำคัญเท่ากัน โดยให้เวกเตอร์  \pi เท่ากับ หนึ่งส่วนด้วยจำนวนเวอร์เท็กซ์ แต่ละเอนทรี่ของเวกเตอร์จะหมายถึงค่าความสำคัญของเวอร์เท็กซ์ที่ 1 ถึง 6 ตามลำดับ เขียนเป็นสมการได้ดังนี้
    \pi^t=\frac{1}{n}=  \begin{bmatrix}^1/_6\;^1/_6\;^1/_6\;^1/_6\;^1/_6\;^1/_6\end{bmatrix}
    โดยที่ n คือจำนวนเวอร์เท็กซ์ สาเหตุที่ต้องทรานสโพสเพราะว่าต้องเอาไปคูณกับเมตริกซ์ H ในขั้นตอนต่อไป
  2. ขั้นตอนต่อมา เราต้องหาก่อนว่า จากเวอร์เท็กซ์ i ไปเวอร์เท็กซ์ j นั้นสามารถทำได้กี่หนทาง อาจจะผ่านเวอร์เท็กซ์อื่นก็ได้ เช่น จากเวอร์เท็กซ์ 3 ไปเวอร์เท็กซ์ 6 ซึ่งจะเดินจาก 3\rightarrow5\rightarrow6 เส้นทางนี้มีความยาว(length)เป็นสอง สิ่งที่เราสนใจคืออัตราส่วนความสำคัญที่เริ่มจากเวอร์เท็กซ์ i ผ่านไปยังเวอร์เท็กซ์ต่างๆจนไปถึงเวอร์เท็กซ์ j ตัวอย่างเช่น 3\rightarrow5\rightarrow6 จะมีอัตราส่วนความสำคัญ ^1/_3\times^1/_2 แล้วเราจะหาอัตราส่วนความสำคัญของการเดินที่มีความยาวเป็น 2 นี้ได้อย่างไร คำตอบคือ การคูณเมตริกซ์ H สองครั้ง หรือ H^2 การคูณเมตริกซ์ระหว่าง H กับ H จะทำให้เกิดการเดินมีความยาวเป็น 2
    H^2=\begin{bmatrix}\frac{1}{6}&\frac{1}{6}&0&0&\frac{1}{6}&0\\  0&0&0&0&0&0\\  0&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}&0&\frac{1}{6}\\  0&0&0&\frac{3}{4}&0&\frac{1}{4}\\  0&0&0&\frac{1}{2}&\frac{1}{4}&\frac{1}{4}\\  0&0&0&0&\frac{1}{2}&\frac{1}{2}\\  \end{bmatrix}
    มีเส้นทางดังต่อไปนี้   
    1\rightarrow3\rightarrow 1 =^1/_2\times^1/_3 = ^1/_6
    1\rightarrow3\rightarrow2 =^1/_2\times^1/_3 = ^1/_6
    1\rightarrow3\rightarrow5 =^1/_2\times^1/_3 = ^1/_6
    3\rightarrow1\rightarrow2 =^1/_3\times^1/_2 = ^1/_6
    3\rightarrow1\rightarrow3 =^1/_3\times^1/_2 = ^1/_6
    3\rightarrow5\rightarrow4 =^1/_3\times^1/_2 = ^1/_6
    3\rightarrow5\rightarrow6 =^1/_3\times^1/_2 = ^1/_6
    4\rightarrow5\rightarrow4\&4\rightarrow6\rightarrow4 =^1/_2\times^1/_2 +^1/_2\times1= ^3/_4
    4\rightarrow5\rightarrow6 =^1/_2\times^1/_2 = ^1/_4
    5\rightarrow6\rightarrow4 =1\times^1/_2 = ^1/_2
    5\rightarrow4\rightarrow5 =^1/_2\times^1/_2 = ^1/_4
    5\rightarrow4\rightarrow6 =^1/_2\times^1/_2 = ^1/_4
    6\rightarrow4\rightarrow5 =1\times^1/_2 = ^1/_2
    6\rightarrow4\rightarrow6 =1\times^1/_2 = ^1/_2
    เส้นทางที่ไม่มีทางเดินจะมีค่าอัตราส่วนความสำคัญเป็นศูนย์ ยิ่งถ้าเราเอาเมตริกซ์ H มาคูณด้วยตัวเองเรื่อยๆจะเดินได้ไกลมากขึ้นตัวอย่างเช่น H^3 จะมีเส้นทาง 1\rightarrow3\rightarrow5\rightarrow6 เป็นต้น
  3. ขั้นตอนต่อมาจะเอาเวกเตอร์ค่าความสำคัญ \pi^t คูณกับเมตริกซ์อัตราความสำคัญ H เพื่อดูว่าเมื่อเดินไประยะ lenght=1 นั้นส่งผลต่อเวกเตอร์ค่าความสำคัญ \pi^t แค่ไหน \pi^t_1=\pi^t_0H=\begin{bmatrix}0.056\;0.139\;0.083\;0.250\;0.139\;0.167\end{bmatrix} เมื่อลองรันไปเรื่อยๆจะพบว่า สัก  \pi^t_4=\begin{bmatrix}0.000\;0.000\;0.000\;0.267\;0.133\;0.200\end{bmatrix}  ค่าความสำคัญของเวอร์เท็กซ์ 1 2 และ 3 กลับลดลงจนเข้าใกล้ศูนย์ ทั้งนี้เกิดจากปัญหาสองอย่างคือ
    1. ปัญหา Dangling node เช่นเวอร์เท็กซ์ 2 ซึ่งไม่มีลิงค์ออกจากเวอร์เท็กซ์เลย รับค่าความสำคัญจากเวอร์เท็กซ์ 1 และ 3 เพียงอย่างเดียว ไม่มีการถ่ายโอนไปชี้เวอร์เท็กอื่น ทำให้ค่าความสำคัญของเวอร์เท็กซ์ 2 เป็น 0 ในการลูปครั้งต่อไป วิธีแก้ปัญหาคือเวอร์เท็กซ์ใดเป็น dangling node ให้สร้างลิงค์ไปยังทุกๆเวอร์เทกซ์โดยที่แต่ละลิงค์เท่ากับ \frac{1}{n} หรือเปลี่ยนเมตริกซ์ H เป็นเมตริกซ์ใหม่ที่ชื่อ S ดังนี้
      S=H+a_{i}(\frac{1}{n}e^t)
      โดยที่ a_{i}=1   ก็ต่อเมื่อเวอร์เท็กซ์  i  เป็น dangling node a_{i}=0 เมื่อไม่ใช่ ให้ e^t   คือเวกเตอร์แบบแถวที่เป็น1 หมดมีจำนวนคอลัมน์เท่ากับ n ดังนั้น จะได้
      S=\begin{bmatrix}0&\frac{1}{2}&\frac{1}{2}&0&0&0\\  \frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}\\  \frac{1}{3}&\frac{1}{3}&0&0&\frac{1}{3}&0\\  0&0&0&0&\frac{1}{2}&\frac{1}{2}\\  0&0&0&\frac{1}{2}&0&\frac{1}{2}\\  0&0&0&1&0&0\\  \end{bmatrix}
    2. ปัญหา ก็ยังไม่หมดไปยังมีปัญหาอีกปัญหาคือปัญหา Cycle เช่นเวอร์เท็กซ์ 1 กับเวอร์เท็กซ์ 3 เป็น Cycle วนลูป ทำให้การหาค่าความสำคัญค่อยๆเป็น 0 ในที่สุด และปัญหากราฟไม่เชื่อมต่อกัน Brin และ Page จึงคิดค้น Google Matrix ที่สามารถเทเลพอร์ทไปยังที่อื่นได้ ในกรณีที่ตกอยู่ในวังวนออกมาไม่ได้ ก็จะแรนดอมออกไปยังโครงสร้างเว็บอื่น โดย เมตริกซ์ G คือ
      G=\alpha S+(1-\alpha)\frac{1}{n}e e^t
      โดยที่ \alpha คือค่าสเกล่าร์อยู่ในช่วง 0 ถึง 1
      เช่น \alpha=0.9 หมายถึงจะเดินไปตามโครงสร้างเว็บปรกติ 90% และจะเทเลพอร์ทแบบสุ่มมั่วๆไปหน้าเว็บอื่นๆอีก 10% เราจะเรียก \alpha ว่า damping factor
      และ e e^t เวอร์เตอร์ที่เป็น 1 หมดแบบหลักและแบบแถวคูณกันจะได้เมตริกซ์ขนาด n \times n จะได้
      G=\begin{bmatrix}\frac{1}{60}&\frac{7}{15}&\frac{7}{15}&\frac{1}{60}&\frac{1}{60}&\frac{1}{60}\\  \frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}\\  \frac{19}{60}&\frac{19}{60}&\frac{1}{60}&\frac{1}{60}&\frac{19}{60}&\frac{1}{60}\\  \frac{1}{60}&\frac{1}{60}&\frac{1}{60}&\frac{1}{60}&\frac{7}{15}&\frac{7}{15}\\  \frac{1}{60}&\frac{1}{60}&\frac{1}{60}&\frac{7}{15}&\frac{1}{60}&\frac{7}{15}\\  \frac{1}{60}&\frac{1}{60}&\frac{1}{60}&\frac{11}{12}&\frac{1}{60}&\frac{1}{60}\\  \end{bmatrix}
      ตัวอย่างการคำนวนเช่น G_{1,2}=\frac{9}{10}\times\frac{1}{2}+\frac{1}{10}\times\frac{1}{6}=\frac{7}{15}
  4.  ใช้เมตริกซ์ G แทนในเมตริกซ์ H ในข้อ 3 ซึ่งจะได้สมการทั่วไปดังนี้
    \pi^t_{k+1}=\pi^t_k G
    ลองรันหลายๆรอบดู \pi^t จะได้เท่ากับ \begin{bmatrix}0.037\;0.054\;0.042\;0.375\;0.206\;0.286\end{bmatrix} หรือลำดับความสำคัญของเวอร์เท็กคือ (6 4 5 1 3 2)

    จากการสังเกตกราฟด้านบนแล้วก็น่าจะจริงที่เวอร์เท็กซ์ 4 มีโอกาสเข้าถึงได้มากกว่าจึงมีความสำคัญอันดับหนึ่ง และอาจเพราะว่าเวอร์เท็กซ์ 6 ชี้มายัง 4 แต่เพียงผู้เดียวด้วยช่วยให้เวอร์เท็กซ์ 4 มีความสำคัญมากขึ้น และเวอร์เทกซ์ 1 2 และ 3 ไม่สามารถเข้าถึงได้โดยเวอร์เทกซ์ 4 5 6 แต่เวอร์เทกซ์ 4 5 6 กลับสามารถูกเข้าถึงโดยเวอร์เทกซ์ 1 2 และ 3 ได้ ทำให้ค่าความสำคัญเวอร์เทกซ์ 4 5 6 มีค่าความสำคัญมากกว่าเวอร์เทกซ์ 1 2 3
    โปรแกรมทั้งหมดสามารถเขียนทดลองใน Microsoft Excel ได้ครับใช้ function คูณเมตริกซ์ MMULT

  5. หรือสามารถทดลองโดยใช้ framework ของเน็ทเวิร์ก networkx

    ผลลัพธ์ {1: 0.03721312715805474, 2: 0.05395936859791858, 3: 0.04150700697389663, 4: 0.3750784815111541, 5: 0.20599776987949375, 6: 0.28624424587948205}
    ตัวโปรแกรมจะลูปโดย default 100 ครั้ง

    โดยปรกติจะใช้ \alpha=0.85

    การประยุกต์ใช้ PageRank กับ Social Network Mining นั้นจะใช้หาว่าบุคคลใดเป็นบุคคลสำคัญที่ถูกอ้างอิงโดยบุคลลอื่นๆที่มีความสำคัญ

    references:
    1. The Mathematics of Web Search http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/
    2.Study of Page Rank Algorithm (slide) http://www.cs.sjsu.edu/faculty/pollett/masters/Semesters/Fall11/tanmayee/Deliverable3.pdf

1 thought on “PageRank Algorithm

Leave a Reply

Your email address will not be published. Required fields are marked *