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) ช่วยให้การใช้หน่วยความจำอยู่ในขอบเขตที่จัดการได้
- ตีความได้ง่าย: คะแนนสูงหมายถึงโหนดได้รับการสนับสนุนที่มีน้ำหนักมากจากโหนดคะแนนสูงอื่นๆ
การประยุกต์ใช้
- การระบุเอกสารหรือผู้เขียนที่มีอิทธิพลในเครือข่ายการอ้างอิงและการเป็นผู้เขียนร่วมที่มีน้ำหนัก
- การจัดอันดับหน้าเว็บหรือเอกสารเมื่อมีปริมาณการเข้าชมการเชื่อมโยงหรืออัตราการคลิก
- การตรวจจับโปรตีนหรือยีนที่สำคัญในเครือข่ายการโต้ตอบทางชีววิทยาที่มีน้ำหนัก
- การจัดลำดับความสำคัญของโหนดในเครือข่ายธุรกรรมทางการเงินตามปริมาณการไหลของธุรกรรม
- การจัดอันดับผู้ใช้หรือเนื้อหาในกราฟการโต้ตอบโซเชียลมีเดียที่มีน้ำหนัก
- การสร้างระบบแนะนำที่ความถี่ของการปรากฏร่วมกันของรายการทำหน้าที่เป็นน้ำหนักเส้นเชื่อม
วิธีการทำงาน
วิธีการทำงาน
แสดงเครือข่ายเป็นกราฟที่เส้นเชื่อมแต่ละเส้นมีน้ำหนักเชิงตัวเลขสะท้อนความแข็งแรงของความสัมพันธ์ เช่น ความถี่ของการโต้ตอบ ปริมาณธุรกรรม จำนวนการเป็นผู้เขียนร่วม หรือคะแนนความคล้ายคลึง อัลกอริทึมต้องการให้น้ำหนักเหล่านี้ไม่เป็นลบ น้ำหนักที่เป็นลบจะต้องถูกแปลงก่อนการวิเคราะห์
สำหรับเส้นเชื่อมแบบมีทิศทางแต่ละเส้นจากโหนด 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)}ใช้วิธีการคำนวณสูตร 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)ทำซ้ำการปรับปรุงอันดับจนกว่าการเปลี่ยนแปลงคะแนนของทุกโหนดจะต่ำกว่าค่าความคลาดเคลื่อนเล็กน้อย (โดยทั่วไปคือ 1e-6) การลู่เข้าจะรับประกันสำหรับกราฟที่เชื่อมต่อกันอย่างแข็งแกร่ง สำหรับกราฟที่มีโหนดที่ไม่มีเส้นเชื่อมขาออก (dangling nodes) หรือส่วนประกอบที่แยกจากกัน ให้ใช้การแก้ไขปัญหาโหนดที่ไม่มีเส้นเชื่อมขาออกตามมาตรฐานก่อนทำการวนซ้ำ
เมื่อคะแนนลู่เข้าแล้ว ให้จัดเรียงโหนดทั้งหมดตามคะแนน 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 สำหรับความสำคัญทั่วทั้งเครือข่าย
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
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คัดลอกแล้วPageRank. Wikipedia.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว