Skip to content
Kembali ke hasil pencarian

Betweenness Centrality

Diperkenalkan oleh
Freeman, L. C.
Tahun
1977
Jenis
Centrality measure
Keluarga
Network science

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Betweenness centrality, yang diformalkan oleh Linton C. Freeman pada tahun 1977, mengukur seberapa sering sebuah node terletak pada jalur terpendek yang menghubungkan setiap pasangan node lain dalam sebuah jaringan.

Node dengan betweenness tinggi bertindak sebagai jembatan atau perantara: menghapusnya akan memfragmentasi jaringan menjadi komponen-komponen yang terputus secara lebih parah daripada menghapus node lain.

Intuisi di balik metode

Bayangkan jaringan jalan kota di mana semua rute lintas negara melewati satu persimpangan. Persimpangan itu memiliki betweenness maksimum meskipun hanya memiliki jumlah jalan yang sedang. Dalam jaringan sosial, seseorang yang secara rutin meneruskan informasi antara dua kelompok yang terputus satu sama lain menempati posisi yang sama: mereka mungkin tidak mengenal banyak orang secara langsung, tetapi mereka berada di jalur kritis yang menyatukan jaringan. Betweenness centrality mengukur peran perantara tersebut secara kuantitatif, terlepas dari jumlah koneksi mentah.

Sejarah

Linton Freeman memformalkan betweenness centrality dalam makalah landmarknya tahun 1977 di Sociometry, mengacu pada penggunaan konsep informal sebelumnya oleh Bavelas (1948) dalam eksperimen komunikasi. Formulasi Freeman menyatukan beberapa intuisi longgar tentang pentingnya node menjadi satu ukuran yang dapat dihitung dan menjadi definisi kanonik yang digunakan dalam ilmu jaringan. Algoritma Ulrik Brandes tahun 2001 mengurangi komputasi dari O(V^3) menjadi O(VE), membuat betweenness centrality praktis untuk jaringan dengan ribuan node dan memperkuat posisinya sebagai alat standar dalam perangkat lunak analisis jaringan sosial.

Kapan digunakan

Gunakan betweenness centrality ketika pertanyaan penelitian Anda berkaitan dengan perantara (brokerage), penjaga gerbang (gatekeeping), atau node jembatan — aktor yang penghapusannya akan mengganggu aliran informasi atau kohesi jaringan. Ini sesuai untuk graf berarah dan tak berarah, serta untuk graf berbobot di mana bobot tepi mewakili jarak atau biaya. Ini sangat berharga dalam jaringan komunikasi, jaringan kutipan, graf kolaborasi, dan rantai pasokan. Jangan gunakan sebagai satu-satunya ukuran sentralitas ketika perantara bukan fokus teoretis: degree centrality lebih sederhana dan cukup untuk pertanyaan konektivitas murni, dan eigenvector atau PageRank centrality lebih baik menangkap propagasi prestise. Hindari untuk jaringan renggang yang sangat besar tanpa implementasi yang efisien, karena komputasi naif adalah O(V^2 E).

Batasan dan pertimbangan

  • Mahal secara komputasi pada jaringan yang sangat padat bahkan dengan algoritma Brandes; algoritma perkiraan mungkin diperlukan untuk graf berskala web.
  • Mengasumsikan aktor menggunakan jalur terpendek, yang mungkin tidak realistis dalam jaringan di mana aliran melintasi rute yang lebih panjang (misalnya, jalan acak dalam jaringan listrik).
  • Sensitif terhadap tepi yang hilang atau berisik: bahkan beberapa ikatan yang tidak teramati dapat secara dramatis mengubah peringkat betweenness.
  • Memberikan bobot yang sama untuk semua jalur terpendek meskipun kapasitas tepi atau kekuatan hubungan sangat berbeda.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Menangkap peran perantara struktural dan jembatan yang sepenuhnya terlewatkan oleh degree dan eigenvector centrality.
  • Dapat diterapkan pada jaringan berarah, tak berarah, berbobot, dan tak berbobot dengan formula yang sama.
  • Skor yang dinormalisasi memungkinkan perbandingan node yang bermakna dalam satu jaringan dan antar jaringan dengan ukuran berbeda.
  • Algoritma Brandes membuat komputasi dapat dikelola untuk jaringan dengan jutaan node ketika diimplementasikan dalam pustaka yang dioptimalkan seperti NetworkX atau igraph.
  • Interpretasi teoretis yang kokoh: node dengan betweenness tinggi secara empiris dikaitkan dengan kontrol informasi, kekuasaan, dan lubang struktural dalam penelitian organisasi dan sosial.

Penerapan

  • Mengidentifikasi penjaga gerbang dan perantara informasi dalam jaringan komunikasi organisasi.
  • Mendeteksi node infrastruktur kritis dalam studi topologi transportasi, jaringan listrik, dan internet.
  • Menemukan penulis atau makalah perantara kunci dalam jaringan kutipan dan kolaborasi.
  • Memetakan lubang struktural dan posisi perantara dalam jaringan aliansi antar perusahaan.
  • Menemukan penyebar berpengaruh dalam model epidemiologi dan difusi rumor.
  • Memprioritaskan node untuk intervensi yang ditargetkan (misalnya, vaksinasi, gangguan) dalam penelitian kesehatan masyarakat dan keamanan.

Cara kerjanya

Cara kerjanya

1

Untuk setiap pasangan node berurutan (s, t) yang berbeda dalam jaringan, semua jalur terpendek (geodesik) di antara keduanya diidentifikasi. Untuk graf berbobot, jalur terpendek ditentukan oleh bobot tepi total minimum; untuk graf tidak berbobot, oleh jumlah lompatan (hop) paling sedikit. Langkah ini menetapkan semesta jalur di mana betweenness akan didistribusikan.

2

Untuk setiap pasangan (s, t), jumlah total jalur terpendek sigma(s, t) dihitung. Ketika ada beberapa jalur terpendek yang sama panjangnya, masing-masing dihitung secara terpisah. Penyebut ini mewakili total lalu lintas jalur terpendek antara s dan t tanpa batasan perutean.

Rumus
\sigma(s,t) = \text{number of shortest paths from } s \text{ to } t
3

Untuk setiap node kandidat v (di mana v bukan s maupun t), jumlah dari jalur terpendek sigma(s, t) yang benar-benar melewati v dicatat sebagai sigma(s, t | v). Rasio sigma(s, t | v) / sigma(s, t) memberikan fraksi lalu lintas jalur terpendek antara s dan t yang dirutekan melalui v.

Rumus
\sigma(s,t|v) = \text{shortest paths from } s \text{ to } t \text{ passing through } v
4

Fraksi-fraksi ini dijumlahkan di atas semua pasangan yang valid (s, t) untuk menghasilkan skor betweenness mentah C_B(v). Sebuah node yang penghapusannya akan memutuskan banyak jalur terpendek antar pasangan mengakumulasi jumlah yang tinggi, menandakan posisi perantara yang kritis secara struktural.

Rumus
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma(s,t|v)}{\sigma(s,t)}
5

Skor mentah tumbuh seiring ukuran jaringan, membuat perbandingan antar jaringan dengan ukuran berbeda menjadi tidak berarti. Normalisasi dengan (n-1)(n-2)/2 untuk graf tak berarah (atau (n-1)(n-2) untuk graf berarah) menskalakan ulang skor ke [0, 1], di mana 1,0 berarti node terletak pada setiap jalur terpendek dan 0 berarti node tidak terletak pada jalur mana pun. Brandes (2001) memperkenalkan algoritma O(VE) yang menghitung semua skor betweenness secara bersamaan daripada mengulang pencarian untuk setiap node.

Rumus
C_B^{\text{norm}}(v) = \frac{C_B(v)}{(n-1)(n-2)/2}

Kesalahan umum

  • Memperlakukan betweenness tinggi sebagai setara dengan degree tinggi tanpa memeriksa keduanya; node periferal dapat berperingkat pertama pada betweenness sambil berperingkat terakhir pada degree.
  • Membandingkan skor betweenness mentah (tidak dinormalisasi) antar jaringan dengan ukuran berbeda.
  • Mengabaikan arah tepi dalam jaringan berarah, yang dapat menghasilkan identifikasi perantara yang menyesatkan ketika aliran bersifat asimetris.
  • Menerapkan betweenness standar pada jaringan berbobot tanpa mengonfirmasi bahwa bobot tepi diinterpretasikan dengan benar sebagai biaya (bukan kesamaan) dalam algoritma jalur terpendek.
  • Mengabaikan metode betweenness perkiraan untuk jaringan besar dan menghentikan komputasi pada jutaan node.

Pertanyaan yang sering diajukan

Bagaimana betweenness centrality berbeda dari degree centrality?

Degree centrality menghitung koneksi langsung; hub dengan banyak ikatan mendapat skor tinggi. Betweenness centrality menghitung seberapa sering sebuah node terletak pada jalur terpendek antar node lain; jembatan yang menghubungkan dua kluster renggang mendapat skor tinggi meskipun memiliki sedikit ikatan langsung. Kedua ukuran tersebut menangkap aspek penting struktural yang ortogonal.

Haruskah saya menggunakan skor betweenness yang dinormalisasi atau mentah?

Gunakan skor yang dinormalisasi kapan pun Anda membandingkan node antar jaringan dengan ukuran berbeda atau menyajikan hasil kepada pembaca yang tidak terbiasa dengan skala jaringan Anda. Skor mentah dapat diterima hanya untuk perbandingan dalam satu jaringan tetap di mana penyebutnya konstan.

Bagaimana cara menangani tepi berbobot?

Atur bobot tepi untuk mewakili jarak atau biaya, bukan kesamaan. Sebagian besar implementasi (NetworkX, igraph) menerima parameter bobot yang diinterpretasikan sebagai jarak; jika bobot Anda mewakili kekuatan atau kesamaan, balikkan (misalnya, bobot = 1/kesamaan) sebelum menghitung betweenness.

Apakah betweenness centrality bermakna untuk jaringan yang terputus?

Untuk graf yang terputus, jalur terpendek antara node di komponen yang berbeda tidak terdefinisi (tak terhingga). Sebagian besar perangkat lunak memperlakukan pasangan tersebut sebagai kontributor nol terhadap jumlah, yang dapat menurunkan skor. Analisis setiap komponen terhubung secara terpisah atau gunakan varian seperti stress centrality dengan perlakuan eksplisit terhadap pasangan yang terputus.

Jaringan saya memiliki jutaan node — bisakah saya tetap menghitung betweenness centrality?

Perhitungan eksak dengan algoritma Brandes adalah O(VE) dan mungkin terlalu lambat. Gunakan perkiraan acak (misalnya, pengambilan sampel k node sumber) yang tersedia di NetworkX (betweenness_centrality dengan parameter k) atau pustaka graf seperti graph-tool, yang memberikan interval kepercayaan pada skor yang diperkirakan.

Metode terkait

Sumber

  1. Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40(1), 35–41.

    Buka referensi DOI
    Disalin.
  2. Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163–177.

    Buka referensi DOI
    Disalin.