Skip to content
กลับไปยังผลการค้นหา

PageRank Centrality

ผู้เสนอ
Page, Brin, Motwani & Winograd
ปี
1999
ประเภท
Iterative link-based centrality algorithm
กลุ่มวิธี
Centrality

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

PageRank เป็นอัลกอริทึมการวัดความสำคัญของโหนด (node) ในกราฟแบบมีทิศทาง (directed graph) โดยอาศัยการเชื่อมโยง (link-based) ซึ่งจะกำหนดคะแนนความสำคัญให้กับแต่ละโหนด โดยวัดจากจำนวนโหนดคุณภาพสูงที่ชี้มายังโหนดนั้น อัลกอริทึมนี้ถูกพัฒนาขึ้นโดย Larry Page, Sergey Brin, Rajeev Motwani และ Terry Winograd ที่มหาวิทยาลัยสแตนฟอร์ดในปี 1999 และได้กลายเป็นรากฐานทางคณิตศาสตร์ของเครื่องมือค้นหา Google และยังคงเป็นหนึ่งในอัลกอริทึมที่มีอิทธิพลมากที่สุดในวิทยาการเครือข่าย (network science) และการค้นคืนสารสนเทศ (information retrieval).

แนวคิดเบื้องหลังวิธีการ

ลองจินตนาการถึงผู้ท่องเว็บแบบสุ่ม (random web surfer) ที่คลิกลิงก์ไปเรื่อยๆ แบบสุ่ม และบางครั้งก็กระโดดไปยังหน้าเว็บแบบสุ่มโดยสิ้นเชิง แทนที่จะตามลิงก์ไปเรื่อยๆ สัดส่วนของเวลาที่นักท่องเว็บคนนี้ใช้ในแต่ละหน้า หลังจากคลิกไปเรื่อยๆ เป็นจำนวนอนันต์ คือ PageRank ของหน้านั้นๆ หน้าเว็บที่ถูกเข้าชมบ่อยๆ – เพราะมีหน้าเว็บยอดนิยมจำนวนมากเชื่อมโยงมา – จะได้รับคะแนนสูง ปัจจัยการลดทอน (damping factor) (โดยทั่วไปคือ 0.85) เป็นแบบจำลองความน่าจะเป็นของการคลิกต่อไปเรื่อยๆ แทนที่จะกระโดดไปหน้าอื่น.

ประวัติศาสตร์

PageRank ได้รับการพัฒนาที่มหาวิทยาลัยสแตนฟอร์ดโดย Larry Page และ Sergey Brin ในฐานะกลไกการจัดอันดับหลักของโครงการ BackRub ซึ่งต่อมากลายเป็น Google ในปี 1998 รายงานทางเทคนิคที่เป็นรากฐาน ซึ่งเขียนร่วมกับ Rajeev Motwani และ Terry Winograd ได้รับการตีพิมพ์ในปี 1999 อัลกอริทึมนี้ทำให้การใช้การวัดความสำคัญแบบ eigenvector centrality ในเครือข่ายแบบมีทิศทางขนาดใหญ่เป็นที่นิยม และเป็นแรงบันดาลใจโดยตรงให้กับอัลกอริทึมการวิเคราะห์ลิงก์ในภายหลัง รวมถึง HITS และ TrustRank.

ควรใช้เมื่อใด

PageRank เหมาะสมเมื่อคุณต้องการจัดอันดับโหนดในกราฟแบบมีทิศทางตามความสำคัญเชิงโครงสร้างโดยรวม โดยเฉพาะอย่างยิ่งเมื่อทิศทางของเส้นเชื่อมแสดงถึงการยอมรับ (endorsement) หรืออิทธิพล (เช่น ไฮเปอร์ลิงก์, การอ้างอิง, การติดตามในโซเชียลมีเดีย) อัลกอริทึมนี้ตั้งสมมติฐานว่ากราฟสามารถจำลองได้ว่าเป็นมาร์คอฟเชน (Markov chain) และต้องการส่วนประกอบที่เชื่อมโยงกัน (connected) หรือเชื่อมโยงกันอย่างเข้มแข็ง (strongly connected) เพื่อให้การลู่เข้าเป็นไปอย่างถูกต้อง อัลกอริทึมนี้ไม่เหมาะสำหรับเครือข่ายที่ไม่มีทิศทาง (undirected networks) ซึ่งอาจพิจารณาใช้วิธี HITS หรือ betweenness centrality แทน และอาจไวต่อการสแปมลิงก์หรือการเพิ่มจำนวนลิงก์เข้า (in-degree) อย่างจงใจ.

ข้อจำกัดและข้อควรพิจารณา

  • ต้องการกราฟแบบมีทิศทาง การนำไปใช้กับเครือข่ายที่ไม่มีทิศทางต้องมีการเลือกรูปแบบการแปลง
  • ความเร็วในการลู่เข้าขึ้นอยู่กับค่า spectral gap ของเมทริกซ์การเปลี่ยนสถานะ และอาจช้าสำหรับกราฟที่เชื่อมโยงกันไม่ดี
  • ไวต่อการเลือกค่า damping factor d ค่าที่แตกต่างกันอาจส่งผลต่อการจัดอันดับอย่างมาก
  • เสี่ยงต่อการถูกจัดการโดยฟาร์มลิงก์ (link-farm) และลิงก์เข้าที่สร้างขึ้นอย่างจงใจ

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • มีรากฐานทางความน่าจะเป็นที่เป็นหลักการผ่านแบบจำลองมาร์คอฟเชนของผู้ท่องเว็บแบบสุ่ม
  • สามารถปรับขนาดให้รองรับกราฟขนาดใหญ่มากได้ด้วยการคูณเมทริกซ์แบบเบาบาง (sparse matrix-vector products) และการวนซ้ำแบบกำลัง (power iteration)
  • จับภาพโครงสร้างโทโพโลยีของกราฟโดยรวม ให้รางวัลแก่โหนดที่ได้รับการยอมรับจากโหนดคะแนนสูงอื่นๆ
  • ได้รับการตรวจสอบความถูกต้องอย่างกว้างขวางในโดเมนเว็บ, การอ้างอิง, ชีววิทยา และเครือข่ายสังคม

การประยุกต์ใช้

  • การจัดอันดับเครื่องมือค้นหาบนเว็บ: การเรียงลำดับผลการค้นหาตามความน่าเชื่อถือโดยรวมของหน้าเว็บ
  • การวิเคราะห์การอ้างอิงทางวิชาการ: การระบุบทความหรือวารสารที่มีอิทธิพลในเครือข่ายวรรณกรรมทางวิทยาศาสตร์
  • การวัดอิทธิพลในเครือข่ายสังคม: การจัดอันดับผู้ใช้ตามความมีชื่อเสียงของผู้ติดตาม
  • การวิเคราะห์เครือข่ายชีวภาพ: การค้นหาโปรตีนหรือยีนที่เป็นศูนย์กลาง (hub) ในเครือข่ายปฏิสัมพันธ์โปรตีนและเครือข่ายการควบคุมยีน
  • ระบบแนะนำ: การกระจายสัญญาณความชอบผ่านกราฟสองส่วน (bipartite graphs) ของผู้ใช้และรายการ

วิธีการทำงาน

วิธีการทำงาน

1

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

สูตร
PR^{(0)}(v_i) = \frac{1}{N}, \quad \forall\, i \in \{1, \ldots, N\}
2

เมทริกซ์การเปลี่ยนสถานะแบบคอลัมน์สโตแคสติก (column-stochastic transition matrix) M ถูกสร้างขึ้นจากโครงสร้างการเชื่อมโยงของกราฟ ค่าในแต่ละช่อง M_ij จะเท่ากับ 1 หารด้วยจำนวนเส้นเชื่อมออก (out-degree) ของโหนด j หากมีเส้นเชื่อมจาก j ไป i และเป็นศูนย์ในกรณีอื่น โหนดที่ไม่มีเส้นเชื่อมออก (dangling nodes) มักจะถูกจัดการโดยการกระจายคะแนนของโหนดเหล่านั้นอย่างสม่ำเสมอไปยังทุกโหนด.

สูตร
M_{ij} = \begin{cases} \frac{1}{\text{out}(v_j)} & \text{if } (v_j \to v_i) \in E \\ 0 & \text{otherwise} \end{cases}
3

เวกเตอร์ PageRank จะถูกปรับปรุงแบบวนซ้ำโดยใช้สูตรผู้ท่องเว็บแบบสุ่ม ด้วยปัจจัยการลดทอน d (ค่าเริ่มต้น 0.85) แต่ละโหนดจะได้รับความน่าจะเป็นพื้นฐานในการเทเลพอร์ต (teleportation probability) (1-d)/N บวกกับ d คูณกับผลรวมถ่วงน้ำหนักของคะแนนที่มาจากโหนดทั้งหมดที่เชื่อมโยงมายังโหนดนั้น ขั้นตอนนี้จะทำซ้ำไปเรื่อยๆ จนกว่าคะแนนจะคงที่.

สูตร
PR^{(t+1)}(v_i) = \frac{1-d}{N} + d \sum_{v_j \in \mathcal{B}(v_i)} \frac{PR^{(t)}(v_j)}{\text{out}(v_j)}
4

หลังจากการวนซ้ำแต่ละครั้ง ค่า L1 norm ของการเปลี่ยนแปลงในเวกเตอร์คะแนนจะถูกเปรียบเทียบกับค่าความคลาดเคลื่อนเล็กน้อย epsilon (เช่น 1e-6) เมื่อการเปลี่ยนแปลงลดลงต่ำกว่าเกณฑ์นี้ อัลกอริทึมจะลู่เข้า (converged) และเวกเตอร์คะแนนปัจจุบันจะถูกส่งคืนเป็นผลการกระจาย PageRank สุดท้าย.

สูตร
\left\| PR^{(t+1)} - PR^{(t)} \right\|_1 < \varepsilon

ข้อผิดพลาดที่พบบ่อย

  • การละเลยโหนดที่ไม่มีเส้นเชื่อมออก (dangling nodes) อาจทำให้คุณสมบัติสโตแคสติกของเมทริกซ์การเปลี่ยนสถานะเสียไปและทำให้คะแนนไม่ถูกต้อง
  • การใช้ PageRank กับกราฟที่ไม่มีทิศทางโดยไม่แปลงเป็นแบบจำลองเมทริกซ์สมมาตรอาจให้ค่าการวัดความสำคัญที่ทำให้เข้าใจผิดได้
  • การตั้งค่า tolerance หลวมเกินไปนำไปสู่การลู่เข้าก่อนกำหนด; แน่นเกินไปจะเพิ่มการคำนวณโดยไม่มีการเปลี่ยนแปลงคะแนนที่มีนัยสำคัญ
  • การตีความ PageRank เป็นการวัดความสำคัญสัมบูรณ์ แทนที่จะเป็นการจัดอันดับสัมพัทธ์ภายในบริบทของกราฟที่เฉพาะเจาะจง

คำถามที่พบบ่อย

ปัจจัยการลดทอน d แสดงถึงอะไร และควรเลือกอย่างไร?

ปัจจัยการลดทอน d (โดยทั่วไปคือ 0.85) คือความน่าจะเป็นที่นักท่องเว็บแบบสุ่มจะตามลิงก์ แทนที่จะเทเลพอร์ตไปยังโหนดแบบสุ่ม ค่าที่ใกล้เคียง 1 ทำให้อัลกอริทึมไวต่อโครงสร้างกราฟมากขึ้น แต่ลู่เข้าช้าลงและมีแนวโน้มที่จะเกิด rank sinks (โหนดที่คะแนนเพิ่มขึ้นเรื่อยๆ โดยไม่มีที่สิ้นสุด) มากขึ้น ค่าที่ใกล้เคียง 0 จะเข้าใกล้การจัดอันดับแบบสม่ำเสมอ ค่า 0.85 ได้รับการตรวจสอบเชิงประจักษ์โดย Page และ Brin สำหรับกราฟเว็บ และเป็นค่าเริ่มต้นมาตรฐาน.

PageRank แตกต่างจาก degree centrality อย่างไร?

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

PageRank สามารถนำไปใช้กับกราฟที่ไม่มีทิศทางได้หรือไม่?

ได้ แต่มีข้อควรพิจารณา กราฟที่ไม่มีทิศทางจะต้องถูกแปลงเป็นรูปแบบที่มีทิศทาง โดยการแทนที่แต่ละเส้นเชื่อมที่ไม่มีทิศทางด้วยเส้นเชื่อมที่มีทิศทางสองเส้น ผลลัพธ์ PageRank ที่ได้จะเป็นฟังก์ชันของ degree ของโหนด ซึ่งทำให้อัลกอริทึมกลายเป็น weighted degree centrality สำหรับเครือข่ายที่ไม่มีทิศทาง การวัดความสำคัญอื่นๆ เช่น eigenvector centrality หรือ betweenness centrality มักจะให้ข้อมูลมากกว่า.

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว