Degree Centrality

เป็นการหาว่าโหนดที่เราสนใจมีความสำคัญเพียงใดใน Social Network โดยดูจากจำนวน degree หรือจำนวนเส้นที่เชื่อมต่อระหว่างโหนดที่เราสนใจกับโหนดอื่นๆ สำหรับกราฟไม่มีทิศทาง(undirected graph) ค่า degree centrality C_d สำหรับโหนด v_i คือ
C_d(v_i)=d_i
โดยที่ d_i คือ degree หรือจำนวน adjacent edge ของโหนด v_i
ถ้าเป็นกราฟแบบมีทิศทาง(directed graph) สามารถเลือกใช้ in-degree หรือ out-degree หรือใช้ทั้งสองร่วมกันก็ได้ โดย
C_d(v_i)=d^{in}_i   ใช้วัดว่าบุคคลนั้นเป็นคนที่ได้รับความนิยมเพียงใดใน Social Network
C_d(v_i)=d^{out}_i ใช้วัดว่าบุคคลนั้นเป็นคนที่ชอบเข้าสังคมเพียงใดใน Social Network
แต่ถ้าไม่สนใจทิศทางก็จะได้ C_d(v_i)=d^{in}_i+d^{out}_i ซึ่งจะเท่ากันกับ degree centrality ของกราฟที่ไม่มีทิศทาง

ถ้าจะเอาค่า degree centrality จากเครือข่ายสังคมหนึ่งไปเทียบกับเครือข่ายสังคมอีกอันหนึ่งจะยังเทียบไม่ได้ เช่นเทียบ twitter กับ facebook  ต้องทำการ normalization ก่อนซึ่งทำได้หลายวิธีดังนี้

  1. หารด้วยจำนวน degree ที่เป็นไปได้มากสุด C^{norm}_d(v_i)=\frac{d_i}{n-1} โดยที่ n คือจำนวนโหนด หรือ
  2. หารด้วยจำนวน degree ที่มากที่สุด C^{max}_d(v_i)=\frac{d_i}{max d_j} หรือ
  3. หารด้วยจำนวนผลรวมของ degree C^{sum}_d(v_i)=\frac{d_i}{\sum_{j} d_j}=\frac{d_i}{2|E|}=\frac{d_i}{2m} โดยที่ |E| หรือ m คือจำนวน edge

ตัวอย่างโปรแกรมหา Degree Centrality
figure_1

เป็นกราฟแบบไม่มีทิศทาง บรรทัดแรกที่ปรินท์คือค่าแบบยังไม่ได้ normalize ส่วนค่าบรรทัดต่อมาเป็นค่าเรียงตั้งแต่โหนด 1 – 8 เป็นค่าที่ nomalize แบบ  C^{norm},C^{max},C^{sum} ตามลำดับ

References
1.Social Media Mining: An Introduction.By Reza Zafarani, Mohammad Ali Abbasi, and Huan Liu.Cambridge University Press, 2014. Draft version: April 20, 2014.
Complete Draft and Slides Available at: http://dmml.asu.edu/smm Page 74-75
2.“Social Network Analysis for Startups by Maksim Tsvetovat and Alexander Kouznetsov (O’Reilly). Copyright 2011 Maksim Tsvetovat and Alexander Kouznetsov, 978-1-449-30646-5.” Page 46-48

Leave a Reply

Your email address will not be published. Required fields are marked *