ANALISIS JEJARING SOSIAL MENGGUNAKAN CLIQUE PARTITION BERDASARKAN ALGORITMA BRANCH AND BOUND SOCIAL NETWORK ANALYSIS USING CLIQUE PARTITION BASED ON BRANCH AND BOUND ALGORITHM

ABSTRAKSI: Twitter merupakan jejaring sosial yang cukup banyak diminati oleh masyarakat. Hubungan interaksi antar user dalam jejaring sosial tersebut dapat direpresentasikan dalam bentuk graf berbobot. Setiap node merepresentasikan user twitter dan sisi pada graf merepresentasikan interaksi antar user berupa reply to , mention, berdasarkan hubungan followed nya . User dan i nteraksi nya tersebut dapat direpresentasikan dalam graf berbobot. Pada penelitian tugas akhir ini dilakukan analisis dan implementasi metode Clique Partition untuk menganalisis jejaring sosial twitter. Algoritma yang digunakan dalam Clique Partition adalah algoritma branch and bound. Arah penelitian ini adalah untuk menguji algoritma branch and bound dalam pembentukan Clique Partition dan perangkingan menggunakan betweeness centrality dan subgraph centrality pada kasus jejaring sosial twitter. Tahap perfomansi penelitian ini meliputi preprocessing , proses pembentukan Clique Partition , penguk uran betweeness centrality , pengukuran subgraph centrality dan proses visualisasi. Selanjutnya akan ditunjukan hasil pengelompokan user pada jejaring sosial twitter tersebut.Percobaan dilakukan dalam 3 skenario. Skenario pertama bertujuan untuk menguji a lgortima branch and bound menggunakan beberapa jenis graf yang mewakili beberapa interaksi , dengan persentase kedekatan 90,9% . Skenario kedua melihat pengaruh banyak sisi berdasarkan density terhadapat waktu pen carían dan CP , hasil percobaan menunjukan bah wa density cukup berpengaruh terhadap waktu pencarian dan density berbanding terbalik dengan jumlah CP . Sedangkan skenario ketiga bertujuan untuk melihat pengaruh perubahan bobot terhadap anggota Clique Partition , dan berakibat pada berubahnya nilai betwee nness centrality ,subgraph centrality dan node antara graf . Dari hasil yang diperoleh dapat disimpulkan bahwa, perubahan interaksi mention, reply to cukup berpengaruh kepada perubahan anggota CP dan secara tidak langsung berpengaruh kepada perangkingan . Dat a pada skenario kedua didapa t dari NodeXL menggunakan kata pencarian ittelkom, dengan jumlah 540 user . Sedangkan pengujian data uji dijelaskan bahwa dengan da taset berjumlah 847 user yang di - download dari NodeXL graphgallery.orgKata Kunci : Clique Partiti on , branch and bound algorithm, social network analysis , betweeness centralit y , subgraph centrality.ABSTRACT: Twitter is a social media networking that quite demand by the public. The connection between the user interactions in social networks , can be r epresent in the form of a weighted graph. Each node represents the user of twitter and side of the graph represents a user interaction in the form of reply to, mention, based on the relationship of being followed. The u ser and the interaction can be repres ented in a weighted graph. In th is final Project , analysis and implementation of Clique Partition method will be conducted for analyzing twitter social networking . The a lgorithms that used in th is Clique Partition method is branch and bound algorithm. T he d irection of this study was to test the branch and bound algorithm in the formation of Clique Partition and ranking it using betweeness centrality and subgraph centrality in the case of twitter social networking . Perfoman ce phase of th is study include s preprocessing, the process of forming Clique Partition, betweeness centrality measurement, subgraph centrality measurement and visualization process. Furthermore , the results will be shown how the user grouping on the twitter social networking . The expe riments were conducted in 3 scenarios. The first scenario is aim ed to test the branch and bound algorithm , use s several type of graph that represent some interaction, with the proximity percentage is 90.9%. The second scenario saw the effect of a large num ber of sid e based on the density of the time search and CP , the experimental results showed that the density influence sufficiently on the search time and the density inversely proportional to the amount of CP . While the third scenario is aim ed to see the effects of weight s changing o n the members of Clique Partition, and this led to the change i n the value of betweenness centrality, subgraph centrality and between the graph nodes. From the results that have been obtained , it can be concluded that the chang ing interaction of mention , reply to , are influence sufficiently to change CP members and indirectly affect the ranking . The data in the second scenario are obtained by NodeXL using search words of ittelkom, with the number of user are 540 . While the testi ng data with the amount of 847 user dataset is downloaded from NodeXLgraphgallery.org.Keyword: Clique Partition, branch and bound algorithm, social network analysis, betweeness centrality, subgraph centrality