Analisis Dan Implementasi Community Detection Menggunakan Spectral Clustering Method Dalam Social Network

Abstract

Abstrak Twitter merupakan salah satu situs social network yang sedang berkembang dengan pesat dan memiliki lebih dari jutaan pengguna di berbagai belahan dunia pada saat ini. Salah satu penelitian mengenai social network adalah community detection. Community detection bertujuan untuk membagi jaringan ke dalam daerah – daerah pada graph. Pembentukan komunitas ini dapat dimanfaatkan untuk berbagai keperluan seperti menemukan target pemasaran produk, untuk menghitung kepopuleran suatu barang atau pengguna, mendeteksi isu di masyarakat, mendeteksi jaringan teroris, dan masih banyak lagi. Dalam penelitian kali ini akan digunakan suatu metode pendeteksian komunitas pada data Twitter yang bernama Spectral Clustering Method. Dimana metode ini mengelompokkan data dengan memetakan matriks afinitasnya (atau matriks similarity) ke matriks yang berisi vektor – vektor eigen (yang selanjutnya disebut ruang eigen). Yang kemudian akan dikelompokkan dengan menggunakan algoritma clustering dan akan dilakukan perhitungan nilai modularity untuk melihat hasil terbaik dari setiap pengelompokkan. Hasil dari sistem menunjukkan pengaruh dari jumlah k dan centroid terbaik dalam menentukan performansi algoritma Spectral Clustering dalam mendeteksi komunitas. Dari pengujian yang telah dilakukan, hasil terbaik yang diperoleh dengan menggunakan algoritma Spectral Clustering ialah dengan nilai modularity = 0.9607 untuk jumlah pengguna 90 user dengan jumlah sisi sebanyak 36 relasi dan jumlah cluster yaitu 7.

Kata kunci : Twitter, Community Detection, Spectral Clustering, Laplace, K-means, similarity

Abstract Twitter is one of the social network sites that are growing rapidly and has more than millions of users in various parts of the world at this time. One research on social network is community detection. Community detection aims to divide the network into regions on the graph. The formation of this community can be used for various purposes such as finding targeted product marketing, to calculate the popularity of a good or user, detecting issues in the community, detecting terrorist networks, and more. In previous research, community detection has not yet been able to provide information on how to get the best grouping results. In this research will be used a method of community detection called Spectral Clustering Method. Where this method groups data by mapping its affinity matrix (or matrix similarity) to a matrix containing eigenvectors (hereinafter called eigenspaces). Which will then be grouped by using clustering algorithm and will be calculated the value of modularity to see the best results of each grouping. The results of the system show the effect of the best number of k and centroid in determining Spectral Clustering algorithm's performance in detecting community. From the test that has been done, the best result obtained by using Spectral Clustering algorithm is with the value of modularity = 0.9607 for the number of users 90 users with the number of sides as much as 36 relations and the number of clusters is 7.

Keywords: Twitter, Community Detection, Spectral Clustering, Laplace, K-means, similarity