Perpustakaan Digital ITB

Structural holes adalah sekumpulan nodes dalam graf yang memegang peranan penting dalam menghubungkan nodes lainnya. Jika sekumpulan nodes tersebut dihapus dari graf, graf menjadi terputus. Untuk dapat mencari structural holes dalam graf yang besar, diperlukan cara untuk memroses yang efisien sehingga tidak memerlukan waktu dan memori yang banyak. Salah satu cara melakukan pencarian structural holes adalah dengan menggunakan Fiedler vector, eigenvector dari eigenvalues terkecil kedua dari representasi Laplacian matrix dari graf. Cara ini menggunakan memori yang banyak dan memiliki kompleksitas waktu keseluruhan yang kurang baik. Cara lain yang dapat digunakan adalah menggunakan betweenness centrality. Cara ini sudah memiliki implementasi yang paralel dengan GPU, memiliki kompleksitas waktu keseluruhan yang lebih baik dibandingkan cara sebelumnya, dan bisa bekerja dalam struktur data yang sparse, sehingga memungkinkan penggunaan memori yang lebih kecil. Cara kedua menggunakan betweenness centrality dipakai dalam Tugas Akhir ini. Teknik ini dipadukan dengan penggunaan compressed sparse row matrix sebagai penyimpan graf dalam program. Dalam pengujian, ditemukan pencarian menggunakan betweenness centrality dengan GPU menghasilkan waktu yang lebih cepat dan menggunakan memori yang lebih kecil dalam graf berukuran besar dibandingkan dengan pencarian menggunakan Fiedler vector. Pencarian menggunakan betweenness centrality dengan GPU lebih cepat dibandingkan dengan Fiedler vector dalam kasus graf dengan 250 nodes atau lebih. Dalam hal ukuran memori, betweenness centrality dengan GPU menggunakan memori yang lebih kecil dalam kasus graf dengan 500 nodes atau lebih.