Implementasi Algoritma Ulrik Brandes untuk Mencari Orang yang Paling Penting dalam Penyebaran Informasi pada Suatu Social Network

ABSTRAKSI: Saat ini interaksi manusia semakin meningkat dan meluas, jaringan sosial (social network) sebagai bentuk organisasi dari interaksi manusia tentunya semakin berkembang pula. Besarnya data social network ini menyulitkan kita untuk melakukan social network analysis (SNA), yaitu mempelajari social network untuk menangkap informasi penting yang ada didalamnya. Salah satu masalah SNA adalah mengetahui siapa orang yang paling penting dalam penyebaran informasi di suatu jaringan sosial. Masalah ini dapat diatasi dengan mengukur tingkat betweenness centrality (CB) setiap orang pada jaringan sosial tersebut. Perhitungan nilai betweenness centrality memakan waktu yang sangat lama untuk data social network yang sangat besar. Ada sebuah algoritma yang memiliki performansi waktu yang cepat dalam mengukur betweenness centrality, yaitu algoritma Ulrik Brandes. Pada tugas akhir ini dilakukan penerapan algoritma Ulrik Brandes untuk kasus pencarian orang yang paling penting dalam penyebaran informasi pada jejaring sosial iFACE IT Telkom. Selain itu, dilakukan perhitungan akurasi algoritma Ulrik Brandes dalam menentukan central node dan menghitung nilai CB setiap node pada suatu graf. Hasil pengujian menunjukkan bahwa Algoritma Ulrik Brandes memiliki tingkat akurasi sebesar 100% dalam menghitung nilai CB untuk setiap node di dalam unweighted graph dan dalam menentukan central node di dalam unweighted dan weighted graph. Hasil pengujian juga menunjukkan bahwa algoritma Ulrik Brandes mengutamakan jarak dibandingkan bobot sisi graf dalam perhitungan betweenness centrality sehingga nilai bobot sisi tidak mempengaruhi proses penentuan shortest paths.Kata Kunci : social network analysis, betweenness centrality, algoritma Ulrik BrandesABSTRACT: Nowadays, human interactions are increasing and expanding, social networks as a form of organization of human interaction certainly growing as well. The amount of these social networks’s data, make it difficult to perform social network analysis (SNA), which is studying the social network for capturing important information in it. One of the SNA’s problem is knowing who is the most important person in the dissemination of information in a social network. This problem can be overcome by measuring levels of betweenness centrality (CB) per person on these social networks. The calculation of betweenness centrality value takes a very long time for a very large social network data. There is an algorithm that has fast time performance in betweenness centrality measure, it is Ulrik Brandes algorithm. In this paper, Ulrik Brandes algorithm used to search the most important person in the dissemination of information on social network iFACE IT Telkom. Accuracy of Ulrik Brandes algorithm in determining the central node and calculates the value of CB for each node on a graph is measured in this paper. Test results show that Ulrik Brandes algorithm has accuracy rate 100% in calculating the value of CB for each node in the unweighted graph and in determining the central node in the unweighted and weighted graph. Test results also show that the algorithm prioritizes distance than weight of the graph in the calculation of betweenness centrality so that the weights do not affect the process of determining the shortest paths.Keyword: social network analysis, betweenness centrality, Ulrik Brandes algorith