ค่ากลางของความใกล้ชิด (Closeness Centrality)
- ผู้เสนอ
- Bavelas, A.; formalized by Freeman, L. C.
- ปี
- 1950 (formalized 1979)
- ประเภท
- Node-level centrality index
- กลุ่มวิธี
- Network science
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
ค่ากลางของความใกล้ชิดวัดว่าโหนดหนึ่งสามารถเข้าถึงโหนดอื่นๆ ทั้งหมดในเครือข่ายได้เร็วเพียงใด โดยคำนวณจากส่วนกลับของระยะทางที่สั้นที่สุดโดยเฉลี่ยไปยังโหนดอื่นๆ ทุกโหนด แนวคิดนี้ถูกอธิบายครั้งแรกโดย Bavelas (1950) และได้รับการรวบรวมอย่างเป็นทางการโดย Freeman (1979) เพื่อระบุโหนดที่สามารถกระจายข้อมูลหรือทรัพยากรได้อย่างมีประสิทธิภาพทั่วทั้งกราฟ โดยไม่เพียงแต่มุ่งเน้นที่โหนดที่มีการเชื่อมต่อโดยตรงจำนวนมากเท่านั้น
แนวคิดเบื้องหลังวิธีการ
ลองนึกภาพการส่งข้อความไปยังโหนดหนึ่ง แล้วสังเกตว่าข้อความนั้นจะไปถึงทุกมุมของเครือข่ายได้เร็วแค่ไหน โหนดที่มีค่าความใกล้ชิดสูงจะอยู่ใกล้ศูนย์กลางของโครงข่ายการเชื่อมต่อ: ต้องใช้จำนวนก้าวน้อยลงโดยเฉลี่ยในการเข้าถึงใครก็ตาม โหนดที่อยู่ชายขอบ แม้จะมีเพื่อนบ้านจำนวนมาก ก็อาจยังคงอยู่ห่างไกลจากส่วนใหญ่ของเครือข่าย ค่ากลางของความใกล้ชิดจับแนวคิดทางภูมิศาสตร์ของเครือข่ายนี้: ระยะทางเฉลี่ยที่สั้นหมายถึงความใกล้ชิดที่สูง และความใกล้ชิดที่สูงหมายถึงการกระจายข้อมูลที่มีประสิทธิภาพ หรือการเข้าถึงข้อมูลที่ไหลผ่านกราฟได้อย่างรวดเร็ว
ประวัติศาสตร์
Alex Bavelas ได้นำเสนอแนวคิดของค่ากลางของการสื่อสาร (communication centrality) โดยอิงตามเส้นทางที่สั้นที่สุดในปี 1950 ขณะศึกษาประสิทธิภาพการแก้ปัญหากลุ่มที่ MIT Linton Freeman ในบทความ Landmark ปี 1979 เรื่อง Social Networks ได้กำหนดค่ากลางของความใกล้ชิดอย่างเป็นทางการ ควบคู่ไปกับค่ากลางของดีกรีและค่ากลางของระหว่างกลาง ให้เป็นหนึ่งในสามมาตรวัดค่ากลางระดับโหนดที่เป็นแบบฉบับ (canonical) โดยจัดให้มีกรอบการทำงานทางคณิตศาสตร์ที่เป็นหนึ่งเดียว ซึ่งกลายเป็นรากฐานของการวิเคราะห์เครือข่ายสังคมสมัยใหม่
ควรใช้เมื่อใด
ใช้ค่ากลางของความใกล้ชิดเมื่อคุณต้องการระบุโหนดที่สามารถกระจายข้อมูล ระดมทรัพยากร หรือเข้าถึงส่วนที่เหลือของเครือข่ายได้อย่างมีประสิทธิภาพสูงสุด โดยมีตัวกลางน้อยที่สุด เช่น การระบุจุดเริ่มต้นการแพร่กระจายที่เหมาะสม ผู้สื่อสารที่มีอิทธิพล หรือศูนย์กลางการคมนาคม เหมาะสำหรับกราฟที่เชื่อมต่อกันหรือใกล้เคียงกันทุกขนาด อย่าใช้เป็นมาตรวัดค่ากลางหลักเมื่อเครือข่ายมีการแบ่งแยกสูง (ส่วนประกอบที่ไม่เชื่อมต่อกันหลายส่วน) เนื่องจากคะแนนความใกล้ชิดดิบจะเข้าใกล้ศูนย์และไม่มีความหมาย ให้ใช้การปรับมาตรฐานแบบ Wasserman-Faust หรือวิเคราะห์ส่วนประกอบแยกกัน หลีกเลี่ยงการสับสนระหว่างความใกล้ชิดกับค่ากลางของดีกรี: โหนดหนึ่งอาจมีการเชื่อมต่อโดยตรงจำนวนมาก แต่ยังคงอยู่ชายขอบในแง่ของการเข้าถึงทั่วโลก
ข้อจำกัดและข้อควรพิจารณา
- มีความอ่อนไหวต่อการเชื่อมต่อของกราฟ: ในเครือข่ายที่ไม่เชื่อมต่อกัน มาตรวัดดิบจะยุบตัวและต้องการการปรับมาตรฐาน
- ถือว่าเส้นทางที่สั้นที่สุดทั้งหมดมีความสำคัญเท่าเทียมกัน ไม่ได้คำนึงถึงปริมาณการจราจร หรือความน่าจะเป็นที่เส้นทางเฉพาะจะถูกใช้งานจริง
- ใช้ทรัพยากรในการคำนวณสูงบนกราฟขนาดใหญ่มาก (หลายล้านโหนด) เนื่องจากการคำนวณระยะทางที่สั้นที่สุดระหว่างทุกคู่ (all-pairs shortest-path) มีประสิทธิภาพต่ำหากไม่มีอัลกอริทึมประมาณค่า
- ไม่สามารถแยกแยะระหว่างโหนดที่ใกล้กับความสัมพันธ์ที่อ่อนแอจำนวนมาก กับโหนดที่ใกล้กับความสัมพันธ์ที่แข็งแกร่งและสำคัญเชิงกลยุทธ์เพียงไม่กี่อย่าง
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- จับการเข้าถึงทั่วโลก แทนที่จะเป็นเพียงการเชื่อมต่อเฉพาะที่ ทำให้เหมาะสำหรับการศึกษาการไหลของข้อมูลและการแพร่กระจาย
- คะแนนที่ปรับมาตรฐาน (0 ถึง 1) ช่วยให้สามารถเปรียบเทียบเครือข่ายที่มีขนาดต่างกันได้
- มีพื้นฐานทางทฤษฎีที่มั่นคง พร้อมการตรวจสอบความถูกต้องมานานหลายทศวรรษในสาขาสังคมวิทยา ระบาดวิทยา และวิทยาการคอมพิวเตอร์
- เสริมค่ากลางของดีกรีและค่ากลางของระหว่างกลาง (betweenness centrality) เพื่อให้เห็นภาพบทบาทของโหนดที่สมบูรณ์ยิ่งขึ้น
- สามารถคำนวณได้อย่างมีประสิทธิภาพด้วย BFS (ไม่มีน้ำหนัก) หรือ Dijkstra (มีน้ำหนัก) สำหรับเครือข่ายเชิงประจักษ์ส่วนใหญ่
การประยุกต์ใช้
- การระบุตัวกลางข้อมูลหลัก หรือผู้นำทางความคิดเห็นในเครือข่ายองค์กรและสังคม
- การเลือกโหนดเริ่มต้นที่เหมาะสมที่สุดเพื่อเพิ่มความเร็วในการแพร่กระจายข้อมูลหรือโรค
- การจัดอันดับสถานีขนส่งมวลชน หรือสี่แยกบนถนน ตามการเข้าถึงโดยรวมในเครือข่ายการคมนาคม
- การระบุโปรตีน หรือยีนที่มีอิทธิพลในเครือข่ายปฏิสัมพันธ์ทางชีววิทยา
- การตรวจจับผู้รับเทคโนโลยีรายแรกที่มีอิทธิพลในการศึกษากระบวนการแพร่กระจายเทคโนโลยี
- การจัดลำดับความสำคัญของเป้าหมายการแทรกแซงในเครือข่ายการติดต่อด้านสาธารณสุข เพื่อชะลอการแพร่ระบาดของโรคระบาด
วิธีการทำงาน
วิธีการทำงาน
แทนเครือข่ายด้วยกราฟ โดยที่โหนดคือผู้แสดง (บุคคล องค์กร หน้าเว็บ ยีน ฯลฯ) และเส้นเชื่อมเข้ารหัสความสัมพันธ์หรือปฏิสัมพันธ์ กราฟอาจเป็นแบบไม่มีทิศทาง (undirected) หรือมีทิศทาง (directed); เส้นเชื่อมอาจไม่มีน้ำหนัก (แต่ละก้าวมีค่าใช้จ่าย 1) หรือมีน้ำหนัก (ค่าใช้จ่ายเท่ากับน้ำหนักของเส้นเชื่อม ซึ่งตีความได้ว่าเป็นระยะทางหรือความแข็งแกร่งแบบส่วนกลับ)
สำหรับแต่ละโหนด v ให้คำนวณระยะทางที่สั้นที่สุด d(u, v) ไปยังโหนดที่เข้าถึงได้อื่นๆ ทุกโหนด u โดยใช้การค้นหาตามแนวกว้าง (Breadth-First Search) สำหรับกราฟที่ไม่มีน้ำหนัก หรืออัลกอริทึมของ Dijkstra สำหรับกราฟที่มีน้ำหนัก สำหรับกราฟที่มีทิศทาง เฉพาะเส้นทางที่ตามทิศทางของเส้นเชื่อมเท่านั้นที่ถูกต้อง ดังนั้น ค่าความใกล้ชิดขาเข้า (in-closeness) และค่าความใกล้ชิดขาออก (out-closeness) อาจแตกต่างกัน
สูตร
d(u,v) = \text{shortest path length between nodes } u \text{ and } vรวมระยะทางที่สั้นที่สุดทั้งหมดจาก v ไปยังโหนดอื่นๆ ทุกโหนด เพื่อให้ได้ค่าความห่าง (farness) ของ v ค่าความห่างที่น้อยหมายถึง v อยู่ใกล้โดยเฉลี่ยกับส่วนที่เหลือของเครือข่าย ค่าความห่างที่มากบ่งชี้ถึงความเป็นชายขอบ
สูตร
\text{farness}(v) = \sum_{u \neq v} d(u, v)นำส่วนกลับของระยะทางที่สั้นที่สุดโดยเฉลี่ยมาใช้: C(v) = (n-1) / ผลรวมของ d(u,v) การคูณด้วย (n-1) จะได้คะแนนที่ปรับมาตรฐานในช่วง (0, 1] เพื่อให้สามารถเปรียบเทียบโหนดในเครือข่ายที่มีขนาดต่างกันได้ ค่าที่สูงขึ้นบ่งชี้ถึงตำแหน่งที่อยู่ตรงกลางและเข้าถึงได้ง่ายกว่า
สูตร
C(v) = \frac{n-1}{\sum_{u \neq v} d(u, v)}ในกราฟที่ไม่เชื่อมต่อกัน โหนดหนึ่งไม่สามารถเข้าถึงโหนดอื่นๆ ทั้งหมดได้ ดังนั้น ค่าความใกล้ชิดดิบจึงเป็นศูนย์หรือไม่ได้กำหนดสำหรับคู่ที่ไม่สามารถเข้าถึงได้ การปรับมาตรฐานแบบ Wasserman-Faust ขยายแนวคิดความใกล้ชิดไปยังกราฟที่ไม่เชื่อมต่อกัน โดยการรวมเฉพาะโหนดที่เข้าถึงได้และปรับสเกลตามสัดส่วนของกราฟที่เข้าถึงได้ เพื่อป้องกันคะแนนที่ใกล้ศูนย์อย่างผิดพลาดสำหรับส่วนประกอบที่ไม่เชื่อมต่อกัน
ข้อผิดพลาดที่พบบ่อย
- การรายงานค่าความใกล้ชิดดิบในเครือข่ายที่มีส่วนประกอบที่ไม่เชื่อมต่อกันโดยไม่ได้ใช้การปรับมาตรฐานแบบ Wasserman-Faust ซึ่งทำให้เกิดคะแนนที่ใกล้ศูนย์และทำให้เข้าใจผิด
- การปฏิบัติต่อค่ากลางของความใกล้ชิดและค่ากลางของดีกรีเสมือนเป็นสิ่งเดียวกัน — ดีกรีสูงไม่ได้หมายถึงความใกล้ชิดสูง และในทางกลับกัน
- การละเลยว่าเส้นเชื่อมมีทิศทางหรือไม่: ในเครือข่ายที่มีทิศทาง ควรคำนวณค่าความใกล้ชิดแยกกันสำหรับทิศทางขาเข้าและขาออก
- การใช้ค่าความใกล้ชิดที่ไม่มีน้ำหนักกับเครือข่ายที่มีน้ำหนักซึ่งน้ำหนักของเส้นเชื่อมเข้ารหัสระยะทางที่มีความหมาย ทำให้สูญเสียข้อมูลเกี่ยวกับความแข็งแกร่งของความสัมพันธ์
- การเปรียบเทียบคะแนนความใกล้ชิดดิบ (ไม่ได้ปรับมาตรฐาน) ข้ามเครือข่ายที่มีขนาดต่างกันโดยไม่ได้ควบคุม n
คำถามที่พบบ่อย
ค่ากลางของความใกล้ชิดแตกต่างจากค่ากลางของดีกรีอย่างไร?
ค่ากลางของดีกรีจะนับเฉพาะเพื่อนบ้านโดยตรงเท่านั้น ดังนั้นโหนดหนึ่งอาจมีคะแนนสูงหากมีการเชื่อมต่อจำนวนมาก แม้ว่าการเชื่อมต่อนั้นจะกระจุกตัวอยู่ในมุมหนึ่งของเครือข่ายก็ตาม ค่ากลางของความใกล้ชิดจะพิจารณาระยะทางที่สั้นที่สุดไปยังทุกโหนดในกราฟ ดังนั้นจึงให้รางวัลกับการเข้าถึงทั่วโลก โหนดที่อยู่ชายขอบซึ่งเป็นศูนย์กลางของกลุ่มย่อย (clique hub) อาจมีดีกรีสูง แต่ความใกล้ชิดต่ำ
ฉันควรทำอย่างไรเมื่อเครือข่ายของฉันมีส่วนประกอบที่ไม่เชื่อมต่อกัน?
ใช้การปรับมาตรฐานแบบ Wasserman-Faust (1994) แบบฮาร์มอนิก (harmonic) หรือแบบปรับตามการเข้าถึง (reachability-adjusted) ซึ่งจะรวมเฉพาะคู่ที่เข้าถึงได้และปรับสเกลตามสัดส่วนของเครือข่ายที่เข้าถึงได้ หรืออีกทางหนึ่ง ให้วิเคราะห์ส่วนประกอบที่เชื่อมต่อกันที่ใหญ่ที่สุดแยกต่างหาก หรือใช้ค่ากลางฮาร์มอนิก (ผลรวมของส่วนกลับของระยะทาง) ซึ่งจัดการกับคู่ที่ไม่สามารถเข้าถึงได้โดยธรรมชาติ โดยกำหนดค่าการมีส่วนร่วมเป็นศูนย์
ค่ากลางของความใกล้ชิดใช้ได้กับเครือข่ายที่มีน้ำหนักหรือไม่?
ได้ แทนที่ BFS ด้วยอัลกอริทึมของ Dijkstra โดยใช้น้ำหนักของเส้นเชื่อมเป็นระยะทาง (หรือส่วนกลับของน้ำหนักความแข็งแกร่ง/ความคล้ายคลึง หากน้ำหนักที่สูงกว่าหมายถึงใกล้กว่า) ค่าความใกล้ชิดที่มีน้ำหนักที่ได้จะสะท้อนทั้งโครงสร้าง (topology) และคุณภาพของการเชื่อมต่อ
ฉันจะตีความคะแนนความใกล้ชิดที่ปรับมาตรฐานได้อย่างไร?
คะแนนที่ใกล้ 1 หมายความว่าโหนดสามารถเข้าถึงโหนดอื่น ๆ ทั้งหมดได้โดยเฉลี่ยประมาณหนึ่งก้าวเท่านั้น — โหนดนั้นอยู่ตรงกลางเครือข่าย คะแนนที่ใกล้ 0 หมายความว่าโหนดนั้นอยู่ชายขอบมาก คะแนนที่สูงกว่าประมาณ 0.6 โดยทั่วไปบ่งชี้ถึงตำแหน่งที่อยู่ตรงกลางอย่างแท้จริงในเครือข่ายเชิงประจักษ์ส่วนใหญ่
ค่ากลางของความใกล้ชิดเหมาะสมสำหรับเครือข่ายที่มีทิศทางหรือไม่?
ได้ แต่ให้คำนวณแยกกันในแต่ละทิศทาง ค่าความใกล้ชิดขาเข้า (in-closeness) วัดว่าโหนดอื่น ๆ สามารถเข้าถึงโหนดเป้าหมายได้ง่ายเพียงใด (มีประโยชน์ในการศึกษาชื่อเสียง หรือความสามารถในการรับของโหนด) ในขณะที่ค่าความใกล้ชิดขาออก (out-closeness) วัดว่าโหนดเป้าหมายสามารถเข้าถึงโหนดอื่น ๆ ได้ง่ายเพียงใด (มีประโยชน์ในการศึกษาความสามารถในการกระจายข่าวสาร)
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Freeman, L. C. (1979). Centrality in social networks: Conceptual clarification. Social Networks, 1(3), 215–239.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วBavelas, A. (1950). Communication patterns in task-oriented groups. Journal of the Acoustical Society of America, 22(6), 725–730.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว