Sentralitas Antara Bobot
- Diperkenalkan oleh
- Opsahl, T.; Agneessens, F.; Skvoretz, J. (extending Freeman 1977 and Brandes 2001)
- Tahun
- 2010
- Jenis
- Centrality measure (path-based)
- Keluarga
- Network science
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Sentralitas Antara Bobot memperluas ukuran antara Freeman untuk graf berbobot tepi dengan merutekan jalur terpendek melalui transformasi yang dapat disetel dari bobot tepi.
Node yang berada di banyak jalur terpendek bernilai tinggi menerima skor tinggi, mengidentifikasi perantara dan jembatan dalam jaringan sosial, biologis, dan informasi di mana kekuatan ikatan penting.
Intuisi di balik metode
Bayangkan sebuah kota di mana jalan memiliki kapasitas lalu lintas yang berbeda. Persimpangan yang paling berpengaruh bukanlah hanya yang memiliki banyak jalan, tetapi yang terletak di rute tercepat atau berkapasitas tertinggi antara banyak pasangan lokasi. Sentralitas antara bobot menangkap hal ini secara tepat: ia menemukan node yang berfungsi sebagai titik relai penting, dengan memperhitungkan seberapa kuat atau lemah koneksi yang melewatinya. Node dengan sentralitas antara bobot tinggi adalah jembatan atau penjaga gerbang yang penghapusannya akan mengganggu banyak jalur kuat.
Sejarah
Sentralitas antara diperkenalkan oleh Linton Freeman pada tahun 1977 sebagai ukuran peran node dalam menghubungkan orang lain melalui jalur terpendek. Ulrik Brandes mengembangkan algoritma efisien penting pada tahun 2001 yang mengurangi komputasi dari O(n^3) menjadi O(n + m) waktu untuk graf tanpa bobot. Perluasan berbobot diformalkan secara sistematis oleh Opsahl, Agneessens, dan Skvoretz pada tahun 2010, yang mengusulkan transformasi bobot-ke-jarak yang diparameterisasi alfa dan memvalidasinya terhadap jaringan kolaborasi dan penerbangan empiris.
Kapan digunakan
Gunakan sentralitas antara bobot ketika bobot tepi mewakili kekuatan ikatan yang bermakna (frekuensi kontak, volume aliran, intensitas kolaborasi, kesamaan) dan Anda ingin mengidentifikasi perantara, penjaga gerbang, atau titik kegagalan tunggal dalam jaringan. Ini sesuai untuk jaringan sosial, jaringan kolaborasi, jaringan transportasi, dan jalur biologis di mana kekuatan koneksi membentuk rute mana yang sebenarnya digunakan. Hindari jika bobot tepi berisik atau sewenang-wenang — dalam kasus tersebut, sentralitas antara biasa lebih aman. Juga hindari untuk jaringan yang sangat besar (jutaan node) tanpa algoritma perkiraan, karena perhitungan yang tepat adalah O(n^3) dalam kasus terburuk.
Batasan dan pertimbangan
- Perhitungan yang tepat adalah O(n^3) dalam ruang dan waktu untuk graf padat, membatasi skalabilitas ke jaringan yang sangat besar.
- Hasil sensitif terhadap pilihan alfa; nilai yang berbeda dapat secara substansial mengubah peringkat node.
- Mengasumsikan bahwa informasi atau pengaruh mengalir hanya di sepanjang jalur geodesik (terpendek), yang mungkin tidak mencerminkan proses difusi yang sebenarnya.
- Bobot tepi negatif atau nol memerlukan penanganan khusus dan dapat merusak algoritma jalur terpendek.
- Jaringan yang terputus menghasilkan sentralitas antara yang tidak terdefinisi untuk pasangan di komponen yang berbeda, memerlukan analisis tingkat komponen.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menangkap perantara dan kontrol dalam jaringan di mana kekuatan ikatan menentukan jalur mana yang disukai.
- Parameter penyetelan alfa memungkinkan analis untuk memadukan logika jalur tanpa bobot dan jalur berbobot penuh, membuat ukuran tersebut dapat diadaptasi.
- Secara langsung mengidentifikasi node hambatan yang penghapusannya akan memfragmentasi atau memperlambat jaringan.
- Kompatibel dengan algoritma efisien Brandes, membuat perhitungan layak untuk jaringan dengan puluhan ribu node.
- Skor yang dinormalisasi dapat ditafsirkan di seluruh jaringan dengan ukuran yang berbeda.
- Berakar kuat dalam kerangka generalisasi yang ditinjau sejawat (Opsahl et al. 2010) dengan kutipan luas.
Penerapan
- Mengidentifikasi perantara pengetahuan dan penjelajah batas dalam jaringan organisasi dan kolaborasi.
- Menemukan node relai kritis dalam jaringan komunikasi atau rantai pasokan untuk analisis ketahanan.
- Menemukan bandara hub atau stasiun transit yang membawa sebagian besar lalu lintas antar kota dalam jaringan transportasi.
- Mendeteksi hambatan peraturan dalam jaringan interaksi protein atau regulasi gen.
- Menunjuk penyebar berpengaruh dalam model epidemi atau difusi informasi berbobot.
- Analisis perantara tingkat komunitas dalam jaringan kutipan dan penulisan bersama berbobot.
Cara kerjanya
Cara kerjanya
Bobot tepi dikonversi menjadi jarak menggunakan transformasi terbalik yang dikendalikan oleh parameter penyetelan alfa. Ketika alfa sama dengan nol, ukuran tersebut berkurang menjadi sentralitas antara standar tanpa bobot; saat alfa meningkat mendekati satu, ikatan yang lebih kuat diperlakukan sebagai jalur yang lebih pendek dan oleh karena itu lebih disukai, membuat ukuran tersebut sensitif terhadap kekuatan ikatan.
Rumus
d_{ij} = w_{ij}^{-\alpha}, \; \alpha \in [0,1]Algoritma Dijkstra (atau varian aljabar linear Brandes untuk efisiensi) menghitung himpunan jalur terbobot terpendek antara setiap pasangan node sumber dan target dalam jaringan, menggunakan jarak yang ditransformasi. Langkah ini mengidentifikasi rute mana yang optimal secara geodesik mengingat konfigurasi bobot.
Untuk setiap pasangan node berurutan, algoritma menghitung jumlah total jalur terbobot terpendek dan subset dari jalur tersebut yang melewati setiap node kandidat v. Hitungan ini diakumulasikan secara efisien menggunakan teknik propagasi balik Brandes, menjaga algoritma tetap dapat dilacak untuk jaringan yang berukuran sedang.
Untuk setiap node v, skor antara mentah adalah jumlah dari semua pasangan sumber-target dari fraksi jalur terpendek mereka yang merutekan melalui v. Node yang berada di semua jalur terpendek antara sepasang berkontribusi 1,0 pada skornya untuk pasangan itu; node yang dilewati oleh semua jalur berkontribusi 0.
Rumus
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}Skor mentah dibagi dengan nilai maksimum yang mungkin — yaitu (n-1)(n-2)/2 untuk jaringan tak berarah — sehingga skor berada dalam [0, 1] dan dapat dibandingkan di seluruh jaringan dengan ukuran yang berbeda. Untuk jaringan berarah, penyebutnya berlipat ganda menjadi (n-1)(n-2).
Rumus
C_B^{\text{norm}}(v) = \frac{C_B(v)}{(n-1)(n-2)/2}Kesalahan umum
- Menggunakan alfa default tanpa melaporkan atau membenarkan nilainya — selalu nyatakan dan benarkan pilihan alfa Anda.
- Memperlakukan skor mentah (tidak ternormalisasi) sebagai dapat dibandingkan di seluruh jaringan dengan ukuran yang berbeda.
- Mengabaikan arah tepi dalam jaringan berarah dan menghitung sentralitas antara tak berarah sebagai gantinya.
- Menafsirkan sentralitas antara yang tinggi sebagai pengaruh yang tinggi tanpa mempertimbangkan apakah aliran benar-benar mengikuti jalur terpendek dalam domain.
- Lupa memeriksa komponen yang terputus, yang secara artifisial menurunkan skor sentralitas antara untuk node di komponen yang lebih kecil.
Pertanyaan yang sering diajukan
Bagaimana cara memilih parameter alfa?
Alfa mengontrol seberapa besar bobot memengaruhi pilihan jalur. Pada alfa=0 Anda mendapatkan sentralitas antara klasik tanpa bobot; pada alfa=1 ikatan yang lebih kuat sepenuhnya mendefinisikan jalur terpendek. Praktik umum adalah menguji alfa=0, 0,5, dan 1 dan melaporkan sensitivitas. Jika peringkat node stabil di berbagai nilai, pilihan apa pun dapat dipertahankan; jika berbeda secara substansial, benarkan pilihan Anda secara teoritis berdasarkan apakah ikatan yang kuat harus lebih disukai.
Apa perbedaan antara sentralitas antara berbobot dan tanpa bobot?
Sentralitas antara tanpa bobot menghitung lompatan; setiap tepi memiliki panjang yang sama. Sentralitas antara berbobot menggunakan bobot tepi (dikonversi menjadi jarak) sehingga jalur lebih memilih koneksi yang lebih kuat atau lebih pendek. Dalam jaringan di mana kekuatan ikatan bermakna secara substantif — seperti frekuensi kolaborasi atau volume perdagangan — versi berbobot memberikan gambaran yang lebih akurat tentang node mana yang mengontrol aliran aktual.
Apakah sentralitas antara bobot cocok untuk jaringan yang sangat besar?
Perhitungan yang tepat menjadi mahal di atas kira-kira 100.000 node. Untuk jaringan yang sangat besar, gunakan algoritma perkiraan seperti pengambilan sampel pivot acak (diimplementasikan di NetworkX sebagai betweenness_centrality dengan parameter k) atau manfaatkan alat yang dipercepat GPU seperti cuGraph. Laporkan apakah Anda menggunakan perhitungan yang tepat atau perkiraan.
Bisakah saya menggunakan sentralitas antara berbobot ketika jaringan saya memiliki node terisolasi atau beberapa komponen?
Ya, tetapi node terisolasi akan selalu memiliki skor nol, dan node di komponen kecil akan memiliki skor berdasarkan jalur di dalam komponen mereka saja. Hitung sentralitas antara secara terpisah per komponen jika Anda menginginkan peringkat dalam komponen, dan laporkan struktur komponen bersama dengan skornya.
Bagaimana cara melaporkan sentralitas antara bobot dalam sebuah manuskrip?
Laporkan perangkat lunak dan versi yang digunakan (misalnya, NetworkX, igraph), nilai alfa, apakah skor dinormalisasi, bagaimana Anda menangani komponen yang terputus, dan statistik ringkasan (rata-rata, rentang) bersama dengan node berperingkat teratas. Plot sebar derajat versus sentralitas antara atau visualisasi jaringan dengan ukuran node sebanding dengan skor membantu interpretasi.
Metode terkait
Sumber
Opsahl, T., Agneessens, F., & Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks, 32(3), 245–251.
Buka referensi DOIDisalin.Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163–177.
Buka referensi DOIDisalin.