ค่าความเป็นจุดศูนย์กลางระหว่างจุด (Betweenness Centrality)
- ผู้เสนอ
- Freeman, L. C.
- ปี
- 1977
- ประเภท
- Centrality measure
- กลุ่มวิธี
- Network science
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
ค่าความเป็นจุดศูนย์กลางระหว่างจุด (Betweenness centrality) ซึ่งถูกกำหนดรูปแบบอย่างเป็นทางการโดย Linton C. Freeman ในปี 1977 เป็นการวัดว่าโหนดหนึ่งๆ ปรากฏอยู่บนเส้นทางที่สั้นที่สุดที่เชื่อมต่อระหว่างคู่โหนดอื่นๆ บ่อยครั้งเพียงใด โหนดที่มีค่าความเป็นจุดศูนย์กลางระหว่างจุดสูงจะทำหน้าที่เป็นสะพานหรือตัวกลาง: การลบโหนดเหล่านี้จะทำให้เครือข่ายแตกออกเป็นส่วนๆ ที่ไม่เชื่อมต่อกันอย่างรุนแรงกว่าการลบโหนดอื่นๆ
แนวคิดเบื้องหลังวิธีการ
ลองนึกถึงเครือข่ายถนนในเมืองที่เส้นทางข้ามทวีปทั้งหมดต้องผ่านจุดตัดเพียงจุดเดียว จุดตัดนั้นจะมีค่าความเป็นจุดศูนย์กลางระหว่างจุดสูงสุด แม้ว่าจะมีถนนเพียงไม่กี่สายก็ตาม ในเครือข่ายสังคม บุคคลที่ส่งต่อข้อมูลระหว่างสองกลุ่มที่แยกจากกันโดยสิ้นเชิงเป็นประจำ จะอยู่ในตำแหน่งเดียวกัน: พวกเขาอาจไม่ได้รู้จักคนจำนวนมากโดยตรง แต่พวกเขานั่งอยู่บนเส้นทางที่สำคัญซึ่งยึดเหนี่ยวเครือข่ายไว้ด้วยกัน ค่าความเป็นจุดศูนย์กลางระหว่างจุดจะวัดบทบาทตัวกลางนั้นได้อย่างแม่นยำ โดยไม่ขึ้นกับจำนวนการเชื่อมต่อดิบ
ประวัติศาสตร์
Linton Freeman ได้กำหนดรูปแบบค่าความเป็นจุดศูนย์กลางระหว่างจุดอย่างเป็นทางการในบทความสำคัญของเขาเรื่อง Sociometry ปี 1977 โดยอิงจากการใช้งานแนวคิดอย่างไม่เป็นทางการก่อนหน้านี้โดย Bavelas (1948) ในการทดลองการสื่อสาร สูตรของ Freeman ได้รวมเอาสัญชาตญาณที่คลุมเครือหลายอย่างเกี่ยวกับความสำคัญของโหนดเข้าไว้ด้วยกันเป็นมาตรวัดเดียวที่สามารถคำนวณได้ และกลายเป็นคำจำกัดความที่เป็นมาตรฐานที่ใช้ในวิทยาศาสตร์เครือข่าย อัลกอริทึมของ Ulrik Brandes ในปี 2001 ได้ลดการคำนวณจาก O(V^3) เป็น O(VE) ทำให้ค่าความเป็นจุดศูนย์กลางระหว่างจุดสามารถนำไปใช้ได้จริงกับเครือข่ายที่มีโหนดหลายพันโหนด และตอกย้ำตำแหน่งของมันในฐานะเครื่องมือมาตรฐานในซอฟต์แวร์วิเคราะห์เครือข่ายสังคม
ควรใช้เมื่อใด
ใช้ค่าความเป็นจุดศูนย์กลางระหว่างจุดเมื่อคำถามวิจัยของคุณเกี่ยวกับบทบาทตัวกลาง การเป็นผู้ควบคุม หรือโหนดสะพาน — ผู้กระทำการที่การลบจะขัดขวางการไหลของข้อมูลหรือความเชื่อมโยงของเครือข่าย เหมาะสำหรับกราฟที่มีทิศทางและไม่มีทิศทาง และสำหรับกราฟที่มีน้ำหนักซึ่งน้ำหนักขอบแสดงถึงระยะทางหรือต้นทุน มีคุณค่าอย่างยิ่งในเครือข่ายการสื่อสาร เครือข่ายการอ้างอิง กราฟความร่วมมือ และห่วงโซ่อุปทาน อย่าใช้เป็นมาตรวัดความเป็นจุดศูนย์กลางเพียงอย่างเดียวเมื่อบทบาทตัวกลางไม่ใช่จุดสนใจทางทฤษฎี: ค่าความเป็นจุดศูนย์กลางตามดีกรี (degree centrality) นั้นง่ายกว่าและเพียงพอสำหรับคำถามเกี่ยวกับความเชื่อมโยงล้วนๆ และค่าความเป็นจุดศูนย์กลางตามลักษณะเฉพาะ (eigenvector centrality) หรือ PageRank centrality จะจับการแพร่กระจายของบารมีได้ดีกว่า หลีกเลี่ยงการใช้กับเครือข่ายที่เบาบางมากโดยไม่มีการใช้งานที่มีประสิทธิภาพ เนื่องจากการคำนวณแบบตรงไปตรงมาคือ O(V^2 E)
ข้อจำกัดและข้อควรพิจารณา
- มีค่าใช้จ่ายในการคำนวณสูงในเครือข่ายที่หนาแน่นมากแม้จะใช้อัลกอริทึมของ Brandes อาจจำเป็นต้องใช้อัลกอริทึมประมาณค่าสำหรับกราฟขนาดเว็บ
- สมมติว่าผู้กระทำการใช้เส้นทางที่สั้นที่สุด ซึ่งอาจไม่สมจริงในเครือข่ายที่การไหลผ่านเส้นทางที่ยาวกว่า (เช่น การเดินแบบสุ่มในเครือข่ายไฟฟ้า)
- มีความอ่อนไหวต่อขอบที่ขาดหายไปหรือมีสัญญาณรบกวน: แม้แต่ความสัมพันธ์ที่ไม่ได้สังเกตเพียงไม่กี่อย่างก็สามารถเปลี่ยนแปลงอันดับความเป็นจุดศูนย์กลางระหว่างจุดได้อย่างมาก
- ให้ความสำคัญเท่าเทียมกันกับทุกเส้นทางที่สั้นที่สุด แม้ว่าความจุของขอบหรือความแข็งแรงของความสัมพันธ์จะแตกต่างกันอย่างมาก
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- จับบทบาทตัวกลางและสะพานเชิงโครงสร้างที่ค่าความเป็นจุดศูนย์กลางตามดีกรีและลักษณะเฉพาะไม่สามารถจับได้เลย
- สามารถนำไปใช้กับเครือข่ายที่มีทิศทาง ไม่มีทิศทาง มีน้ำหนัก และไม่มีน้ำหนัก ด้วยสูตรเดียวกัน
- คะแนนที่เป็นมาตรฐานช่วยให้สามารถเปรียบเทียบโหนดภายในเครือข่ายเดียวกันและระหว่างเครือข่ายที่มีขนาดต่างกันได้อย่างมีความหมาย
- อัลกอริทึมของ Brandes ทำให้การคำนวณสามารถจัดการได้สำหรับเครือข่ายที่มีโหนดหลายล้านโหนดเมื่อนำไปใช้ในไลบรารีที่ปรับให้เหมาะสม เช่น NetworkX หรือ igraph
- การตีความทางทฤษฎีที่มีพื้นฐานดี: โหนดที่มีค่าความเป็นจุดศูนย์กลางระหว่างจุดสูงมีความสัมพันธ์เชิงประจักษ์กับการควบคุมข้อมูล อำนาจ และช่องว่างเชิงโครงสร้างในการวิจัยองค์กรและสังคม
การประยุกต์ใช้
- การระบุผู้ควบคุมและตัวกลางข้อมูลในเครือข่ายการสื่อสารขององค์กร
- การตรวจจับโหนดโครงสร้างพื้นฐานที่สำคัญในการศึกษาโทโพโลยีการขนส่ง เครือข่ายไฟฟ้า และอินเทอร์เน็ต
- การค้นหาผู้เขียนหรือบทความที่เป็นตัวกลางหลักในเครือข่ายการอ้างอิงและความร่วมมือ
- การสร้างแผนที่ช่องว่างเชิงโครงสร้างและตำแหน่งตัวกลางในเครือข่ายพันธมิตรระหว่างองค์กร
- การระบุผู้แพร่กระจายที่มีอิทธิพลในแบบจำลองการแพร่ระบาดทางระบาดวิทยาและข่าวลือ
- การจัดลำดับความสำคัญของโหนดสำหรับการแทรกแซงเป้าหมาย (เช่น การฉีดวัคซีน การขัดขวาง) ในการวิจัยสาธารณสุขและความปลอดภัย
วิธีการทำงาน
วิธีการทำงาน
สำหรับแต่ละคู่โหนดที่มีลำดับ (s, t) ที่แตกต่างกันในเครือข่าย เส้นทางที่สั้นที่สุดทั้งหมด (geodesics) ระหว่างโหนดเหล่านั้นจะถูกระบุ สำหรับกราฟที่มีน้ำหนัก เส้นทางที่สั้นที่สุดจะถูกกำหนดโดยน้ำหนักขอบรวมน้อยที่สุด สำหรับกราฟที่ไม่มีน้ำหนัก โดยจำนวนฮอปน้อยที่สุด ขั้นตอนนี้เป็นการกำหนดจักรวาลของเส้นทางที่จะกระจายค่าความเป็นจุดศูนย์กลางระหว่างจุด
สำหรับแต่ละคู่ (s, t) จะมีการนับจำนวนเส้นทางที่สั้นที่สุดทั้งหมด sigma(s, t) เมื่อมีเส้นทางที่สั้นเท่ากันหลายเส้นทาง แต่ละเส้นทางจะถูกนับแยกกัน ตัวหารนี้แสดงถึงปริมาณการจราจรบนเส้นทางที่สั้นที่สุดทั้งหมดระหว่าง s และ t โดยไม่มีข้อจำกัดในการกำหนดเส้นทาง
สูตร
\sigma(s,t) = \text{number of shortest paths from } s \text{ to } tสำหรับแต่ละโหนดผู้สมัคร v (โดยที่ v ไม่ใช่ทั้ง s และ t) จำนวนเส้นทางที่สั้นที่สุด sigma(s, t) ที่ผ่านโหนด v จริงๆ จะถูกบันทึกเป็น sigma(s, t | v) อัตราส่วน sigma(s, t | v) / sigma(s, t) จะให้เศษส่วนของการจราจรบนเส้นทางที่สั้นที่สุดระหว่าง s และ t ที่ถูกกำหนดเส้นทางผ่าน v
สูตร
\sigma(s,t|v) = \text{shortest paths from } s \text{ to } t \text{ passing through } vเศษส่วนเหล่านี้จะถูกรวมเข้าด้วยกันสำหรับทุกคู่ที่ถูกต้อง (s, t) เพื่อสร้างคะแนนดิบความเป็นจุดศูนย์กลางระหว่างจุด C_B(v) โหนดที่การลบจะตัดเส้นทางที่สั้นที่สุดระหว่างคู่จำนวนมากออก จะสะสมผลรวมสูง ซึ่งบ่งชี้ถึงตำแหน่งตัวกลางที่มีความสำคัญเชิงโครงสร้าง
สูตร
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma(s,t|v)}{\sigma(s,t)}คะแนนดิบจะเพิ่มขึ้นตามขนาดของเครือข่าย ทำให้การเปรียบเทียบระหว่างเครือข่ายที่มีขนาดต่างกันไม่มีความหมาย การทำให้เป็นมาตรฐานโดย (n-1)(n-2)/2 สำหรับกราฟที่ไม่มีทิศทาง (หรือ (n-1)(n-2) สำหรับกราฟที่มีทิศทาง) จะปรับคะแนนให้อยู่ในช่วง [0, 1] โดย 1.0 หมายถึงโหนดนั้นอยู่บนทุกเส้นทางที่สั้นที่สุด และ 0 หมายถึงไม่อยู่บนเส้นทางใดเลย Brandes (2001) ได้นำเสนออัลกอริทึม O(VE) ที่คำนวณคะแนนความเป็นจุดศูนย์กลางระหว่างจุดทั้งหมดพร้อมกัน แทนที่จะค้นหาซ้ำสำหรับแต่ละโหนด
สูตร
C_B^{\text{norm}}(v) = \frac{C_B(v)}{(n-1)(n-2)/2}ข้อผิดพลาดที่พบบ่อย
- การปฏิบัติต่อค่าความเป็นจุดศูนย์กลางระหว่างจุดสูงเทียบเท่ากับค่าดีกรีสูงโดยไม่ได้ตรวจสอบทั้งสองอย่าง: โหนดที่อยู่ชายขอบสามารถมีอันดับแรกในค่าความเป็นจุดศูนย์กลางระหว่างจุด ในขณะที่อยู่อันดับสุดท้ายในค่าดีกรี
- การเปรียบเทียบคะแนนความเป็นจุดศูนย์กลางระหว่างจุดดิบ (ไม่ได้ปรับมาตรฐาน) ระหว่างเครือข่ายที่มีขนาดต่างกัน
- การละเลยทิศทางของขอบในเครือข่ายที่มีทิศทาง ซึ่งอาจทำให้การระบุตัวกลางผิดพลาดเมื่อการไหลไม่สมมาตร
- การใช้ค่าความเป็นจุดศูนย์กลางระหว่างจุดมาตรฐานกับเครือข่ายที่มีน้ำหนักโดยไม่ยืนยันว่าน้ำหนักขอบถูกตีความอย่างถูกต้องว่าเป็นต้นทุน (ไม่ใช่ความคล้ายคลึง) ในอัลกอริทึมเส้นทางที่สั้นที่สุด
- การมองข้ามวิธีการประมาณค่าความเป็นจุดศูนย์กลางระหว่างจุดสำหรับเครือข่ายขนาดใหญ่ และการหยุดการคำนวณบนโหนดหลายล้านโหนด
คำถามที่พบบ่อย
ค่าความเป็นจุดศูนย์กลางระหว่างจุดแตกต่างจากค่าความเป็นจุดศูนย์กลางตามดีกรีอย่างไร
ค่าความเป็นจุดศูนย์กลางตามดีกรีจะนับการเชื่อมต่อโดยตรง โหนดศูนย์กลางที่มีการเชื่อมต่อจำนวนมากจะมีคะแนนสูง ค่าความเป็นจุดศูนย์กลางระหว่างจุดจะนับว่าโหนดหนึ่งๆ อยู่บนเส้นทางที่สั้นที่สุดระหว่างโหนดอื่นบ่อยครั้งเพียงใด โหนดสะพานที่เชื่อมต่อสองกลุ่มที่เบาบางจะมีคะแนนสูงแม้จะมีการเชื่อมต่อโดยตรงน้อย มาตรวัดทั้งสองจับแง่มุมที่ตั้งฉากของความสำคัญเชิงโครงสร้าง
ฉันควรใช้คะแนนความเป็นจุดศูนย์กลางระหว่างจุดที่ปรับมาตรฐานหรือคะแนนดิบ
ใช้คะแนนที่ปรับมาตรฐานเมื่อใดก็ตามที่คุณเปรียบเทียบโหนดระหว่างเครือข่ายที่มีขนาดต่างกัน หรือนำเสนอผลลัพธ์แก่ผู้อ่านที่ไม่คุ้นเคยกับขนาดเครือข่ายของคุณ คะแนนดิบจะยอมรับได้เฉพาะสำหรับการเปรียบเทียบภายในเครือข่ายเดียวที่คงที่ซึ่งตัวหารมีค่าคงที่
ฉันจะจัดการกับขอบที่มีน้ำหนักได้อย่างไร
ตั้งค่าน้ำหนักขอบเพื่อแสดงถึงระยะทางหรือต้นทุน ไม่ใช่ความคล้ายคลึง การใช้งานส่วนใหญ่ (NetworkX, igraph) ยอมรับพารามิเตอร์น้ำหนักที่ตีความว่าเป็นระยะทาง หากน้ำหนักของคุณแสดงถึงความแข็งแรงหรือความคล้ายคลึง ให้กลับค่า (เช่น น้ำหนัก = 1/ความคล้ายคลึง) ก่อนคำนวณค่าความเป็นจุดศูนย์กลางระหว่างจุด
ค่าความเป็นจุดศูนย์กลางระหว่างจุดมีความหมายสำหรับเครือข่ายที่ไม่เชื่อมต่อกันหรือไม่
สำหรับกราฟที่ไม่เชื่อมต่อกัน เส้นทางที่สั้นที่สุดระหว่างโหนดในส่วนประกอบที่ต่างกันจะไม่มีการกำหนด (อนันต์) ซอฟต์แวร์ส่วนใหญ่จะปฏิบัติต่อคู่เหล่านั้นว่ามีส่วนทำให้ผลรวมเป็นศูนย์ ซึ่งอาจทำให้คะแนนลดลง ให้วิเคราะห์แต่ละส่วนประกอบที่เชื่อมต่อกันแยกต่างหาก หรือใช้รูปแบบอื่น เช่น ค่าความเป็นจุดศูนย์กลางตามความเครียด (stress centrality) ที่มีการจัดการคู่ที่ไม่ได้เชื่อมต่ออย่างชัดเจน
เครือข่ายของฉันมีโหนดหลายล้านโหนด — ฉันยังสามารถคำนวณค่าความเป็นจุดศูนย์กลางระหว่างจุดได้หรือไม่
การคำนวณที่แม่นยำด้วยอัลกอริทึมของ Brandes คือ O(VE) และอาจช้าเกินไป ใช้การประมาณค่าแบบสุ่ม (เช่น การสุ่มตัวอย่างโหนดต้นทาง k โหนด) ที่มีอยู่ใน NetworkX (betweenness_centrality พร้อมพารามิเตอร์ k) หรือไลบรารีกราฟ เช่น graph-tool ซึ่งให้ช่วงความเชื่อมั่นของคะแนนประมาณค่า
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40(1), 35–41.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วBrandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163–177.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว