Komputasi Betweenness Centrality dengan Algorithma Eksak dan Pendekatan

Abstract

Betweenness merupakan ukuran centrality berdasarkan pada lintasan terpendek yang banyak digunakan dalam analisis terhadap graf yang kompleks. Solusi eksak terbaik untuk menghitung betweenness centrality adalah O(nm) untuk graf tak berbobot dan O(nm+n² log n) untuk graf berbobot untuk jumlah vertex adalah n serta jumlah edge adalah m. Dalam dunia nyata dimana ukuran graf sangat besar perhitungan eksak akan menjadi sangat tidak fisibel. Untuk kondisi tersebut maka solusi pendekatan menjadi pilihan terbaik yang dapat dilakukan. Dalam paper ini akan dibandingkan solusi eksak dengan solusi pendekatan untuk menghitung betweennes centrality. Algoritma eksak yang digunakan adalah algoritma Brandes yang dieksekusi secara stand alone dan paralel serta algoritma pendekatan dengan teknik sampling yang adaptif untuk mengurangi secara signifikan perhitungan jumlah SSSP (single-source shortest path)?  untuk verteks-verteks yang mempunyai nilai centrality yang tinggi. Dari ketiga algoritma tersebut akan diberikan diskusi terkait dengan kinerja masing-masing dengan graf uji yang berbeda-beda. Untuk keperluan saat ini dan ke depan dibutuhkan algoritma dinamis dengan kompleksitas lebih baik.