Perpustakaan Digital ITB

Pemrosesan pada graf berskala besar secara cepat telah menjadi topik penelitian yang banyak diminati pada beberapa domain seperti graph partitioning dan community detection. Penelitian ini membahas mengenai kinerja vertex-cut partitioning untuk pemrosesan deteksi komunitas pada graf berskala besar. Algoritma Fast Community Detection (FastCD) adalah algoritma deteksi komunitas berbasis modularity optimization yang mampu melakukan deteksi komunitas pada graf berskala besar. Deteksi komunitas pada graf berskala besar memerlukan teknik graph partitioning yang mempartisi graf berskala besar menjadi beberapa subgraf agar pemrosesan dapat dilakukan secara paralel, sehingga beban komputasi dapat didistribusikan ke seluruh mesin di dalam klaster komputer. Berbeda dengan pemrosesan data paralel secara konvensional, pemrosesan deteksi komunitas pada algoritma FastCD memerlukan informasi edge dan vertex tetangganya ketika dilakukan perhitungan nilai modularity partisi pada setiap vertex. Penelitian dilakukan pada graph parallel distributed framework yaitu GraphX yang merupakan komponen pemrosesan graf pada Spark. Strategi vertex-cut partitioning meliputi RandomVertexCut, CanonicalRandomVertexCut, EdgePartition1D, dan EdgePartition2D diterapkan pada algoritma FastCD untuk melakukan deteksi komunitas pada graf berskala besar secara paralel. Berdasarkan hasil eksperimen, kinerja masing-masing strategi vertex-cut partitioning untuk algoritma FastCD melakukan deteksi komunitas tergantung pada kondisi graf. Kinerja strategi vertex-cut partitioning pada algoritma FastCD dapat diukur dengan waktu pemrosesan deteksi komunitas, kecepatan deteksi komunitas, dan kualitas hasil deteksi komunitas. Strategi EdgePartition1D memiliki kinerja terbaik untuk algoritma FastCD melakukan deteksi komunitas secara paralel pada graf berskala besar dengan jumlah edge mencapai 7.600.595 dan jumlah vertex mencapai 685.230.