Social Network Extraction dan Social Network Analysis dari Web
LAPORAN TUGAS AKHIR
Disusun sebagai syarat kelulusan tingkat sarjana
oleh : Maria Helena Iwo / 13503088
PROGRAM STUDI TEKNIK INFORMATIKA SEKOLAH TEKNIK ELEKTRO DAN INFORMATIKA INSTITUT TEKNOLOGI BANDUNG 2007
Lembar Pengesahan Program Studi Sarjana Informatika
Social Network Extraction dan Social Network Analysis dari Web
Tugas Akhir Program Studi Sarjana Informatika ITB
Oleh Maria Helena Iwo / 13503088
Telah disetujui dan disahkan sebagai laporan tugas akhir di Bandung, pada tanggal 31 Agustus 2007
Pembimbing
Ir. Dwi Hendratmo Widyantoro, M.Sc., Ph.D. NIP. 132084094
i
ABSTRAK Social network merupakan pola-pola interaksi sosial yang terjadi antar individu di dalam komunitas tertentu. Untuk mengungkapkan social network yang terjadi di dalam suatu komunitas, maka diperlukan Social Network Extraction (SNE) dari sumber data tertentu, misalnya dokumen web. SNE dapat dilakukan dengan menggunakan pendekatan web mining dan prinsip co-occurrence nama individu pada dokumen web hasil pencarian search engine. Penentuan jenis relasi antar individu dapat diselesaikan melalui teknik Text Classification (TC). Social network tersebut kemudian dapat dianalisis strukturnya dengan menggunakan berbagai metode statistik yang disebut Social Network Analysis (SNA). Penerapan SNA terdapat dalam bidang pemasaran, medis, dan sosiologi. Tugas Akhir ini bertujuan untuk melakukan SNE dari dokumen web dengan bantuan search engine Google serta melakukan analisis terhadap social network yang diperoleh. Teknik SNE yang diimplementasikan menggunakan properti Google hit dan Google top, serta kombinasi keduanya. Pada Tugas Akhir ini juga dikaji teknik TC sebagai bagian dari proses SNE. Algoritma TC yang dikaji adalah Naive Bayes dan Support Vector Machine (SVM). Melalui Tugas Akhir ini diharapkan akan didapatkan teknik SNE dan teknik TC yang memberikan performansi maksimum. Dari hasil eksperimen yang dilakukan, disimpulkan bahwa teknik SNE yang memberikan performansi maksimum sebesar 69,59% adalah teknik SNE yang menggunakan parameter Google top. Hal ini menunjukkan bahwa Google top lebih tepat dalam menentukan keberadaan relasi antara sepasang individu. Namun, akurasi yang didapatkan berbanding lurus dengan banyak dokumen dan relasi yang benar terdapat pada dokumendokumen awal hasil perankingan search engine. Selain itu, algoritma TC yang memberikan performansi maksimum sebesar 93.99% adalah SVM. SVM juga lebih tangguh daripada Naive Bayes dari segi feature selection. Walaupun demikian perbedaan performansi SVM dan Naive Bayes tidak signifikan. Kata kunci : social network, Social Network Extraction, Social Network Analysis, web mining, prinsip co-occurrence, search engine, Google top, Google hit, text classification, Support Vector Machine, Naive Bayes, feature selection.
ii
KATA PENGANTAR Puji syukur Penulis panjatkan ke hadirat Tuhan Yesus Kristus, karena atas kuasa dan kebaikanNya, Penulis dapat merampungkan Tugas Akhir yang berjudul “Social Network Extraction dan Social Network Analysis dari Web” dengan baik dan tepat pada waktunya.
Begitu banyak pihak yang turut berkontribusi sekaligus membantu Penulis baik secara langsung maupun tidak langsung dalam proses penyelesaian Tugas Akhir ini. Oleh karena itu, pada kesempatan ini Penulis mengucapkan terima kasih kepada: 1. Bapak Ir. Dwi Hendratmo Widyantoro, M.Sc., Ph.D sebagai Pembimbing Tugas Akhir yang telah banyak meluangkan waktu dan memberikan arahan, perhatian serta semangat selama pembuatan Tugas Akhir ini. 2. Ibu Henny Yusnita Zubir, B.S., M.T dan Bapak Ir. Rinaldi Munir, M.T yang telah bersedia memberikan masukan bagi Penulis pada saat review proposal, seminar, prasidang dan sidang Tugas Akhir. 3. Ibu Nur Ulfa Maulidevi, S.T, M.Sc selaku Wali Penulis yang bersedia ditanya pendapat dan diminta bantuan mengenai berbagai hal. 4. Papa dan Mama yang senantiasa memberikan doa, dorongan, semangat, dan dukungan dalam segala hal. 5. Darmawan Shi untuk segala dukungan, motivasi, dan bantuan yang selalu diberikannya sejak tahun pertama Penulis belajar di Teknik Informatika. Secara khusus, terima kasih untuk ide dasar dari Tugas Akhir ini. 6. Adik-adik Penulis, Hendrik dan Willi, terima kasih untuk segala doa dan bantuannnya, khususnya ketika harus mengantar dan menjemput Penulis selama mengerjakan Tugas Akhir ini. 7. Aku Ima untuk segala bantuannya sejak Penulis mendaftar ke ITB dan ketika Penulis sedang sakit. 8. Keluarga besar Penulis di Jakarta dan Maumere untuk segala doa dan dukungannya. 9. Rekan-rekan asisten Laboratorium Programming: Ronny, Ndan, Fahris, Uqi, CK, Dewi, dan Okta.
iii
10. Sahabat Penulis selama kuliah di Departemen Teknik Informatika ITB: Anna, Ira, Metta, Victor, Pendy, Jeffrey, Davis, Ong, Aulia, Adhit, Andri, Arie, Audi, Indi, Rika, Simon, Andoko, Satria, dan Krisantus. 11. Senior Penulis di Teknik Informatika ITB yang telah membantu selama kuliah: Peter, Ivan, Arya, Rayhan, Andri, Samuel, Dhara, JF, dan Ridho. 12. Teman-teman kos Kyai Gede Utama 28: Mbak Nia, Mbak Bita, Mbak Prita, Mbak Nancy, Mbak Mini, dan Bibi. 13. Staf pengajar Teknik Informatika ITB terutama Ibu Inge dan Ibu Wanti. 14. Staf Teknik Informatika ITB, terutama bagian dapur yang mau direpotkan ketika Penulis sedang mengejar deadline pengerjaan tugas-tugas kuliah. Terima kasih juga kepada Pak Rasidi, Pak Ade, Ibu Titi, Ibu Nur, Ibu Tita, dan Pak Maman 15. Seluruh teman-teman Informatika angkatan 2003 yang telah menemani selama empat tahun masa perkuliahan 16. Pihak lain yang tidak dapat disebutkan satu per satu.
Semoga Tugas Akhir ini dapat berguna khususnya bagi mereka yang tertarik dalam bidang social network. Penulis menyadari bahwa Laporan Tugas Akhir ini memiliki banyak kekurangan. Oleh karena itu Penulis mengharapkan kritik dan saran dari pembaca.
Bandung, Agustus 2005
Penulis
iv
DAFTAR ISI Lembar Pengesahan Program Studi Sarjana Informatika .......................................................... i ABSTRAK ....................................................................................................................................... ii KATA PENGANTAR .................................................................................................................... iii DAFTAR ISI .................................................................................................................................... v DAFTAR GAMBAR ..................................................................................................................... vii DAFTAR TABEL......................................................................................................................... viii DAFTAR ALGORITMA ............................................................................................................... ix DAFTAR SINGKATAN ................................................................................................................. x DAFTAR ISTILAH ....................................................................................................................... xi BAB I PENDAHULUAN ............................................................................................................. I-1 1.1 Latar Belakang ............................................................................................................... I-1 1.2 Rumusan Masalah .......................................................................................................... I-3 1.3 Tujuan ............................................................................................................................ I-3 1.4 Batasan Masalah ............................................................................................................. I-4 1.5 Metodologi ..................................................................................................................... I-4 1.6 Sistematika Pembahasan ................................................................................................ I-5 BAB II STUDI LITERATUR.....................................................................................................II-1 2.1 Teori Graf ...................................................................................................................... II-1 2.1.1 Definisi Graf .......................................................................................................... II-1 2.1.2 Jenis-Jenis Graf ..................................................................................................... II-2 2.1.3 Representasi Graf .................................................................................................. II-3 2.2 Social Network .............................................................................................................. II-6 2.2.1 Definisi Social Network ........................................................................................ II-7 2.2.2 Data Social Network ............................................................................................ II-10 2.2.3 SNA ..................................................................................................................... II-11 2.2.3.1 Ukuran-Ukuran pada SNA .............................................................................. II-11 2.2.3.2 Aplikasi SNA .................................................................................................. II-15 2.2.4 SNE dari Dokumen Web ..................................................................................... II-16 2.2.4.1 Teknik SNE dari Dokumen Web ..................................................................... II-17 2.2.4.2 Sistem SNE dari Dokumen Web ...................................................................... II-22 2.2.5 Perangkat Lunak Social Network ........................................................................ II-23 2.3 Text Classification ....................................................................................................... II-25 2.3.1 Klasifikasi............................................................................................................ II-25 2.3.2 Pemilihan Atribut Klasifikasi pada Text Classification ....................................... II-27 2.3.3 Algoritma Klasifikasi .......................................................................................... II-29 2.3.3.1 Naïve Bayes ..................................................................................................... II-29 2.3.3.2 SVM ................................................................................................................ II-31 2.3.3.2.1 SVM pada Linearly Separable Data ....................................................... II-31 2.3.3.2.2 Multi Class SVM ..................................................................................... II-33 BAB III METODE PEMBANGUNAN SOCIAL NETWORK ............................................... III-1 3.1 Analisis Teknik SNE .................................................................................................... III-1 3.1.1 Penentuan Keterhubungan antar Individu ............................................................ III-2 3.1.1.1 Pemilihan Parameter Google ............................................................................ III-2 3.1.1.2 Pemilihan Koefisien Co-occurrence ................................................................ III-5 3.1.1.3 Penentuan Threshold ........................................................................................ III-6
v
3.1.2 Teknik Text Classification untuk Penentuan Jenis Relasi Sosial.......................... III-7 3.1.2.1 Feature Selection untuk Representasi Dokumen Web ...................................... III-7 3.1.2.2 Penentuan Algoritma Klasifikasi ...................................................................... III-9 3.2 Algoritma Lintasan Terpendek ................................................................................... III-11 3.3 Contoh Perhitungan SNA ........................................................................................... III-13 3.3.1 Centrality ............................................................................................................ III-13 3.3.2 Betweenness ....................................................................................................... III-16 3.3.3 Closeness ............................................................................................................ III-18 3.3.4 Density................................................................................................................ III-19 BAB IV EKSPERIMEN SOCIAL NETWORK EXTRACTION ............................................. IV-1 4.1 Lingkungan Eksperimen...............................................................................................IV-1 4.2 Data ..............................................................................................................................IV-1 4.3 Prosedur Eksperimen ....................................................................................................IV-2 4.4 Pengukuran Performansi ..............................................................................................IV-4 4.5 Hasil .............................................................................................................................IV-4 4.6 Diskusi..........................................................................................................................IV-4 4.6.1 Pengaruh Threshold ..............................................................................................IV-4 4.6.2 Pengaruh Banyak Dokumen .................................................................................IV-9 4.6.3 Pengaruh Algoritma SNE ...................................................................................IV-10 BAB V EKSPERIMEN TEXT CLASSIFICATION .................................................................. V-1 5.1 Lingkungan Eksperimen................................................................................................ V-1 5.2 Data ............................................................................................................................... V-1 5.3 Prosedur Eksperimen ..................................................................................................... V-2 5.4 Pengukuran Performansi ............................................................................................... V-5 5.5 Hasil .............................................................................................................................. V-5 5.6 Diskusi........................................................................................................................... V-6 5.6.1 Pengaruh Pendekatan Feature Selection ............................................................... V-6 5.6.2 Pengaruh Penggunaan Stemming ........................................................................... V-8 5.6.3 Pengaruh Lingkup Dokumen ................................................................................. V-9 5.6.4 Pengaruh Algoritma Klasifikasi ............................................................................ V-9 BAB VI IMPLEMENTASI SOCIAL NETWORK ANALYSIS............................................... VI-1 6.1 Prosedur dan Hasil Implementasi .................................................................................VI-1 6.2 Diskusi..........................................................................................................................VI-9 6.2.1 Centrality ..............................................................................................................VI-9 6.2.2 Betweenness .........................................................................................................VI-9 6.2.3 Closeness ............................................................................................................VI-10 6.2.4 Density................................................................................................................VI-10 BAB VII PENUTUP ................................................................................................................. VII-1 7.1 Kesimpulan ................................................................................................................ VII-1 7.2 Saran ........................................................................................................................... VII-3 DAFTAR REFERENSI ................................................................................................................ xii DAFTAR PUSTAKA ................................................................................................................... xvi LAMPIRAN A DAFTAR NAMA INDIVIDU .......................................................................... A-1 LAMPIRAN B DAFTAR PASANGAN INDIVIDU................................................................ B-1 LAMPIRAN C HASIL EKSPERIMEN SOCIAL NETWORK EXTRACTION...................... C-1 LAMPIRAN D DAFTAR STOPWORD .................................................................................... D-1 LAMPIRAN E CONTOH HASIL PREDIKSI JENIS RELASI ............................................. E-1 LAMPIRAN F CONTOH FORMAT ARSIP MASUKAN PAJEK ........................................ F-1
vi
DAFTAR GAMBAR Gambar II-1 Graf G ....................................................................................................................... II-1 Gambar II-2 Graf (atas) dan Matriks Ketetanggaannya (bawah) .................................................. II-4 Gambar II-3 Graf (atas) dan Matriks Bersisiannya (bawah) ......................................................... II-5 Gambar II-4 Social Network pada Komunitas Ilmu Komputer ..................................................... II-9 Gambar II-5 Tahap Pembelajaran pada Proses Klasifikasi ......................................................... II-26 Gambar II-6 Tahap Klasifikasi pada Proses Klasifikasi .............................................................. II-26 Gambar II-7 Alternatif Bidang Pemisah .................................................................................... II-32 Gambar II-8 Bidang Pemisah Terbaik dengan Margin m Terbesar ........................................... II-32 Gambar II-9 Contoh Klasifikasi dengan Teknik One-against-one.............................................. II-34 Gambar III-1 Contoh Query untuk Satu Buah Nama ...................................................................III-3 Gambar III-2 Contoh Query untuk Dua Buah Nama ...................................................................III-3 Gambar III-3 Contoh Sociogram................................................................................................III-14 Gambar IV-1 Grafik Pengaruh Threshold pada Algoritma GoogleCoocHit ............................... IV-5 Gambar IV-2 Grafik Hasil Eksperimen Algoritma SNE ............................................................. IV-9 Gambar V-1 Grafik Eksperimen Pendekatan Feature Selection pada Naïve Bayes ..................... V-7 Gambar V-2 Grafik Eksperimen Pengaruh Stemming pada Naïve Bayes .....................................V-8 Gambar VI-1 Sociogram Hasil Algoritma GoogleCoocTop (k=20) ........................................... VI-2 Gambar VI-2 Sociogram Hasil Algoritma GoogleCoocTop (k=30) ........................................... VI-3 Gambar C-1 Hubungan Threshold terhadap Nilai r dan R pada GoogleCoocHit ......................... C-1 Gambar C- 2 Hubungan Threshold terhadap Nilai r dan R pada GoogleCoocTop ....................... C-2 Gambar C- 3 Grafik Hubungan Threshold terhadap Nilai r dan R pada GoogleTopHit ............... C-3 Gambar C- 4 Grafik Precision dan Recall pada GoogleCoocHit .................................................. C-3 Gambar C- 5 Grafik Precision dan Recall pada GoogleCoocTop ............................................... C-4 Gambar C- 6 Grafik Precision dan Recall pada GoogleTopHit .................................................... C-4 Gambar C- 7 Grafik Hubungan Nilai r dan R pada GoogleCoocHit ............................................. C-5 Gambar C- 8 Grafik Hubungan Nilai r dan R pada GoogleCoocTop ........................................... C-5 Gambar C- 9 Grafik Hubungan Nilai r dan R pada GoogleTopHit ............................................... C-6
vii
DAFTAR TABEL Tabel II-1 Sistem Software Network Extraction dari Dokumen Web .......................................... II-22 Tabel II-2 Perangkat Lunak Social Network ............................................................................... II-24 Tabel II-3 Kelompok Kata pada Polyphonet ............................................................................... II-28 Tabel II-4 Atribut Klasifikasi dan Nilainya pada Polyphonet ..................................................... II-29 Tabel II-5 Aturan Klasifikasi pada Polyphonet ........................................................................... II-29 Tabel II-6 Contoh 3 SVM Biner dengan Teknik One-against-one ............................................. II-34 Tabel III-1 Atribut Klasifikasi pada Tugas Akhir ......................................................................III-10 Tabel III-2 Sociomatrix untuk Sociogram Gambar III-3 ............................................................III-14 Tabel III-3 Centrality untuk Sociogram pada Gambar III-3 ......................................................III-15 Tabel III-4 Geodesic Setiap Pasangan Individu untuk Sociogram pada Gambar III-3 ..............III-15 Tabel III-5 Perhitungan Absolute Betweenness (“Andre”) .........................................................III-17 Tabel III-6 Betweenness untuk Sociogram pada Gambar III-3 ..................................................III-18 Tabel III-7 Perhitungan Absolute Closeness ("Andre")..............................................................III-18 Tabel III-8 Closeness untuk Sociogram pada Gambar III-3 .......................................................III-19 Tabel IV-1 Hasil Eksperimen Teknik SNE ................................................................................. IV-7 Tabel IV-2 Rata-Rata Precision dan Recall ................................................................................ IV-8 Tabel IV-3 Banyak Relasi (N) dengan Koefisien Co-occurrence >0 .......................................... IV-8 Tabel IV-4 Nilai r dan R ............................................................................................................. IV-8 Tabel V-1 Hasil Eksperimen Text Classification (a) .....................................................................V-6 Tabel V-2 Hasil Eksperimen Text Classification (b).....................................................................V-6 Tabel V-3 Hasil Eksperimen Text Classification (c) .....................................................................V-6 Tabel VI-1 SNA pada Sociogram Hasil Algoritma GoogleCoocTop (k=20).............................. VI-4 Tabel VI-2 SNA pada Sociogram Hasil Algoritma GoogleCoocTop (k=30).............................. VI-6 Tabel C-1 Daftar Threshold .......................................................................................................... C-2
viii
DAFTAR ALGORITMA Algoritma II-1 Algoritma Ekstraksi Nama Individu dari Dokumen Web ................................... II-17 Algoritma II-2 Algoritma Co-occurrence Menggunakan Google Hit ......................................... II-20 Algoritma II-3 Algoritma Co-occurrence Menggunakan Google Top........................................ II-20 Algoritma II-4 Algoritma SNE Menggunakan GoogleCoocHit .................................................. II-21 Algoritma II-5 Algoritma Klasifikasi Relasi Sosial .................................................................... II-22 Algoritma II-6 Algoritma Naive Bayes ....................................................................................... II-30 Algoritma III-1 Algoritma Kombinasi Google Top dan Google Hit ............................................III-5 Algoritma III-2 Algoritma Lintasan Terpendek .........................................................................III-11
ix
DAFTAR SINGKATAN Singkatan FOAF IDF IR SNA SNE SVM TF XML WWW
Kepanjangan Friend-Of-A-Friend Inverse Document Frequency Information Retrieval Social Network Analysis Social Network Extraction Support Vector Machine Term Frequency eXtensible Markup Language World Wide Web
x
DAFTAR ISTILAH Istilah Broker Coverage Inverse Document Frequency Networking Precision Recall Rule-of-thumb Search engine Social Capital
Stemming Stopword Term Frequency Test set Text Classification Threshold Training set Tupple Word-of-mouth Web mining
Definisi Penghubung antara dua buah kelompok dalam suatu jaringan sosial Cakupan Perbandingan banyak dokumen dalam koleksi dokumen dengan banyak dokumen yang mengandung kata tertentu Aktivitas menjalin dan mengembangkan relasi dengan pihak lain Perbandingan antara banyaknya objek yang benar dan dideteksi oleh sistem dengan jumlah total objek yang dideteksi oleh sistem Perbandingan antara banyaknya objek yang benar dan dideteksi oleh sistem dengan banyaknya objek yang benar pada koleksi objek Petunjuk praktis Mesin pencari Kemampuan seorang individu untuk mengumpulkan sumber daya atau potensi milik individu-individu lainnya melalui relasi-relasi sosial. Proses mengembalikan suatu kata ke bentuk dasarnya Kata yang tidak penting dan sering muncul dalam dokumen Banyaknya kemunculan suatu kata dalam suatu dokumen Koleksi data yang digunakan untuk tahap pengujian pada permasalahan klasifikasi proses klasifikasi yang diterapkan pada teks atau dokumen Ambang batas Koleksi data yang digunakan untuk tahap pembelajaran pada permasalahan klasifikasi Representasi sebuah objek dalam bentuk pasangan atribut dan nilai Secara lisan Proses penemuan informasi dari dokumen web
xi
