Perpustakaan Digital ITB

Aktivitas manusia pada layanan jejaring sosial online seperti Twitter, Facebook, Linkedin dan lainnya meningkat dewasa ini. Peningkatan aktivitas diiringi dengan peningkatan jumlah konten yang diproduksi oleh para pengguna layanan tersebut. Ekstraksi informasi dari jejak digital manusia yang berupa konten tersebut dapat digunakan untuk memahami perilaku manusia dan lingkungan sosialnya. Pada umumnya atribut data pada layanan tersebut tidak tersedia lengkap atau disebut sebagai data tidak terstruktur. Untuk itu diperlukan suatu metode yang bisa menangkap pola yang ada berdasarkan data tidak terstruktur tersebut. Salah satu dimensi data yang bisa diambil adalah data interaksi antar aktor. Bentuk interaksi antar aktor bisa berupa percakapan, pertemanan, pemanggilan ataupun yang lainnya. Data interaksi tersebut bisa dimodelkan berdasarkan teori graf, yang mana aktor direpresentasikan sebagai node dan interaksi antar aktor direpresentasikan dalam bentuk edge. Metode ini dinamakan sebagai Social Network Analysis (SNA). SNA sebagai suatu model jejaring sosial, mempunyai sekumpulan metrik untuk kuantifikasi suatu jejaring sosial. Salah satu metrik terpenting adalah keluarga metrik centrality yang digunakan untuk identifikasi aktor aktor yang paling berpengaruh pada suatu jejaring sosial pada konteks tertentu. Betweenness centrality (BC) mengidentifikasi pentingnya aktor berdasarkan seberapa sering aktor tersebut dilewati jalur terpendek alur informasi antar sembarang pasang aktor dalam jejaring sosial. Pertumbuhan pengguna dan konten layanan jejaring sosial online membentuk jejaring sosial skala besar yang mencapai jutaan node dan edge. Beberapa masalah muncul dengan adanya jejaring sosial skala besar tersebut, antara lain perhitungan metrik yang tidak scalable, kompleksitas visualisasi, identifikasi struktur inti, dan lain lain. Metrik BC merupakan salah satu metrik yang tidak scalable. Kompleksitas waktu perhitungan metrik BC sebesar O(n3), dengan n ada jumlah node di dalam jaringan. Dengan banyak bermunculannya jejaring sosial skala besar di sekitar kita, maka perhitungan metrik BC tersebut menjadi sangat mahal. Penelitian terkini untuk mereduksi proses perhitungan metrik BC selama ini berfokus pada usaha usaha untuk membuat metrik BC yang scalable, namun hal ini bukan merupakan pekerjaan yang mudah. Salah satu usaha yang dilakukan adalah memodifikasi algoritma sehingga tidak melibatkan semua node dan edge dalam perhitungan metrik. Salah satu algoritma yang paling penting dan dijadikan standard perhitungan metrik BC berdasarkan prinsip tersebut adalah algoritma Brandes, yang berhasil mereduksi kompleksitas waktu komputasi menjadi O(nm), dengan n adalah jumlah node dan m jumlah edge. Akan tetapi seiring bertambahnya ukuran jaringan maka waktu yang dibutuhkan untuk operasi tersebut masih tetap tinggi. Terdapat 3 kandidat skenario untuk mempercepat proses perhitungan metrik BC yaitu: memodifikasi algoritma metrik BC, menggunakan komputasi paralel, dan mereduksi ukuran input graf. Pada disertasi ini pilihan mereduksi ukuran input graf dipilih dengan alasan proses lebih scalable karena tidak terpaku oleh ukuran jejaring yang diproses, memperoleh informasi struktur inti dari jejaring sosial, dan struktur inti graf bisa digunakan untuk kepentingan lainnya. Dua pilihan proses reduksi input graf adalah graf ringkasan dan pemilihan sampel graf atau graph sampling (GS). Diantara kedua pilihan tersebut GS merupakan pilihan lebih cepat dan lebih murah dari pada proses membuat graf ringkasan berdasarkan prinsip enumerasi subgraf dalam menemukan motif graf. Kondisi terkini penelitian metode GS terdiri dari teknik teknik sampling graf menggunakan teknik pemilihan node secara acak, edge secara acak, dan teknik eksplorasi graf menggunakan prinsip random walk (RW). Metrik BC terdiri dari komponen yang menghitung rasio jalur terpendek dalam graf, sehingga untuk menjaga sifat jalur terpendek tersimpan dalam sampel graf, maka teknik GS yang digunakan adalah teknik RW. Pada umumnya teknik RW digunakan untuk mengambil sampel dari graf berdasarkan representasi nilai pengukuran tunggal (single value measurement (SVM)) atau nilai pengukuran distribusi (distribution measurement (DM)). Metropolis Hastings Random Walk (MHRW) dan Forest Fire (FF) adalah dua modifikasi teknik RW yang akurat dalam membuat sampel graf yang menjaga nilai SVM dan DM dari graf asli. Dalam kasus metrik BC yang termasuk dalam pengukuran peringkat (rank measurement (RM)) belum pernah ada klaim metode GS yang representatif. Dalam disertasi ini metode GS dibangun berdasarkan dua komponen utama yaitu: 1). Metode graph pruning (GP) yang berfungsi untuk mereduksi ukuran jejaring sosial secara cepat, dengan syarat jejaring sosial harus mengikuti distribusi power law. 2). Metode optimized random walk (ORW) yang berfungsi untuk mengambil sampel secara akurat yang mewakili populasi graf dan memastikan bahwa bagian graf yang terpilih merupakan bagian yang paling penting dalam menjaga sifat jalur terpendek pada graf. Metode GP adalah metode yang dikonstruksi sendiri pada disertasi ini, sedangkan metode ORW adalah modifikasi metode umum RW. Fungsi kedua metode tersebut saling melengkapi dalam membuat sampel yang representatif, oleh karena itu dibuat metode gabungan yang diberi nama Hybrid Graph Pruning – Optimized Random Walk (HGPORW). Pada metode Hybrid GPORW, metode GP bertindak sebagai langkah preprocessing dan metode ORW bertindak sebagai metode utama GS. Pada bagian akhir, dilakukan pengujian performansi metode Hybrid GPORW dalam hal kecepatan waktu pemrosesan dan akurasi peringkat metrik BC pada sampel graf. Metode ini juga diperbandingkan dengan metode konvensional RW, MHRW, FF, dan juga algoritma Brandes. Kesimpulan yang diperoleh bahwa metode Hybrid GPORW unggul dalam hal kecepatan waktu pemrosesan, sedangkan dalam hal akurasi peringkat metrik BC sepadan dengan metode sampling lainnya.