Betweeness Centrality

ใช้หาว่าใครเป็นศูนย์กลางระหว่างสองกลุ่ม คำนวนได้จาก

C_b(v_i)=\displaystyle\sum_{s\neq t\neq v_i} \frac{\sigma_{st}(v_i)}{\sigma_{st}}

โดยที่ \sigma_{st} คือจำนวนของเส้นทางที่สั้นสุดระหว่างโหนด s ไปโหนด t ส่วน  \sigma_{st}(v_i)  คือจำนวนของเส้นทางที่สั้นสุดระหว่างโหนด s ไปโหนด t แต่ต้องผ่านโหนด v_i

ตัวอย่างfigure_1

จะได้พาททั้งหมดดังนี้

เช่นจะหา C_b(v_2) ทำได้โดย 2\times(\frac{\sigma_{13}(v_2)}{\sigma_{13}}+\frac{\sigma_{14}(v_2)}{\sigma_{14}}+\frac{\sigma_{15}(v_2)}{\sigma_{15}}+\frac{\sigma_{34}(v_2)}{\sigma_{34}}+\frac{\sigma_{35}(v_2)}{\sigma_{35}}+\frac{\sigma_{45}(v_2)}{\sigma_{45}}) สาเหตุที่คูณด้วยสองเพราะว่าเป็นกราฟแบบไม่มีทิศทางดังนั้นจึงมีพาทวิ่งกลับด้วย เช่น จาก 3 ไป 1 จาก 4 ไป 1 จาก 5 ไป 1 เป็นต้น ดังนั้นจะได้

2\sum_{s\neq t \neq v_{i},s<t} \frac{\sigma_{st}(v_i)}{\sigma_{st}}=2\times(\frac{1}{1}+\frac{1}{1}+\frac{2}{2}+\frac{1}{2}+0+0)=7

ถ้าจะเอาไปเทียบกับเครือข่ายสังคมอื่นๆต้อง normalize ก่อน โดยเอาไปหารด้วยค่า max สังเกตจากสมการด้านบนพจน์ที่ 4 หายไปครึ่งหนึ่ง พจน์ที่ 5 กับพจน์ที่ 6 ไม่มี ถ้ามีหมดจะได้ 6 คูณ 2 จะได้ 12  ค่า 12 นี้ก็คือ ทุกพาธจาก s ไป t วิ่งผ่านโหนด 2 หมดซึ่งเป็นค่า max เราเอาค่านี้ไปหาร 7 จะได้ประมาณ 0.5833 จะกล่าวสรุปได้ว่า เมื่อโหนด v_i อยู่ระหว่างเส้นทางที่สั้นที่สุดระหว่าง s กับ t ทุกคู่นั่นคือจะเท่ากับ 1 หรือ \forall(s,t),s\neq t \neq v_{i}\frac{\sigma_{st}(v_i)}{\sigma_{st}}=1 หรือถ้าหาได้ว่าจากโหนด s ไปโหนด t มีกี่คู่ก็ได้ หาได้จากสองเท่าของ combination มี n-1 โหนดเลือก 2 (หรืออีกชื่อไบโนเมียล)2\binom {n-1}{2}=2\times\frac{(n-1)!}{2!((n-1)-2)!}=\frac{(n-1)!}{(n-3)!}=\frac{(n-1)(n-2)(n-3)!}{(n-3)!}=(n-1)(n-2) ดังนั้นจะได้ว่า

C^{norm}_b(v_i)= \frac{C_{b}(v_i)}{2\binom {n-1}{2}} เช่น C^{norm}_b(v_2)= \frac{7}{12}\approx 0.5833

โค้ดโปรแกรม

ผลลัพธ์

สรุป โหนด 2 มีค่า betweeness centrality สูงสุด เป็นตัวเชื่อมระหว่างโหนดต่างๆมากสุด

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/smmPage 82-84
2.All shortest Path NetworkX Library at: http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.generic.all_shortest_paths.html
3.Betweeness Centrality NetworkX Library at: http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.centrality.betweenness_centrality.html#networkx.algorithms.centrality.betweenness_centrality

Leave a Reply

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