Analisis Dan Implementasi Algoritma Cnm-centrality Untuk Deteksi Komunitas Pada Dataset Facebook

Abstract

Abstrak Deteksi komunitas menjadi salah satu task dari social network analysis yang banyak dibahas. Hal ini disebabkan dengan pendeteksian komunitas tersebut dapat digunakan untuk berbagai hal seperti skema pemasaran produk, mendeteksi isu di masyarakat, dan sebagainya. Masalah dalam mendeteksi komunitas yaitu bagaimana cara mengelompokkan simpul yang baik untuk mengidentifikasi suatu kelompok. Salah satu algoritma untuk mendeteksi komunitas adalah CNMCentrality. CNM-Centrality merupakan algoritma Clauset-Newman-Moore yang dikombinasi dengan algoritma Pagerank. Algoritma Pagerank digunakan untuk menentukan simpul terpenting sedangkan algoritma CNM digunakan untuk mendeteksi komunitas. Algoritma ini dianggap algoritma dengan kecepatan running time yang baik dan nilai modularity yang baik pada pengujian sebelumnya. Namun, pada pengujian sebelumnya hanya menguji beberapa data saja seperti data jazz network dengan 198 simpul dengan relasi sebanyak 2742, belum diketahui bagaimana performansi algoritma CNM-Centrality jika menggunakan dalam jumlah yang besar. Algoritma CNM-Centrality mempunyai parameter yaitu damping factor. Damping factor merupakan parameter yang digunakan untuk menghitung nilai rank dan bernilai antara 0 sampai 1. Pada pengujian ini akan menggunakan dataset Facebook dengan tiga jenis damping factor yang berbeda untuk mengetahui pengaruh damping factor terhadap nilai modularity dan juga keandalan performansi algoritma CNM-Centrality untuk dataset Facebook. Penelitian ini bermanfaat untuk menilai apakah algoritma CNM-Centrality mempunyai nilai modularity dan running time yang baik dengan dataset yang berbeda dan damping factor yang berbeda. Hasil dari pengujian ini adalah nilai damping factor 0,15 memperoleh nilai rank tertinggi daripada dua damping factor yang diujikan. Namun, damping factor 0,85 memperoleh running time yang baik untuk menentukan simpul terpenting dan mendeteksi komunitas dibandingkan dua damping factor yang diuji. Selain itu, modularity terbaik yang dihasilkan pada pengujian ini adalah 0,8318 yang diperoleh oleh damping factor 0,85.

Kata kunci : Deteksi Komunitas, Algoritma CNM-Centrality, Damping factor, Modularity

Abstract Community detection becomes one of the tasks of social network analysis that is widely discussed because with the detection of the community can be used for various things such as product marketing schemes, detect issues in the community, and so forth. The problem in detecting communities is how to group good nodes to identify a group. One of the algorithms for detecting communities is CNM-Centrality. CNM-Centrality is a Clauset-Newman-Moore algorithm combined with Pagerank algorithm. Pagerank algorithm is used to determine the most important node while the CNM algorithm is used to detect the community. This algorithm is considered an algorithm with good running time speed and good modularity value in previous test. However, in the previous test only tested some data only, not yet known how CNM-Centrality algorithm performance if using in large amount. The parameter used in CNM-Centrality Algorithm is damping factor. Damping factor is a parameter used to calculate rank values and values between 0 and 1. In this test will use the dataset up with three different damping factor factor to determine the effect of damping factor on the value of modularity and also the reliability of CNM-Centrality algorithm performance for Facebook dataset . This research is useful to assess whether the CNM-Centrality algorithm has good modularity and running time values with different datasets and different damping factors. The result of this test is the damping value factor 0.15 obtains the highest rank value rather than the two damping factors tested. However, the damping factor of 0.85 obtains good running time to determine the most important node and detect the community over the two damping factors tested. In addition, the best modularity produced in this test is 0.8318 obtained by the damping factor of 0.85 Keywords: Community Detection, CNM-Centrality Algorithm, Damping factor, Modularity