Perpustakaan Digital ITB

Social network adalah sebuah struktur sosial yang terdiri dari sejumlah individu yang memiliki hubungan tertentu antar satu sama lain. Salah satu bentuk social network adalah Q&A network yang merepresentasikan hubungan antara seorang individu yang memberikan pertanyaan dengan individu lain yang menjawab pertanyaan tersebut. Pendekatan yang mengkaji tentang pengaruh seorang individu terhadap individu lainnya disebut social influence analysis. Algoritme social influence analysis dapat digunakan untuk menyelesaikan permasalahan influence maximization, yaitu menentukan kumpulan individu (seed node) yang memiliki influence tertinggi dalam sebuah social network. Dalam konteks Q&A network, mencari kumpulan individu ini dapat disamakan dengan expert finding dalam sebuah network. Algoritme yang paling baik untuk digunakan hingga saat ini adalah algoritme greedy yang memanfaatkan model linear threshold (LT) dan independent cascade (IC). Namun, waktu komputasi algoritme greedy sangat lama. Untuk mempersingkat waktu komputasi, telah dikembangkan algoritme alternatif yang memanfaatkan model LT dan IC yaitu algoritme LDAG dan algoritme NewGreedyIC (NGIC) . Pada tugas akhir ini, dilakukan implementasi algoritme LDAG dan algoritme NGIC untuk menyelesaikan permasalahan influence maximization pada Q&A network. Dari hasil eksperimen algoritme LDAG dan NGIC terhadap beberapa dataset Q&A network, didapatkan hasil berupa waktu komputasi dan nilai influence spread yang dicapai oleh kedua algoritme. Dari segi nilai influence spread dan waktu komputasi, algoritme NGIC mendapatkan hasil yang lebih baik daripada algoritme LDAG. Untuk pengembangan kedua algoritme lebih lanjut, terdapat potensi untuk diimplementasikan secara paralel sehingga mempersingkat waktu komputasi yang dibutuhkan. Selain itu, dapat dilakukan pula pengembangan dengan menggabungkan algoritme-algoritme ini dengan teknik network analysis lainnya seperti clustering dan community detection.