Perpustakaan Digital ITB

Konektivitas merupakan salah satu parameter penting pada analisis graf, terutama pada graf jejaring sosial. Salah satu metrik mendasar untuk menganalisa konektivitas sebuah graf adalah segitiga. Segitiga dapat digunakan untuk menggambarkan seberapa erat hubungan antar personal dalam sebuah komunitas, dan juga menggambarkan usia atau kematangan sebuah komunitas. Menghitung dan mendaftar segitiga pada sebuah graf memiliki banyak implementasi dalam anal is is graf kompleks, tetapi algoritma untuk menghitung dan mendaftar segitiga memiliki kompleksitas yang tinggi. Sehingga menemukan metode komputasi yang optimal dan algoritma yang efisien menjadi isu penting. Telah banyak peneliti sebelumnya yang mengusulkan solusi terkait masalah di atas. Sebagian dari algoritma yang diusulkan memiliki kinerja yang baik untuk tipe dataset atau kasus tertentu. Sebagian algoritma ditujukan untuk menghitung dan mendaftar segitiga, dan sebagian lainnya ditujukan hanya untuk menghitung segitiga saja. Belum ada algoritma yang khusus ditujukan untuk menghitung dan mendaftar segitiga pada graf yang berdistribusi heavy-tailed, khususnya graf jejaring sosial. Pada penelitian ini, kami mengusulkan algoritma ComRo ( COMpute and RemOve ), untuk menghitung dan mendaftar segitiga lebih efisien pada grafyang berdistribusi heavy-tailed, khususnya jejaring sosial. Pandang kumpulan simpul yang memiliki derajat besar sebagai head dan simpul yang berderajat kecil sebagai tail. Algoritma ComRo terdiri dari tiga langkah yaitu: sorting (mengurutkan simpul dari derajat terbesar), compute (menghitung dan mendaftar) segitiga pada simpul derajat terbesar dan remove simpul tersebut secara berurutan sejumlah fl .n, dimana fl adalah estimasi proporsi simpul berderajat besar (head) yang harus dihapus, kemudian langkah terakhir adalah menghitung simpul yang tersisa (tail) sekaligus. Proses compute dan remove simpul pada langkah kedua akan mengurangi kompleksitas graf yang tersisa. Apalagi jika simpul yang dihapus adalah simpul yang memiliki derajat besar, tentu akan mengurangi jumlah iterasi dan waktu komputasi secara keseluruhan secara signifikan. Salah satu tantangan pada algoritma ComRo adalah bagaimana menentukan nilai p yang paling optimal. Nilai p diestimasi dengan melakukan eksperimen, yaitu menjalankan algoritma ComRo dengan menggunakan nilai p yang berbeda-beda, dimana 0 < P < 1. Secara umum nilai p bergantung kepada nilai kurtosis, derajat maksimum (dmax) graf, dan rata-rata derajat (dmean) graf. Untuk grafyang memiliki nilai kurtosis dan dmax besar, dan selisih antara dmax - dmean besar, maka nilai P terbaik adalah 0,1 sampai 0,2. Sedangkan untuk graflainnya nilai p terbaik adalah p > 0,4. Dan secara keseluruhan algoritma ComRo memiliki performansi yang lebih baik untuk graf berdistribusi heavy-tailed. Algoritma ComRo dievaluasi dengan menggunakan beberapa dataset dari graf jejaring sosial. Hasil eksperimen menunjukkan bahwa proses compute dan remove pada algoritma ComRo mengurangi kompleksitas dan jumlah iterasi secara keseluruhan. Algoritma ComRo memberikan kinerja yang lebih baik dibandingkan algoritma lainnya pada data yang berdistribusi heavy-tailed. Bahkan algoritma ComRo memberikan speed-up yang lebih signifikan untuk data berdistribusi extremely heavy-tailed.