Perpustakaan Digital ITB

Model evolusi komunitas adalah model yang dapat digunakan untuk memahami dinamika interaksi berbagai komunitas dari waktu ke waktu. Model ini dapat diperoleh dengan melakukan deteksi evolusi komunitas pada graf. Sementara itu, perkembangan teknologi informasi telah mengakibatkan berbagai organisasi dapat menyimpan data dalam jumlah yang sangat besar, yang mengakibatkan munculnya fenomena graf berskala besar. Sejauh ini metoda yang sudah dikembangkan untuk mendeteksi evolusi komunitas baru mampu memproses graf dengan ukuran sekitar maksimal sekitar satu juta simpul. Oleh karena itu dibutuhkan metode deteksi evolusi komunitas untuk graf berskala besar. Penelitian-penelitian yang berkaitan dengan graf skala besar menunjukkan bahwa cara terbaik untuk memproses graf yang sangat besar adalah dengan memanfaatkan sistem terdistribusi, karena pada umumnya graf yang sangat besar membutuhkan memori yang sangat besar pula dan umumnya tidak mampu diproses dengan komputer tunggal dengan kapasitas memori yang tentunya terbatas pula. Berdasarkan studi awal penelitian ini, algoritma Facetnet adalah salah satu algoritma deteksi evolusi komunitas yang berpotensi untuk dikembangkan, karena memiliki kompleksitas algoritma linier sehingga dianggap cocok untuk memproses graf berskala besar, dan mampu menghasilkan model evolusi yang lengkap. Sehingga dipandang sangat bermanfaat untuk mengembangkan algoritma Facetnet ini agar dapat memproses graf yang sangat besar menggunakan sistem terdistribusi. Untuk dapat memproses graf berskala besar menggunakan sistem terdistribusi ada beberapa komponen yang harus dipenuhi yaitu, teknik untuk mempartisi graf serta algoritma yang dapat dijalankan secara paralel. Teknik mempartisi graf diperlukan, agar terbentuk sub graf yang lebih kecil sehingga dapat diproses secara paralel pada masing-masing komputer yang menjadi bagian dari sebuah sistem terdistribusi. Penelitian ini telah menganalisis teknik-teknik pemecahan graf dan menemukan teknik Vertex Cut adalah teknik yang tepat untuk dikombinasikan dengan algoritma Facetnet yang dimodifikasi skema iterasinya, sehingga menghasilkan algoritma Facetnet Paralel yang dapat dijalankan pada sistem terdistribusi. Namun dengan hanya memecah graf yang besar menjadi subgraf dan mengkombinasikan dengan algoritma Facetnet Paralel tidak cukup menjadi sebuah metoda yang mampu memproses graf yang sangat besar karena adanya matriks yang menyimpan nilai peluang keanggotaan sebuah simpul pada klaster yang ternyata juga berukuran sangat besar dan tidak dapat disimpan pada memori sebuah komputer saja. Penelitian ini juga telah berhasil menemukan representasi graf dengan simpul beratribut yang mampu mengatasi masalah ini. Dengan struktur graf yang memiliki simpul beratribut algoritma Facetnet Paralel tidak lagi perlu mendefinisikan atau menyimpan matriks ketetanggaan maupun matriks keanggotaan simpul pada klaster secara terpisah. Kedua matriks tersebut sudah dapat digantikan dengan subgraf-subgraf dengan simpul beratribut yang dapat disimpan secara paralel, sekaligus diproses secara paralel oleh algoritma Facetnet Paralel menggunakan memori lokal pada masing masing komputer pada sebuah sistem terdistribusi. Dengan demikian metoda deteksi evolusi komunitas menggunakan ketiga unsur penting tersebut mampu menghasilkan model evolusi komunitas untuk graf berskala besar. Keterbatasan memori pada sebuah komputer untuk memproses graf yang besar dapat diatasi dengan menambah komputer saja, tanpa perlu mengubah logika proses yang didefinisikan pada algoritma Facetnet Paralel. Sehingga untuk metoda ini diprediksi mampu memproses graf dengan jumlah simpul yang jauh lebih besar dari jutaan simpul bahkan sampai milyaran simpul. Penelitian ini juga menemukan bahwa Facetnet memiliki kelemahan, yaitu menentukan jumlah komunitas sebagai nilai tebakan di awal iterasi, sehingga menghasilkan model evolusi dengan jumlah komunitas yang sama dari waktu ke waktu. Hal ini tentunya kurang sesuai dengan kondisi riil yang memungkinkan perbedaan jumlah komunitas yang terkandung pada sebuah graf dari waktu ke waktu. Oleh karena itu telah dicoba untuk menghasilkan metoda penentuan banyaknya komunitas secara otomotis, yaitu menggunakan nilai Nulitas dari Matriks Laplacian dari Matriks Ketetanggaan (NML) graf yang dimaksud. NML terbukti mampu menunjukkan banyaknya komunitas yang terkandung pada sebuah graf secara otomatis, walaupun teknik ini belum dapat dikombinasikan dengan algoritma Facetnet Paralel karena masih perlu dikembangkan algoritma yang dapat menghitung nilai NML ini secara paralel menggunakan matriks ketetanggaan yang sudah dipartisi. Secara bertahap penelitian ini dimulai dari menganalisis berbagai metoda yang telah ada, menganalisis dan mendesain metoda usulan, melakukan eksperimen untuk menguji kemampuan metoda yang diusulkan hingga akhirnya dapat ditarik kesimpulan akan keberhasilan penelitian. Hasil eksperimen membuktikan metoda deteksi evolusi komunitas yang terdiri dari algoritma Facetnet Paralel menggunakan teknik Vertex Cut dan struktur graf dengan simpul beratribut mampu menghasilkan model evolusi komunitas dari graf yang berukuran hingga sekitar dua jutaan simpul dan 15 juta sisi menggunakan sistem terdistribusi berupa klaster Spark yang terdiri dari sembilan komputer. Hal ini sama artinya klaster Spark tersebut dapat memproses dengan maksimal 32 prosesor dan maksimal total memori worker sebesar 72 GB, karena masing-masing komputer memiliki empat buah prosesor dan 10 GB memori. Algoritma Facetnet Paralel terbukti merupakan algoritma yang memiliki skalabilitas tinggi, karena memiliki kompleksitas waktu yang linier. Berdasarkan eksperimen menggunakan infrastruktur klaster Spark yang ada dapat pula ditunjukkan bahwa setiap komputer mampu memproses graf yang nampaknya membutuhkan memori lebih besar dari total memori yang tersedia pada klaster, selama kebutuhan memori untuk memproses setiap sub graf tidak melebihi dari sekitar 55% dari memori pada masing-masing komputer.