ความเป็นศูนย์กลางแบบคั่นกลางที่ถ่วงน้ำหนัก (Weighted Betweenness Centrality)
- ผู้เสนอ
- Opsahl, T.; Agneessens, F.; Skvoretz, J. (extending Freeman 1977 and Brandes 2001)
- ปี
- 2010
- ประเภท
- Centrality measure (path-based)
- กลุ่มวิธี
- Network science
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Weighted Betweenness Centrality ขยายการวัดค่า betweenness ของ Freeman ไปยังกราฟที่มีน้ำหนักขอบ โดยการกำหนดเส้นทางที่สั้นที่สุดผ่านการแปลงน้ำหนักขอบที่ปรับแต่งได้ โหนดที่อยู่บนเส้นทางที่สั้นที่สุดซึ่งมีความสำคัญสูงจำนวนมากจะได้รับคะแนนสูง ซึ่งระบุถึงตัวกลางและสะพานเชื่อมในเครือข่ายสังคม ชีวภาพ และข้อมูลที่ความแข็งแรงของความสัมพันธ์มีความสำคัญ
แนวคิดเบื้องหลังวิธีการ
ลองจินตนาการถึงเมืองที่มีถนนที่มีความจุการจราจรแตกต่างกัน ทางแยกที่สำคัญที่สุดไม่ใช่แค่ทางแยกที่มีถนนหลายสายเท่านั้น แต่เป็นทางแยกที่อยู่บนเส้นทางที่เร็วที่สุดหรือมีความจุสูงสุดระหว่างสถานที่หลายคู่ Weighted betweenness centrality จับภาพสิ่งนี้ได้อย่างแม่นยำ: มันค้นหาโหนดที่ทำหน้าที่เป็นจุดถ่ายทอดที่สำคัญ โดยคำนึงถึงความเหนียวแน่นหรือความอ่อนแอของการเชื่อมต่อที่ผ่านโหนดเหล่านั้น โหนดที่มีค่า weighted betweenness สูงเป็นสะพานหรือผู้เฝ้าประตูที่การถอดออกจะขัดขวางเส้นทางที่สำคัญหลายเส้นทาง
ประวัติศาสตร์
Betweenness centrality ถูกนำเสนอโดย Linton Freeman ในปี 1977 เพื่อเป็นมาตรวัดบทบาทของโหนดในการเชื่อมต่อผู้อื่นผ่านเส้นทางที่สั้นที่สุด Ulrik Brandes ได้พัฒนาอัลกอริทึมที่มีประสิทธิภาพที่สำคัญในปี 2001 ซึ่งลดการคำนวณจาก O(n^3) เป็น O(n + m) สำหรับกราฟที่ไม่มีน้ำหนัก การขยายแบบถ่วงน้ำหนักได้รับการจัดรูปแบบอย่างเป็นระบบโดย Opsahl, Agneessens, และ Skvoretz ในปี 2010 ซึ่งเสนอการแปลงน้ำหนักเป็นระยะทางแบบพารามิเตอร์ alpha และตรวจสอบความถูกต้องกับเครือข่ายความร่วมมือและสายการบินเชิงประจักษ์
ควรใช้เมื่อใด
ใช้ weighted betweenness centrality เมื่อน้ำหนักขอบแสดงถึงความแข็งแรงของความสัมพันธ์ที่มีความหมาย (ความถี่ของการติดต่อ, ปริมาณการไหล, ความเข้มข้นของการทำงานร่วมกัน, ความคล้ายคลึงกัน) และคุณต้องการระบุตัวกลาง, ผู้เฝ้าประตู, หรือจุดเดียวที่ล้มเหลวในเครือข่าย เหมาะสำหรับเครือข่ายสังคม, เครือข่ายความร่วมมือ, โครงข่ายการขนส่ง, และเส้นทางชีวภาพที่ความแข็งแรงของการเชื่อมต่อกำหนดว่าเส้นทางใดถูกใช้จริง หลีกเลี่ยงเมื่อน้ำหนักขอบมีสัญญาณรบกวนหรือเป็นไปตามอำเภอใจ — ในกรณีนั้น plain betweenness centrality จะปลอดภัยกว่า นอกจากนี้ยังหลีกเลี่ยงสำหรับเครือข่ายขนาดใหญ่มาก (หลายล้านโหนด) ที่ไม่มีอัลกอริทึมประมาณค่า เนื่องจาก exact computation คือ O(n^3) ในกรณีที่เลวร้ายที่สุด
ข้อจำกัดและข้อควรพิจารณา
- การคำนวณที่แม่นยำคือ O(n^3) ในพื้นที่และเวลาสำหรับกราฟหนาแน่น ซึ่งจำกัดความสามารถในการปรับขนาดสำหรับเครือข่ายขนาดใหญ่มาก
- ผลลัพธ์มีความไวต่อการเลือก alpha; ค่าที่แตกต่างกันสามารถเปลี่ยนแปลงการจัดอันดับของโหนดได้อย่างมาก
- สมมติว่าข้อมูลหรืออิทธิพลไหลไปตามเส้นทางที่สั้นที่สุดเท่านั้น ซึ่งอาจไม่สะท้อนกระบวนการแพร่กระจายจริง
- น้ำหนักขอบที่เป็นลบหรือศูนย์ต้องได้รับการจัดการเป็นพิเศษและสามารถทำให้เกิดข้อผิดพลาดในอัลกอริทึมเส้นทางที่สั้นที่สุดได้
- เครือข่ายที่ไม่เชื่อมต่อกันจะสร้างค่า betweenness ที่ไม่สามารถกำหนดได้สำหรับคู่ในส่วนประกอบที่แตกต่างกัน ซึ่งต้องมีการวิเคราะห์ระดับส่วนประกอบ
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- จับภาพการเป็นตัวกลางและการควบคุมในเครือข่ายที่ความแข็งแรงของความสัมพันธ์กำหนดว่าเส้นทางใดเป็นที่ต้องการ
- พารามิเตอร์ปรับแต่ง alpha ช่วยให้นักวิเคราะห์สามารถผสมผสานตรรกะเส้นทางแบบไม่ถ่วงน้ำหนักและแบบถ่วงน้ำหนักเต็มที่ ทำให้การวัดสามารถปรับเปลี่ยนได้
- ระบุโหนดที่เป็นคอขวดโดยตรงที่การถอดออกจะทำให้เครือข่ายแตกแยกหรือช้าลง
- เข้ากันได้กับอัลกอริทึมที่มีประสิทธิภาพของ Brandes ทำให้การคำนวณเป็นไปได้สำหรับเครือข่ายที่มีโหนดหลายหมื่นโหนด
- คะแนนที่ถูกทำให้เป็นมาตรฐานสามารถตีความได้ในเครือข่ายที่มีขนาดต่างกัน
- มีพื้นฐานที่มั่นคงในกรอบการทำงานการสรุปผลที่ผ่านการตรวจสอบโดยผู้ทรงคุณวุฒิ (Opsahl et al. 2010) พร้อมการอ้างอิงที่กว้างขวาง
การประยุกต์ใช้
- การระบุผู้ประสานงานความรู้และผู้เชื่อมโยงขอบเขตในเครือข่ายองค์กรและความร่วมมือ
- การค้นหาโหนดถ่ายทอดที่สำคัญในเครือข่ายการสื่อสารหรือห่วงโซ่อุปทานสำหรับการวิเคราะห์ความยืดหยุ่น
- การค้นหาสนามบินศูนย์กลางหรือสถานีขนส่งที่รองรับการจราจรระหว่างเมืองมากที่สุดในเครือข่ายการขนส่ง
- การตรวจจับคอขวดด้านกฎระเบียบในเครือข่ายปฏิสัมพันธ์โปรตีนหรือเครือข่ายควบคุมยีน
- การระบุผู้แพร่กระจายที่มีอิทธิพลในแบบจำลองการแพร่ระบาดหรือการแพร่กระจายข้อมูลแบบถ่วงน้ำหนัก
- การวิเคราะห์การเป็นตัวกลางระดับชุมชนในเครือข่ายการเขียนร่วมและการอ้างอิงแบบถ่วงน้ำหนัก
วิธีการทำงาน
วิธีการทำงาน
น้ำหนักขอบจะถูกแปลงเป็นระยะทางโดยใช้การแปลงผกผันที่ควบคุมโดยพารามิเตอร์ปรับแต่ง alpha เมื่อ alpha เท่ากับศูนย์ การวัดจะลดลงเป็น standard unweighted betweenness; เมื่อ alpha เพิ่มขึ้นเข้าใกล้หนึ่ง ความสัมพันธ์ที่เหนียวแน่นจะถูกมองว่าสั้นกว่าและเป็นเส้นทางที่ต้องการ ทำให้การวัดมีความไวต่อความแข็งแรงของความสัมพันธ์
สูตร
d_{ij} = w_{ij}^{-\alpha}, \; \alpha \in [0,1]อัลกอริทึมของ Dijkstra (หรือ Brandes' linear-algebra variant เพื่อประสิทธิภาพ) จะคำนวณชุดของเส้นทางที่สั้นที่สุดที่มีน้ำหนักระหว่างโหนดต้นทางและปลายทางทุกคู่ในเครือข่าย โดยใช้ระยะทางที่แปลงแล้ว ขั้นตอนนี้ระบุว่าเส้นทางใดเป็นเส้นทางสั้นที่สุด (geodesic) อย่างแท้จริงเมื่อพิจารณาการกำหนดค่าน้ำหนัก
สำหรับโหนดทุกคู่ที่มีลำดับ อัลกอริทึมจะนับจำนวนรวมของเส้นทางที่สั้นที่สุดที่มีน้ำหนักและชุดย่อยของเส้นทางเหล่านั้นที่ผ่านโหนด v แต่ละโหนด การนับเหล่านี้จะถูกสะสมอย่างมีประสิทธิภาพโดยใช้เทคนิค back-propagation ของ Brandes ทำให้การทำงานของอัลกอริทึมสามารถจัดการได้สำหรับเครือข่ายขนาดปานกลาง
สำหรับแต่ละโหนด v คะแนน betweenness ดิบคือผลรวมของเศษส่วนของเส้นทางที่สั้นที่สุดที่ผ่าน v สำหรับทุกคู่ต้นทาง-ปลายทาง โหนดที่อยู่บนเส้นทางที่สั้นที่สุดทั้งหมดระหว่างคู่หนึ่งจะให้คะแนน 1.0 แก่คะแนนของมันสำหรับคู่นั้น; โหนดที่ถูกข้ามโดยเส้นทางทั้งหมดจะให้คะแนน 0
สูตร
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}คะแนนดิบจะถูกหารด้วยค่าสูงสุดที่เป็นไปได้ — ซึ่งคือ (n-1)(n-2)/2 สำหรับเครือข่ายที่ไม่มีทิศทาง — เพื่อให้คะแนนอยู่ในช่วง [0, 1] และสามารถเปรียบเทียบได้ในเครือข่ายที่มีขนาดต่างกัน สำหรับเครือข่ายที่มีทิศทาง ตัวหารจะเพิ่มเป็นสองเท่าเป็น (n-1)(n-2)
สูตร
C_B^{\text{norm}}(v) = \frac{C_B(v)}{(n-1)(n-2)/2}ข้อผิดพลาดที่พบบ่อย
- การใช้ alpha เริ่มต้นโดยไม่มีการรายงานหรือให้เหตุผลสำหรับค่าของมัน — ควรระบุและให้เหตุผลในการเลือก alpha ของคุณเสมอ
- การถือว่าคะแนนดิบ (ที่ยังไม่ถูกทำให้เป็นมาตรฐาน) เปรียบเทียบกันได้ในเครือข่ายที่มีขนาดต่างกัน
- การละเลยทิศทางของขอบในเครือข่ายที่มีทิศทางและการคำนวณ betweenness แบบไม่มีทิศทางแทน
- การตีความ betweenness สูงว่ามีอิทธิพลสูงโดยไม่พิจารณาว่าการไหลเป็นไปตามเส้นทางที่สั้นที่สุดในโดเมนจริงหรือไม่
- การลืมตรวจสอบส่วนประกอบที่ไม่เชื่อมต่อกัน ซึ่งทำให้คะแนน betweenness สำหรับโหนดในส่วนประกอบที่เล็กกว่าต่ำกว่าความเป็นจริงโดยเทียม
คำถามที่พบบ่อย
ฉันจะเลือกพารามิเตอร์ alpha ได้อย่างไร?
Alpha ควบคุมว่าน้ำหนักมีอิทธิพลต่อการเลือกเส้นทางมากน้อยเพียงใด ที่ alpha=0 คุณจะได้ betweenness แบบไม่ถ่วงน้ำหนักแบบคลาสสิก; ที่ alpha=1 ความสัมพันธ์ที่เหนียวแน่น (strong ties) จะกำหนดเส้นทางที่สั้นที่สุดอย่างสมบูรณ์ การปฏิบัติทั่วไปคือการทดสอบ alpha=0, 0.5, และ 1 และรายงานความไว หากการจัดอันดับโหนดมีความเสถียรในค่าต่างๆ การเลือกใดๆ ก็สามารถป้องกันได้; หากแตกต่างกันอย่างมาก ให้ให้เหตุผลในการเลือกของคุณตามทฤษฎีว่าความสัมพันธ์ที่เหนียวแน่นควรเป็นที่ต้องการหรือไม่
ความแตกต่างระหว่าง weighted และ unweighted betweenness centrality คืออะไร?
Unweighted betweenness นับจำนวนการกระโดด; ทุกขอบมีความยาวเท่ากัน Weighted betweenness ใช้น้ำหนักขอบ (แปลงเป็นระยะทาง) เพื่อให้เส้นทางเป็นไปตามการเชื่อมต่อที่เหนียวแน่นกว่าหรือสั้นกว่า ในเครือข่ายที่ความแข็งแรงของความสัมพันธ์มีความหมายอย่างมาก — เช่น ความถี่ของการทำงานร่วมกันหรือปริมาณการค้า — เวอร์ชันถ่วงน้ำหนักจะให้ภาพที่แม่นยำยิ่งขึ้นว่าโหนดใดควบคุมการไหลจริง
weighted betweenness centrality เหมาะสำหรับเครือข่ายขนาดใหญ่มากหรือไม่?
การคำนวณที่แม่นยำมีค่าใช้จ่ายสูงเมื่อมีโหนดเกินประมาณ 100,000 โหนด สำหรับเครือข่ายขนาดใหญ่มาก ให้ใช้อัลกอริทึมประมาณค่า เช่น random-pivot sampling (นำไปใช้ใน NetworkX เป็น betweenness_centrality ด้วยพารามิเตอร์ k) หรือใช้เครื่องมือที่เร่งด้วย GPU เช่น cuGraph รายงานว่าคุณใช้การคำนวณที่แม่นยำหรือประมาณค่า
ฉันสามารถใช้ weighted betweenness ได้หรือไม่เมื่อเครือข่ายของฉันมีโหนดที่แยกตัวหรือมีส่วนประกอบหลายส่วน?
ได้ แต่โหนดที่แยกตัวจะมีคะแนนเป็นศูนย์เสมอ และโหนดในส่วนประกอบขนาดเล็กจะมีคะแนนตามเส้นทางภายในส่วนประกอบของตนเท่านั้น คำนวณ betweenness แยกกันต่อส่วนประกอบหากคุณต้องการการจัดอันดับภายในส่วนประกอบ และรายงานโครงสร้างส่วนประกอบพร้อมกับคะแนน
ฉันควรรายงาน weighted betweenness centrality ในต้นฉบับอย่างไร?
รายงานซอฟต์แวร์และเวอร์ชันที่ใช้ (เช่น NetworkX, igraph), ค่าของ alpha, ว่าคะแนนถูกทำให้เป็นมาตรฐานหรือไม่, วิธีที่คุณจัดการส่วนประกอบที่ไม่เชื่อมต่อกัน, และสถิติสรุป (ค่าเฉลี่ย, ช่วง) พร้อมกับโหนดที่ได้รับการจัดอันดับสูงสุด แผนภาพการกระจายระหว่างระดับกับ betweenness หรือการแสดงภาพเครือข่ายที่มีขนาดโหนดเป็นสัดส่วนกับคะแนนช่วยในการตีความ
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Opsahl, T., Agneessens, F., & Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks, 32(3), 245–251.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วBrandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163–177.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว