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

PageRank แบบถ่วงน้ำหนัก

ผู้เสนอ
Xing, W. & Ghorbani, A.
ปี
2004
ประเภท
Centrality measure / ranking algorithm
กลุ่มวิธี
Network science

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

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

ใช้ทำอะไร?

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

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

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

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

PageRank ถูกนำเสนอโดย Brin และ Page ในปี 1998 เป็นรากฐานของ Google Search โดยพิจารณาการเชื่อมโยงทุกรูปแบบเท่ากัน Weighted PageRank ถูกทำให้เป็นทางการโดย Xing และ Ghorbani ในปี 2004 โดยขยายอัลกอริทึมเพื่อกำหนดการกระจายอันดับตามสัดส่วนของน้ำหนักเส้นเชื่อม โดยอาศัยเศษส่วนน้ำหนักขาเข้าและขาออก ตั้งแต่นั้นมาก็ถูกนำไปใช้ในการวิเคราะห์การอ้างอิง ชีวสารสนเทศ การวิเคราะห์เครือข่ายสังคม และระบบแนะนำทุกที่ที่ความแข็งแรงของการเชื่อมโยงเป็นตัวบ่งชี้อิทธิพลที่มีความหมาย

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

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

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

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

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

จุดแข็ง

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

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

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

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

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

1

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

2

สำหรับเส้นเชื่อมแบบมีทิศทางแต่ละเส้นจากโหนด v ไปยังโหนด u ให้คำนวณปัจจัยน้ำหนักสองค่า: ปัจจัยน้ำหนักขาเข้า (in-weight factor) ที่ปรับน้ำหนักเส้นเชื่อมตามน้ำหนักขาเข้าทั้งหมดของ u และปัจจัยน้ำหนักขาออก (out-weight factor) ที่ปรับน้ำหนักเส้นเชื่อมตามน้ำหนักขาออกทั้งหมดของ v เศษส่วนเหล่านี้จะเป็นตัวกำหนดว่าอันดับของ v จะถูกกระจายไปยัง u ผ่านเส้นเชื่อมเฉพาะนี้มากน้อยเพียงใด

สูตร
W_{in}(v,u) = \frac{w(v,u)}{\sum_{k \in In(u)} w(k,u)}, \quad W_{out}(v,u) = \frac{w(v,u)}{\sum_{k \in Out(v)} w(v,k)}
3

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

สูตร
WPR(u) = (1-d) + d \sum_{v \in In(u)} WPR(v) \cdot W_{in}(v,u) \cdot W_{out}(v,u)
4

ทำซ้ำการปรับปรุงอันดับจนกว่าการเปลี่ยนแปลงคะแนนของทุกโหนดจะต่ำกว่าค่าความคลาดเคลื่อนเล็กน้อย (โดยทั่วไปคือ 1e-6) การลู่เข้าจะรับประกันสำหรับกราฟที่เชื่อมต่อกันอย่างแข็งแกร่ง สำหรับกราฟที่มีโหนดที่ไม่มีเส้นเชื่อมขาออก (dangling nodes) หรือส่วนประกอบที่แยกจากกัน ให้ใช้การแก้ไขปัญหาโหนดที่ไม่มีเส้นเชื่อมขาออกตามมาตรฐานก่อนทำการวนซ้ำ

5

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

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

  • การใช้น้ำหนักเส้นเชื่อมดิบที่ไม่ได้ปรับมาตรฐานโดยไม่ได้ตรวจสอบสเกล — การผสมผสานจำนวนหลักสิบกับค่าหลักล้านจะทำให้การแพร่กระจายอันดับผิดเพี้ยน
  • การลืมจัดการกับโหนดที่ไม่มีเส้นเชื่อมขาออก (dangling nodes) ซึ่งอาจทำให้คะแนนอันดับรั่วไหลออกจากเครือข่ายทั้งหมดหากไม่ได้รับการแก้ไข
  • การสันนิษฐานว่าปัจจัยลดทอนเริ่มต้นที่ 0.85 เหมาะสมกับทุกกรณี ในเครือข่ายการอ้างอิงหรือเครือข่ายชีววิทยา ค่าอื่นอาจสะท้อนถึงโดเมนได้ดีกว่า
  • การตีความคะแนน Weighted PageRank เป็นความน่าจะเป็นสัมบูรณ์แทนที่จะเป็นการจัดอันดับสัมพัทธ์ — มีเพียงลำดับเท่านั้นที่คงที่ตลอดการทำงานที่แตกต่างกัน
  • การเปรียบเทียบคะแนน Weighted PageRank ข้ามเครือข่ายที่มีขนาดต่างกันโดยไม่มีการปรับมาตรฐาน

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

Weighted PageRank แตกต่างจาก PageRank มาตรฐานอย่างไร

PageRank มาตรฐานกระจายอันดับของโหนดอย่างเท่าเทียมกันไปยังเพื่อนบ้านขาออกทั้งหมดโดยไม่คำนึงถึงความแข็งแรงของเส้นเชื่อม Weighted PageRank ปรับการกระจายนี้ตามน้ำหนักขาเข้าและขาออกสัมพัทธ์ของแต่ละเส้นเชื่อม ดังนั้นการเชื่อมต่อที่แข็งแกร่งกว่าจึงมีอันดับเป็นสัดส่วนมากขึ้น

ควรใช้ปัจจัยลดทอนเท่าใด

ค่ามาตรฐานคือ 0.85 ซึ่งได้มาจากการสันนิษฐานเกี่ยวกับเครือข่ายเว็บเกี่ยวกับการท่องแบบสุ่ม สำหรับเครือข่ายสังคม ชีววิทยา หรือการอ้างอิง มีการสำรวจค่าระหว่าง 0.5 ถึง 0.9 ในวรรณกรรม แนะนำให้ทำการวิเคราะห์ความไวต่อค่าลดทอนหลายค่า

สามารถใช้ Weighted PageRank กับเครือข่ายที่ไม่มีทิศทางได้หรือไม่

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

จะจัดการกับเส้นเชื่อมที่มีน้ำหนักเป็นศูนย์ได้อย่างไร

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

Weighted PageRank ดีกว่า weighted degree centrality หรือไม่

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

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

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

  1. Xing, W., & Ghorbani, A. (2004). Weighted PageRank algorithm. Proceedings of the Second Annual Conference on Communication Networks and Services Research (CNSR '04), pp. 305–314. IEEE.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. PageRank. Wikipedia.

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