ค่ากลางแบบวัดความใกล้ชิดถ่วงน้ำหนัก
- ผู้เสนอ
- Opsahl, T.; Agneessens, F.; Skvoretz, J.
- ปี
- 2010
- ประเภท
- Centrality measure (network analysis)
- กลุ่มวิธี
- Network science
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
ค่ากลางแบบวัดความใกล้ชิดถ่วงน้ำหนักเป็นการขยายการวัดความใกล้ชิดแบบคลาสสิกไปยังเครือข่ายที่เส้นเชื่อมมีน้ำหนักเชิงตัวเลข เช่น ความถี่ ความแข็งแรง หรือต้นทุน โดยการรวมน้ำหนักเหล่านั้นเข้ากับการวัดระยะทางของเส้นทางที่สั้นที่สุด โหนดที่สามารถเข้าถึงโหนดอื่นได้อย่างรวดเร็วผ่านการเชื่อมต่อที่แข็งแรงหรือมีประสิทธิภาพจะได้รับคะแนนสูง ทำให้เป็นตัวบ่งชี้ศักยภาพในการแพร่กระจายข้อมูลที่สมบูรณ์กว่าแบบคู่ตรงข้ามที่เป็นไบนารี
แนวคิดเบื้องหลังวิธีการ
ในเครือข่ายที่ไม่มีน้ำหนัก ค่ากลางแบบวัดความใกล้ชิดจะถามว่าโหนดต้องใช้กี่ขั้นจึงจะเข้าถึงโหนดอื่นทั้งหมดได้ ในเครือข่ายที่มีน้ำหนัก ตรรกะดังกล่าวจะละเลยว่าการเชื่อมต่อแข็งแรงหรืออ่อนแอ ค่ากลางแบบวัดความใกล้ชิดถ่วงน้ำหนักปฏิบัติต่อแต่ละน้ำหนักของเส้นเชื่อมเสมือนเป็นความจุหรือระยะทางผกผัน: การเชื่อมต่อที่แข็งแรงกว่าจะนับเป็นก้าวที่สั้นกว่า โหนดที่มีคะแนนสูงไม่ได้เพียงแค่เชื่อมต่อได้ดีในเชิงโครงสร้างเท่านั้น แต่ยังใกล้ชิดกับโหนดอื่นอย่างแท้จริงผ่านเส้นทางที่มีความจุสูงหรือต้นทุนต่ำ Opsahl และคณะ (2010) ได้นำเสนอพารามิเตอร์ปรับค่าอัลฟาที่ช่วยให้นักวิเคราะห์สามารถเน้นที่ความยาวเส้นทางหรือน้ำหนักของเส้นเชื่อมได้ ทำให้เป็นการเชื่อมโยงระหว่างค่ากลางแบบวัดความใกล้ชิดที่ไม่มีน้ำหนักและแบบอิงน้ำหนักล้วนๆ
ประวัติศาสตร์
ค่ากลางแบบวัดความใกล้ชิดแบบคลาสสิกถูกทำให้เป็นทางการโดย Sabidussi (1966) และต่อมาได้รับความนิยมโดย Freeman (1978) การขยายไปยังเครือข่ายที่มีน้ำหนักได้รับการพัฒนาอย่างเป็นระบบโดย Opsahl, Agneessens และ Skvoretz ในบทความ Social Networks ปี 2010 ซึ่งเป็นการทำให้ทั่วไปทั้งการวัดแบบดีกรีและแบบเส้นทางที่สั้นที่สุดโดยใช้พารามิเตอร์ปรับค่าอัลฟา กรอบงานของพวกเขาได้กลายเป็นแหล่งอ้างอิงมาตรฐานสำหรับค่ากลางถ่วงน้ำหนักในการวิเคราะห์เครือข่ายสังคม และได้รับการนำไปใช้ในแพ็คเกจที่ใช้กันอย่างแพร่หลาย เช่น igraph และ NetworkX
ควรใช้เมื่อใด
ใช้ค่ากลางแบบวัดความใกล้ชิดถ่วงน้ำหนักเมื่อน้ำหนักของเส้นเชื่อม (ความถี่ความร่วมมือ ปริมาณการสื่อสาร กระแสเงินตรา ความจุในการขนส่ง) มีความหมายเชิงทฤษฎีและควรมีอิทธิพลต่อการพิจารณาโหนดที่เป็นศูนย์กลาง เหมาะสำหรับเครือข่ายสังคม เครือข่ายการค้า ระบบขนส่ง กราฟการเป็นผู้ร่วมประพันธ์ และทุกสถานการณ์ที่ประสิทธิภาพการเข้าถึงขึ้นอยู่กับความแข็งแรงของการเชื่อมต่อ ควรเลือกใช้แทนค่ากลางแบบวัดความใกล้ชิดที่ไม่มีน้ำหนักเมื่อการละเลยน้ำหนักจะทำให้การจัดอันดับค่ากลางบิดเบือน อย่าใช้เมื่อน้ำหนักไม่น่าเชื่อถือ ถูกปรับสเกลตามอำเภอใจ หรือไม่มีอยู่จริง ในกราฟที่ไม่เชื่อมต่อโดยไม่มีการจัดการคู่ที่ไม่สามารถเข้าถึงได้อย่างระมัดระวัง หรือเมื่อคำถามวิจัยเกี่ยวกับโครงสร้างเชิงโครงสร้างล้วนๆ แทนที่จะเป็นประสิทธิภาพการไหล
ข้อจำกัดและข้อควรพิจารณา
- ต้องการข้อมูลน้ำหนักที่สมบูรณ์และน่าเชื่อถือ น้ำหนักเส้นเชื่อมที่ขาดหายไปหรือมีสัญญาณรบกวนจะส่งผลโดยตรงต่อคะแนนค่ากลาง
- เครือข่ายที่ไม่เชื่อมต่อต้องการการจัดการพิเศษ (เช่น การยกเว้นคู่ที่ไม่สามารถเข้าถึงได้ หรือการใช้ค่ากลางแบบฮาร์มอนิก)
- การเลือกพารามิเตอร์อัลฟาต้องอาศัยเหตุผลเชิงทฤษฎี ค่าเริ่มต้นตามอำเภอใจอาจทำให้การจัดอันดับบิดเบือน
- ใช้ทรัพยากรในการคำนวณมากกว่าค่ากลางแบบดีกรีสำหรับเครือข่ายขนาดใหญ่ที่เบาบาง
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- รวมน้ำหนักของเส้นเชื่อม เพื่อให้การเชื่อมต่อที่แข็งแรงหรือมีประสิทธิภาพช่วยเพิ่มคะแนนค่ากลางของโหนดได้อย่างเหมาะสม
- พารามิเตอร์ปรับค่าอัลฟาให้การเชื่อมต่อแบบต่อเนื่องระหว่างค่ากลางแบบวัดความใกล้ชิดแบบไบนารีและแบบอิงน้ำหนักเต็มรูปแบบ
- ยังคงการตีความความใกล้ชิดที่เข้าใจง่าย: โหนดสามารถเข้าถึงหรือถูกเข้าถึงโดยผู้อื่นได้อย่างรวดเร็วเพียงใด
- สามารถเปรียบเทียบกับค่ากลางแบบวัดความใกล้ชิดที่ไม่มีน้ำหนักได้โดยตรง ทำให้สามารถวิเคราะห์ความไวแบบควบคุมได้
- เหมาะสมกับเครือข่ายถ่วงน้ำหนักแบบมีทิศทาง เมื่อรวมกับการแยกย่อยค่ากลางแบบวัดความใกล้ชิดขาเข้าและขาออก
การประยุกต์ใช้
- การระบุตัวกลางหลักในเครือข่ายความร่วมมือทางวิทยาศาสตร์โดยอิงจากความถี่ของการเป็นผู้ร่วมประพันธ์
- การจัดอันดับสนามบินหรือศูนย์กลางโลจิสติกส์ตามประสิทธิภาพการเข้าถึงในเครือข่ายการขนส่งหรือการค้าที่มีน้ำหนัก
- การตรวจจับผู้แพร่กระจายที่มีอิทธิพลในเครือข่ายการสื่อสารหรือโซเชียลมีเดียที่มีน้ำหนัก
- การประเมินศักยภาพการแพร่กระจายข้อมูลในเครือข่ายองค์กรหรือการแบ่งปันความรู้ที่มีน้ำหนัก
- การเปรียบเทียบการจัดอันดับค่ากลางภายใต้ค่าอัลฟาที่แตกต่างกันเพื่อประเมินความทนทานของผลการวิจัย
- การเสริมค่ากลางแบบวัดความเชื่อมโยงถ่วงน้ำหนักเพื่อแยกแยะความสามารถในการเข้าถึงที่มีประสิทธิภาพออกจากการควบคุมการไหล
วิธีการทำงาน
วิธีการทำงาน
น้ำหนักของเส้นเชื่อมจะถูกแปลงเป็นระยะทาง: สำหรับเครือข่ายความร่วมมือหรือความถี่ น้ำหนัก w จะถูกผกผัน (ระยะทาง = 1/w) เพื่อให้การเชื่อมต่อที่แข็งแรงกว่าส่งผลให้ระยะทางสั้นลง สำหรับเครือข่ายต้นทุนหรือความหน่วง เวลา น้ำหนักนั้นเป็นระยะทางอยู่แล้ว จากนั้นอัลกอริทึมของ Dijkstra จะค้นหาระยะทางถ่วงน้ำหนักต่ำสุด d^w(i,j) ระหว่างทุกคู่ของโหนด
สูตร
d^w(i,j) = \min_{\text{paths}} \sum_{e \in \text{path}} w_e^{-1}สำหรับแต่ละโหนด i ระยะทางถ่วงน้ำหนักไปยังโหนดอื่นที่เข้าถึงได้อีก n-1 โหนดจะถูกรวมเข้าด้วยกัน โหนดที่เชื่อมต่ออย่างอ่อนแอ หรือไม่เชื่อมต่อ กับส่วนใหญ่ของเครือข่ายจะสะสมผลรวมจำนวนมาก ซึ่งจะลดทอนคะแนนค่ากลางของโหนดนั้น
ค่ากลางแบบวัดความใกล้ชิดถ่วงน้ำหนักของโหนด i คือ (n-1) หารด้วยผลรวมของระยะทางถ่วงน้ำหนักไปยังโหนดอื่นทั้งหมด ซึ่งเป็นรูปแบบพีชคณิตเดียวกับค่ากลางแบบวัดความใกล้ชิดแบบคลาสสิก แต่ใช้ d^w แทนจำนวนก้าว วิธีนี้จะปรับคะแนนให้อยู่ในช่วง (0, 1] เพื่อให้สามารถเปรียบเทียบเครือข่ายที่มีขนาดต่างกันได้
สูตร
C^w(i) = \frac{n-1}{\sum_{j \neq i} d^w(i,j)}Opsahl และคณะ ได้นำเสนอพารามิเตอร์อัลฟา (0 ถึง 1) ซึ่งเป็นการผสมผสานระหว่างระยะทางเชิงโครงสร้างล้วนๆ (อัลฟา = 0 เทียบเท่ากับค่ากลางแบบวัดความใกล้ชิดที่ไม่มีน้ำหนัก) กับข้อมูลน้ำหนักล้วนๆ (อัลฟา = 1) ค่าระหว่างกลางช่วยให้นักวิจัยสามารถควบคุมว่าความแข็งแรงของการเชื่อมต่อมีความสำคัญเพียงใดเมื่อเทียบกับโครงสร้างเส้นทาง ทำให้การวัดสามารถปรับให้เข้ากับการตั้งค่าเชิงประจักษ์ที่หลากหลาย
สูตร
C^{w,\alpha}(i) = \frac{n-1}{\sum_{j \neq i} d^{w,\alpha}(i,j)}ข้อผิดพลาดที่พบบ่อย
- การใช้นับดิบเป็นน้ำหนักโดยไม่ตรวจสอบการแปลงน้ำหนักเป็นระยะทางที่เหมาะสม (เช่น การผกผันน้ำหนักความถี่)
- การใช้การวัดนี้กับกราฟที่ไม่เชื่อมต่อโดยไม่มีการปรับปรุงสำหรับคู่ที่ไม่สามารถเข้าถึงได้ ซึ่งทำให้ผลรวมของระยะทางสำหรับโหนดที่แยกจากกันสูงเกินจริง
- การปฏิบัติต่อการจัดอันดับค่ากลางเสมือนว่าคงที่โดยไม่ต้องทดสอบความไวต่อพารามิเตอร์อัลฟา
- การสับสนระหว่างค่ากลางแบบวัดความใกล้ชิดถ่วงน้ำหนักกับค่ากลางแบบวัดความเชื่อมโยง ค่ากลางแบบวัดความใกล้ชิดสะท้อนประสิทธิภาพการเข้าถึง ไม่ใช่การควบคุมการไหล
- การละเลยการปรับให้เป็นมาตรฐานเมื่อเปรียบเทียบโหนดข้ามเครือข่ายที่มีขนาดต่างกัน
คำถามที่พบบ่อย
ฉันควรเลือกพารามิเตอร์อัลฟาอย่างไร?
อัลฟา = 0 ให้ค่ากลางแบบวัดความใกล้ชิดที่ไม่มีน้ำหนัก (โครงสร้างเท่านั้น); อัลฟา = 1 ให้น้ำหนักมีอิทธิพล วิธีทั่วไปคือการคำนวณการจัดอันดับที่อัลฟา = 0, 0.5 และ 1 และรายงานความไว หากทฤษฎีบ่งชี้ว่าความแข็งแรงของการเชื่อมต่อเป็นกลไกหลัก อัลฟา = 1 สามารถอธิบายได้ หากโครงสร้างมีความสำคัญมากกว่า ให้ใช้อัลฟา = 0 หรือ 0.5
ฉันควรใช้การแปลงน้ำหนักเป็นระยะทางแบบใด?
สำหรับน้ำหนักความถี่ ความแข็งแรง หรือความจุ (ยิ่งมากยิ่งแข็งแรง) ให้ผกผันน้ำหนัก: ระยะทาง = 1/w สำหรับน้ำหนักต้นทุน ความหน่วงเวลา หรือความต้านทาน (ยิ่งมากยิ่งอ่อนแอ) ให้ใช้น้ำหนักโดยตรงเป็นระยะทาง การผสมผสานข้อตกลงเหล่านี้โดยไม่ระมัดระวังจะทำให้การจัดอันดับค่ากลางผกผัน
ฉันจะจัดการกับส่วนประกอบที่ไม่เชื่อมต่อได้อย่างไร?
แนวทางมาตรฐานคือการจำกัดผลรวมเฉพาะโหนดที่เข้าถึงได้และปรับให้เป็นมาตรฐานด้วย (n_reachable - 1) แทนที่จะเป็น (n - 1) หรือใช้ค่ากลางแบบฮาร์มอนิกซึ่งจัดการกับคู่ที่ไม่สามารถเข้าถึงได้โดยธรรมชาติโดยการรวมส่วนกลับของระยะทาง
ค่ากลางแบบวัดความใกล้ชิดถ่วงน้ำหนักดีกว่าค่ากลางแบบวัดความใกล้ชิดที่ไม่มีน้ำหนักหรือไม่?
เมื่อน้ำหนักมีความหมายที่สำคัญ (เช่น ความถี่ของการติดต่อ ปริมาณการค้า) ค่ากลางแบบวัดความใกล้ชิดถ่วงน้ำหนักจะให้ภาพประสิทธิภาพการเข้าถึงที่แม่นยำยิ่งขึ้น เมื่อน้ำหนักไม่น่าเชื่อถือ หรือน้ำหนักและโครงสร้างแทบไม่มีความสัมพันธ์กัน ความซับซ้อนที่เพิ่มขึ้นอาจไม่ช่วยปรับปรุงการอนุมาน
สิ่งนี้แตกต่างจากค่ากลางแบบวัดความเชื่อมโยงถ่วงน้ำหนักอย่างไร?
ค่ากลางแบบวัดความใกล้ชิดถ่วงน้ำหนักวัดว่าโหนดสามารถเข้าถึงโหนดอื่นผ่านเส้นทางที่แข็งแรงได้อย่างมีประสิทธิภาพเพียงใด ค่ากลางแบบวัดความเชื่อมโยงถ่วงน้ำหนักวัดว่าโหนดปรากฏบนเส้นทางที่สั้นที่สุดระหว่างคู่โหนดอื่นบ่อยเพียงใด โหนดหนึ่งอาจใกล้ (ค่ากลางแบบวัดความใกล้ชิดสูง) โดยไม่จำเป็นต้องเป็นสะพานที่สำคัญ (ค่ากลางแบบวัดความเชื่อมโยงสูง) และในทางกลับกัน
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
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คัดลอกแล้ว