Skip to content
กลับไปยังผลการค้นหา

ค่ากลางของความใกล้ชิด (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 (มีน้ำหนัก) สำหรับเครือข่ายเชิงประจักษ์ส่วนใหญ่

การประยุกต์ใช้

  • การระบุตัวกลางข้อมูลหลัก หรือผู้นำทางความคิดเห็นในเครือข่ายองค์กรและสังคม
  • การเลือกโหนดเริ่มต้นที่เหมาะสมที่สุดเพื่อเพิ่มความเร็วในการแพร่กระจายข้อมูลหรือโรค
  • การจัดอันดับสถานีขนส่งมวลชน หรือสี่แยกบนถนน ตามการเข้าถึงโดยรวมในเครือข่ายการคมนาคม
  • การระบุโปรตีน หรือยีนที่มีอิทธิพลในเครือข่ายปฏิสัมพันธ์ทางชีววิทยา
  • การตรวจจับผู้รับเทคโนโลยีรายแรกที่มีอิทธิพลในการศึกษากระบวนการแพร่กระจายเทคโนโลยี
  • การจัดลำดับความสำคัญของเป้าหมายการแทรกแซงในเครือข่ายการติดต่อด้านสาธารณสุข เพื่อชะลอการแพร่ระบาดของโรคระบาด

วิธีการทำงาน

วิธีการทำงาน

1

แทนเครือข่ายด้วยกราฟ โดยที่โหนดคือผู้แสดง (บุคคล องค์กร หน้าเว็บ ยีน ฯลฯ) และเส้นเชื่อมเข้ารหัสความสัมพันธ์หรือปฏิสัมพันธ์ กราฟอาจเป็นแบบไม่มีทิศทาง (undirected) หรือมีทิศทาง (directed); เส้นเชื่อมอาจไม่มีน้ำหนัก (แต่ละก้าวมีค่าใช้จ่าย 1) หรือมีน้ำหนัก (ค่าใช้จ่ายเท่ากับน้ำหนักของเส้นเชื่อม ซึ่งตีความได้ว่าเป็นระยะทางหรือความแข็งแกร่งแบบส่วนกลับ)

2

สำหรับแต่ละโหนด 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
3

รวมระยะทางที่สั้นที่สุดทั้งหมดจาก v ไปยังโหนดอื่นๆ ทุกโหนด เพื่อให้ได้ค่าความห่าง (farness) ของ v ค่าความห่างที่น้อยหมายถึง v อยู่ใกล้โดยเฉลี่ยกับส่วนที่เหลือของเครือข่าย ค่าความห่างที่มากบ่งชี้ถึงความเป็นชายขอบ

สูตร
\text{farness}(v) = \sum_{u \neq v} d(u, v)
4

นำส่วนกลับของระยะทางที่สั้นที่สุดโดยเฉลี่ยมาใช้: C(v) = (n-1) / ผลรวมของ d(u,v) การคูณด้วย (n-1) จะได้คะแนนที่ปรับมาตรฐานในช่วง (0, 1] เพื่อให้สามารถเปรียบเทียบโหนดในเครือข่ายที่มีขนาดต่างกันได้ ค่าที่สูงขึ้นบ่งชี้ถึงตำแหน่งที่อยู่ตรงกลางและเข้าถึงได้ง่ายกว่า

สูตร
C(v) = \frac{n-1}{\sum_{u \neq v} d(u, v)}
5

ในกราฟที่ไม่เชื่อมต่อกัน โหนดหนึ่งไม่สามารถเข้าถึงโหนดอื่นๆ ทั้งหมดได้ ดังนั้น ค่าความใกล้ชิดดิบจึงเป็นศูนย์หรือไม่ได้กำหนดสำหรับคู่ที่ไม่สามารถเข้าถึงได้ การปรับมาตรฐานแบบ Wasserman-Faust ขยายแนวคิดความใกล้ชิดไปยังกราฟที่ไม่เชื่อมต่อกัน โดยการรวมเฉพาะโหนดที่เข้าถึงได้และปรับสเกลตามสัดส่วนของกราฟที่เข้าถึงได้ เพื่อป้องกันคะแนนที่ใกล้ศูนย์อย่างผิดพลาดสำหรับส่วนประกอบที่ไม่เชื่อมต่อกัน

ข้อผิดพลาดที่พบบ่อย

  • การรายงานค่าความใกล้ชิดดิบในเครือข่ายที่มีส่วนประกอบที่ไม่เชื่อมต่อกันโดยไม่ได้ใช้การปรับมาตรฐานแบบ Wasserman-Faust ซึ่งทำให้เกิดคะแนนที่ใกล้ศูนย์และทำให้เข้าใจผิด
  • การปฏิบัติต่อค่ากลางของความใกล้ชิดและค่ากลางของดีกรีเสมือนเป็นสิ่งเดียวกัน — ดีกรีสูงไม่ได้หมายถึงความใกล้ชิดสูง และในทางกลับกัน
  • การละเลยว่าเส้นเชื่อมมีทิศทางหรือไม่: ในเครือข่ายที่มีทิศทาง ควรคำนวณค่าความใกล้ชิดแยกกันสำหรับทิศทางขาเข้าและขาออก
  • การใช้ค่าความใกล้ชิดที่ไม่มีน้ำหนักกับเครือข่ายที่มีน้ำหนักซึ่งน้ำหนักของเส้นเชื่อมเข้ารหัสระยะทางที่มีความหมาย ทำให้สูญเสียข้อมูลเกี่ยวกับความแข็งแกร่งของความสัมพันธ์
  • การเปรียบเทียบคะแนนความใกล้ชิดดิบ (ไม่ได้ปรับมาตรฐาน) ข้ามเครือข่ายที่มีขนาดต่างกันโดยไม่ได้ควบคุม n

คำถามที่พบบ่อย

ค่ากลางของความใกล้ชิดแตกต่างจากค่ากลางของดีกรีอย่างไร?

ค่ากลางของดีกรีจะนับเฉพาะเพื่อนบ้านโดยตรงเท่านั้น ดังนั้นโหนดหนึ่งอาจมีคะแนนสูงหากมีการเชื่อมต่อจำนวนมาก แม้ว่าการเชื่อมต่อนั้นจะกระจุกตัวอยู่ในมุมหนึ่งของเครือข่ายก็ตาม ค่ากลางของความใกล้ชิดจะพิจารณาระยะทางที่สั้นที่สุดไปยังทุกโหนดในกราฟ ดังนั้นจึงให้รางวัลกับการเข้าถึงทั่วโลก โหนดที่อยู่ชายขอบซึ่งเป็นศูนย์กลางของกลุ่มย่อย (clique hub) อาจมีดีกรีสูง แต่ความใกล้ชิดต่ำ

ฉันควรทำอย่างไรเมื่อเครือข่ายของฉันมีส่วนประกอบที่ไม่เชื่อมต่อกัน?

ใช้การปรับมาตรฐานแบบ Wasserman-Faust (1994) แบบฮาร์มอนิก (harmonic) หรือแบบปรับตามการเข้าถึง (reachability-adjusted) ซึ่งจะรวมเฉพาะคู่ที่เข้าถึงได้และปรับสเกลตามสัดส่วนของเครือข่ายที่เข้าถึงได้ หรืออีกทางหนึ่ง ให้วิเคราะห์ส่วนประกอบที่เชื่อมต่อกันที่ใหญ่ที่สุดแยกต่างหาก หรือใช้ค่ากลางฮาร์มอนิก (ผลรวมของส่วนกลับของระยะทาง) ซึ่งจัดการกับคู่ที่ไม่สามารถเข้าถึงได้โดยธรรมชาติ โดยกำหนดค่าการมีส่วนร่วมเป็นศูนย์

ค่ากลางของความใกล้ชิดใช้ได้กับเครือข่ายที่มีน้ำหนักหรือไม่?

ได้ แทนที่ BFS ด้วยอัลกอริทึมของ Dijkstra โดยใช้น้ำหนักของเส้นเชื่อมเป็นระยะทาง (หรือส่วนกลับของน้ำหนักความแข็งแกร่ง/ความคล้ายคลึง หากน้ำหนักที่สูงกว่าหมายถึงใกล้กว่า) ค่าความใกล้ชิดที่มีน้ำหนักที่ได้จะสะท้อนทั้งโครงสร้าง (topology) และคุณภาพของการเชื่อมต่อ

ฉันจะตีความคะแนนความใกล้ชิดที่ปรับมาตรฐานได้อย่างไร?

คะแนนที่ใกล้ 1 หมายความว่าโหนดสามารถเข้าถึงโหนดอื่น ๆ ทั้งหมดได้โดยเฉลี่ยประมาณหนึ่งก้าวเท่านั้น — โหนดนั้นอยู่ตรงกลางเครือข่าย คะแนนที่ใกล้ 0 หมายความว่าโหนดนั้นอยู่ชายขอบมาก คะแนนที่สูงกว่าประมาณ 0.6 โดยทั่วไปบ่งชี้ถึงตำแหน่งที่อยู่ตรงกลางอย่างแท้จริงในเครือข่ายเชิงประจักษ์ส่วนใหญ่

ค่ากลางของความใกล้ชิดเหมาะสมสำหรับเครือข่ายที่มีทิศทางหรือไม่?

ได้ แต่ให้คำนวณแยกกันในแต่ละทิศทาง ค่าความใกล้ชิดขาเข้า (in-closeness) วัดว่าโหนดอื่น ๆ สามารถเข้าถึงโหนดเป้าหมายได้ง่ายเพียงใด (มีประโยชน์ในการศึกษาชื่อเสียง หรือความสามารถในการรับของโหนด) ในขณะที่ค่าความใกล้ชิดขาออก (out-closeness) วัดว่าโหนดเป้าหมายสามารถเข้าถึงโหนดอื่น ๆ ได้ง่ายเพียงใด (มีประโยชน์ในการศึกษาความสามารถในการกระจายข่าวสาร)

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Freeman, L. C. (1979). Centrality in social networks: Conceptual clarification. Social Networks, 1(3), 215–239.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Bavelas, A. (1950). Communication patterns in task-oriented groups. Journal of the Acoustical Society of America, 22(6), 725–730.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว