PERANCANGAN DAN PEMBUATAN PERANGKAT LUNAK PENELUSUR WEB (WEB CRAWLER) MENGGUNAKAN ALGORITMA PAGERANK

PROSIDING SEMINAR NASIONAL TEKNOLOGI INFORMASI DAN APLIKASINYA Institut Teknologi Sepuluh Nopember Surabaya, 3 April 2003

PERANCANGAN DAN PEMBUATAN PERANGKAT LUNAK PENELUSUR WEB (WEB CRAWLER) MENGGUNAKAN ALGORITMA PAGERANK Budianto, Agus Zainal Arifin, Suhadi Lili Jurusan Teknik Informatika, Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember (ITS) – Surabaya Kampus ITS, Jl. Raya ITS, Sukolilo-Surabaya 60111 Tel. +62 31 5939214, Fax + 62 31 5939363 [email protected], agusza,[email protected]

Abstrak Makalah tersebut menguraikan tentang bagaimana web crawler menelusuri dokumen-dokumen yang dianggap penting terlebih dahulu dalam suatu struktur web di sekitar ITS seperti tc.its-sby.edu dan its.ac.id sebagai dataset. Web crawler melakukan penelusuran dengan model ‘Crawl and Stop with Threshold’. Hasil uji coba menunjukkan bahwa web crawler yang dilengkapi dengan metode penelusuran yang sesuai dengan struktur dokumen-dokumen dalam web akan memperoleh dokumen-dokumen yang penting lebih cepat dibanding dengan web crawler yang tidak dilengkapi. KATA KUNCI: web crawler, information retrieval, web mining, web spider, PageRank, and link analysis.

1. PENDAHULUAN World Wide Web merupakan salah satu sumber informasi yang dapat diakses dengan mudah. Informasi tersebut disimpan dalam suatu file dengan nama yang unik dalam suatu direktori yang unik pula dalam suatu situs yang diindentifikasi dalam nomor IP address atau alamat Uniform Resource Locator (URL)[5]. Seorang pengguna internet perlu mengingat setiap URL-URL yang penting baginya. Karena jumlah yang sangat banyak, maka tidak mungkin seorang user mengingat alamat-alamat tersebut. Salah satu solusinya adalah dengan membangun sebuah daftar indek dari alamat URL-URL tersebut. Mesin pencari (search engine) merupakan salah satu alat yang mengunakan teknik tersebut [6]. Bagian penting dari sebuah mesin pencari adalah web crawler. Web crawler merupakan program yang mengumpulkan informasi yang akan ditempatkan pada basis data. Sebuah web crawler bertugas menelusuri web dan mengumpulkan dokumen-dokumen di dalamnya. Selanjutnya web crawler akan mengurutkan dokumen-dokumen tersebut dan membangun sebuah daftar indeknya. Tujuan pengurutan tersebut adalah untuk menentukan seberapa penting suatu dokumen dan untuk Kerjasama antara Lemlit dan PIKTI ITS

menduga URL-URL yang mungkin penting sehingga URL tersebut perlu ditelusuri terlebih dahulu[2]. Sejumlah metode penelusuran berkaitan dengan pengurutan tersebut antara lain adalah breath first search(BFS) dan depth first search(DFS). Pada BSF, web crawler akan menelusuri dokumen-dokumen global terlebih dahulu. Kemudian web crawler akan mengunjungi dokumen-dokumen yang bersifat lokal yang terdapat pada sebuah kelompok tertentu saja[2]. Sedangkan pada metode penelusuran DFS, web crawler akan menelusuri dokumendokumen yang bersifat lokal terlebih dahulu. Kemudian web crawler akan menelusuri dokumen-dokumen pada situs la in. Salah satu contoh metode penelusuran seperti ini adalah penelusuran berdasarkan banyaknya jumlah backlink. Berbeda dengan kedua metode penelusuran diatas, penelusuran berdasarkan nilai PageRank mempunyai sifat BFS dan DFS. Dimana pola penelusurannya tergantung dari kualitas dokumen-dokumen bukan berdasarkan jumlah backlink[2]. Dengan menggunakan PageRank, diharapkan sebuah web crawler akan mengunjungi dokumen-dokumen penting terlebih Paper 19 - 1


dahulu sehingga penelusuran akan efisien dan efektif. Pada Makalah ini akan diuraikan bagaimana web crawler menelusuri URL-URL yang diketahuinya berdasarkan algoritma PageRank[9]. 1.1 Dasar Teori Perkembangan dunia Teknologi melahirkan sebuah cabang ilmu pengetahuan yang dikenal dengan nama information retrieval[10]. Sebelum informasi retrieval digunakan pada web, ilmu ini sudah digunakan di perpustakaan oleh seorang pustakawan. Pencarian informasi pada sistem ini didasarkan pada analisa kata (content-based analysis). Berbeda dengan perpustakaan, web selalu berubah setiap saat. Seorang pengguna web perlu mencari informasi melalui mesin pencari (search engine) yang menggunakan algoritma tidak hanya berdasarkan kata (contentbased analysis), tetapi juga berdasarkan analisa hyperlink (hyperlink analysis) dan analisa bahasa bermarkup (markup language analysis). Hyperlink antara 2 dokumen A dan B pada web berarti bahwa dokumen A mengacu pada dokumen B. Hubungan tersebut tentu mempunyai makna tertentu bagi penulis dokumen A. Penulis dokumen A tentu memberikan link yang mengacu pada dokumen B yang berisi informasi yang berguna bagi pembaca dokumen A. Analisa Hyperlink sangat penting di dalam menentukan tingkat kualitas suatu dokumen yang dicari oleh seorang user. Analisa Hyperlink Analisa hyperlink merupakan suatu analisa yang didasarkan pada hubungan antara dokumen yang satu dengan dokumen yang lain. Karena web merupakan kumpulan dari dokumendokumen yang tersebar dan saling berhubungan melalui suatu link, maka analisa hyperlink dapat digunakan untuk menentukan kualitas suatu dokumen. Ada 2 kegunaan utama analisa hyperlink dalam bidang information retrieval yaitu untuk penelusuran (crawling) dan ranking.

yang terdapat pada dokumen-dokumen dalam suatu koleksi web. Ada 2 jenis dari Connectivity-Based Ranking yaitu: 1. query-independent ? ranking yang bersifat bebas dan memberikan nilai pada dokumen secara bebas dari pengaruh query yang diberikan. 2. query-dependent ? ranking yang bersifat tidak bebas dan nilai pada dokumen bergantung pada query yang diberikan. Query-Independent Ranking Beberapa metode pengukuran yang digunakan untuk menilai kualitas dokumen berdasarkan hubungannya diantaranya sebagai berikut: 1. Back link Count ? Pada pengukuran tersebut, suatu dokumen dinilai berdasarkan jumlah dokumen yang mengacu kepadanya. 2. Forward link Count ? Pada pengukuran tersebut, suatu dokumen dinilai berdasarkan jumlah link yang ada pada dokumen tersebut. 3. Page Rank ? Pengukuran tersebut merupakan turunan dari back link count dimana suatu dokumen dinilai berdasarkan persamaan rumus (1).

IR( p) ? (d ? 1) ? d[

IR(t1) IR(tn ) ? ...? ] …..(1) c1 cn

IR(p) ?nilai pentingnya suatu dokumen. d ? dumping factor (0
1.2 Perancangan Web Crawler web crawler merupakan program yang digunakan untuk menelusuri dokumen yang ada di internet. Untuk memperoleh sebuah dokumen, sebuah crawler membutuhkan URL sebagai inisial awal p0 . Crawler akan mendapatkan p0 , mencari URL yang ada didalamnya dan memasukkan dalam sebuah antrian URL yang akan diamati. Cara kerja sebuah crawler secara sederhana dapat ditulis pada algoritma dibawah ini: Algoritma Crawler

Connectivity-Based Ranking Connectiivity-Based ranking merupakan ranking terhadap dokumen-dokumen dalam web berdasarkan hubungan-hubungan berupa link

Input : AllURLs ? Kumpulan URL-URL yang diketahui CollURLs ? Kumpulan URL-URL yang tersimpan Prosedur: While (true)

Kerjasama antara Lemlit dan PIKTI ITS

Paper 19 - 2

PROSIDING SEMINAR NASIONAL TEKNOLOGI INFORMASI DAN APLIKASINYA Institut Teknologi Sepuluh Nopember Surabaya, 3 April 2003 URL ? SelectToCrawl(AllURLs) page ? Crawl(URL) if (URL ? CollURLs) update(URL, page) else tmpURL?selectToDiscard(CollURLs) Discard(tmpURL) Save(URL,page) CollURLs?(CollURLs-tmpURL)? URL newURLs ? extractURLs(page) AllURLs ? AllURLs ? newURLs

Secara garis besar arsitektur web crawler terdiri atas 3 buah koleksi (AllURLs, CollURLs, dan Collection) dan 4 buah modul (Order Module, SelectToDiscard Module, Save Module, Crawl Module) seperti terlihat pada gambar III.1. Garis dan anak panah menunjukkan aliran data antara module dan label yang terdapat diatasnya menunjukan nama fungsi atau kelas yang dipanggil. Kedua koleksi AllURLs dan CollURLs mengelola data yang hampir sama yaitu alamat URL. Bedanya pada AllURLs tersimpan semua alamat URL-URL yang telah diketahui, sedangkan CollURLs menyimpan semua URL yang terdapat pada Collection. URL-URL yang terdapat pada AllURLs dipilih oleh Order Module. Secara konstan Order Module mengamati URL-URL yang terdapat pada koleksi AllURLs, CollURLs, dan Collection untuk melakukan usaha perbaikan dokumendokumen yang terdapat pada koleksi. Sepintas dapat dikatakan bahwa jika sebuah crawler menggunakan metode PageRank sebagai importance metric, maka Order Module akan mengevaluasi semua URL-URL yang terdapat pada koleksi AllURLs berdasarkan nilai PageRank. Ketika sebuah dokumen yang tidak berada pada CollURLs berubah menjadi lebih penting dari dokumen yang terdapat pada CollURLs, maka SelectToDiscard module dan Save Module akan membuang dokumen dalam CollURLs yang tidak penting dan menggantinya dengan dokumen baru.

Jadi Order Module digunakan sebagai refinement decision sedangkan SelectToDiscard module dan Save Module digunakan sebagai update decision. Secara konstan Crawl Module menelusuri dokumen dan menyimpan ke dalam CollURLs. 2. UJI COBA Sejumlah uji coba dilakukan pada sejumlah dataset dengan nilai parameter dan metode yang berbeda-beda. UjiCoba tersebut dilakukan dengan 2 macam pengukuran yaitu : BackLink metric dan PageRank metric. Keterangan tentang Dataset Dataset yang digunakan di dalam uji coba tersebut diperoleh dari intranet di sekitar ITS yaitu its-sby.edu dan its.ac.id. Dalam penelusuran dokumen tersebut semua URL yang merujuk pada dokumen di luar its-sby.edu akan diabaikan. Disamping itu juga beberapa data yang dianggap tidak valid juga diabaikan seperti data pada direktori book pada se.its-sby.edu yang berisi buku-buku online dan belajarweb yang terdapat pada se.its-sby.edu yang berisi daftar file mahasiswa. Important Metric Jika suatu dokumen p mempunyai important metric I(p), maka I(p) suatu dokumen pada uji coba ini ditentukan dengan BackLink Count dan PageRank. Definisi Dokumen Penting Uji coba tersebut menggunakan model Crawl and Stop with Threshold. Pada model Crawl and Stop with Threshold, diasumsikan crawler telah mengunjungi sejumlah K dokumen kemudian berhenti. Sebuah target sebesar G yang telah ditentukan terlebih dahulu digunakan sebagai threshold. Jika sebuah dokumen mempunyai nilai I(p) ? G, maka dokumen tersebut dikatakan penting. Nilai G dapat bervariasi tergantung dari pengukuran yang digunakan. Dalam uji coba ini digunakan sejumlah target G yang berbeda-beda untuk masing-masing pengukuran. Untuk backlink metric digunakan target G sebesar 3 dan 10. Sedangkan untuk PageRank metric digunakan target G yang lebih kecil sebesar 0.5, 1, dan 3.

Gambar III.1. Arsitektur Web Crawler. Kerjasama antara Lemlit dan PIKTI ITS

Paper 19 - 3


Pengukuran Kinerja Web Crawler Kinerja web crawler diukur dengan mencari nilai Pst (C) dan P(C). Pst (C) merupakan persentase antara jumlah halaman penting (h) yang telah ditelusuri saat web crawler berhenti dengan jumlah seluruh halaman penting yang terdapat pada web (H). Persamaan tersebut dapat dilihat pada rumus 2. Tentu saja nilai H tidak dapat ditentukan sebelum seluruh dokumen telah ditelusuri. Sedangkan jumlah halaman penting (h) pada uji coba ini ditentukan setiap 10 dokumen ditelusuri. Dengan kata lain crawler akan berhenti sejenak setelah mengunjungi 10 dokumen untuk menghitung jumlah halaman penting yang telah diperoleh sejauh ini. Sedangkan P(C) merupakan persentase antara jumlah halaman yang telah ditelusuri saat crawler berhenti(c) dengan jumlah seluruh dokumen yang terdapat pada web (C). Persamaan ini dapat dilihat pada rumus 3.

h …………….….(2) H c P ( C) ? …………………(3) C Pst ( C) ?

Pada uji coba yang dilakukan tersebut, kinerja crawler ini digambarkan dalam bentuk grafik. Dimana sumbu x merupakan nilai P(C) dan sumbu y merupakan nilai dari P st (C) yang bersesuaian. Jadi awal grafik akan dimulai dari 0% dan berakhir pada 100%. Grafik hasil uji coba akan digunakan untuk mengukur kinerja suatu crawler dengan dua metode yaitu PageRank dan BackLink. Crawler yang mampu menelusuri dokumendokumen penting lebih dahulu merupakan crawler yang mempunyai kinerja lebih baik. Uji Coba dengan BackLink Metric Pada BackLink metric tersebut, sebuah dokumen dianggap penting jika dokumen tersebut mempunyai jumlah backlink lebih besar dari target yang telah ditetapkan. Perhitungan BackLink metric/IB(p) membutuhkan struktur web secara lengkap. Selama proses penelusuran, crawler hanya dapat menghitung nilai IB’(p) yang merupakan jumlah backlink yang dapat dihitung sampai saat ini.

Tanggal percobaan Dataset Jumlah Doc Jumlah URL tidak valid Lama Pengukuran %Hot Page Target G

17 Oktober 2002 tc.its-sby.edu 194 46 10 39% (76) 3

Tabel V.1. memperlihatkan keterangan tentang percobaan tersebut. Dari tabel ini diperoleh keterangan bahwa jumlah dokumen valid yang disimpan di dalam koleksi sampai akhir penelusuran adalah 194 dokumen. Sedangkan jumlah dokumen yang tidak valid adalah 46 dokumen. Sedangkan lama pengukuran 10 menunjukkan bahwa pengukuran dari sampel tersebut dilakukan setiap 10 dokumen baru ditelusuri. Dengan menggunakan target G = 3, maka pada akhir penelusuran jumlah dokumen penting adalah 39% dari jumlah dokumen yang telah ditelusuri. Tabel V.2. Tabel Perbandingan Backlink dan PageRank 0.3. %Hot PageRank %Hot 0.3(x) BackLink(y) ?(x-y) ?(x-y)/y 11 11 0 0 12 12 0 0 17 18 -1 -7.1429 17 18 -1 -7.1429 22 20 3 13.333 28 24 4 16.667 32 25 7 26.316 45 29 16 54.545 46 29 17 59.091 55 29 26 90.909 55 29 26 90.909 58 33 25 76 70 43 26 60.606 72 53 20 37.5 79 66 13 20 92 75 17 22.807 93 86 8 9.2308 97 97 0 0 100 100 0 0 %Peningkatan : 30

Percobaan pada tc.its-sby.edu (target G=3) Tabel V.1. Dataset tc.its-sby.edu hasil penelusuran dengan backlink metric dengan target G sebesar 3 Kerjasama antara Lemlit dan PIKTI ITS

Paper 19 - 4


BackLink vs PageRank

Clu

100

Clu

90 80

% Hot

70 60 50

Gambar V.2. Urutan penelusuran dengan Backlink ordering. Garis putus-putus berarti belum ditelusuri, sedangkan garis lurus berarti sudah ditelusuri.

40 30 20 10

BackLink PageRank 0.95 PageRank 0.8 PageRank 0.3

98

88

77

67

57

46

36

26

15

5

0

% Crawled

Gambar V.1. Grafik BackLink vs PageRank dengan dumping factor 0.95 0.8 0. 3 pada dataset tc.itssby.edu dengan target G sebesar 3.

Percobaan tersebut dilakukan sebanyak 4 kali dengan menggunakan metode BackLink dan metode PageRank. Metode PageRank dilakukan sebanyak 3 kali dengan mengubah-ubah nilai dumping factor dari 0.95, 0.8, dan 0.3. Kedua metode tersebut menggunakan target G yang sama yaitu 3. Angka 3 berarti semua dokumen yang mempunyai jumlah backlink lebih besar atau sama dengan 3 dianggap sebagai dokumen yang penting. Perbandingan antara metode PageRank dan BackLink dapat dilihat pada gambar v.1. Pada grafik sumbu horisontal menunjukkan persentase dokumen yang telah ditelusuri, P(C), pada waktu crawler berhenti. Pada akhir sumbu horisontal, 194 dokumen telah ditelusuri oleh crawler. Sedangkan sumbu vertikal menunjukan persentase dokumen penting yang telah ditelusuri, P st (C), pada saat crawler berhenti. Dari grafik pada gambar V.1. dapat dilihat bahwa metode PageRank dengan dumping factor sebesar 0.3 mempunyai kinerja paling baik. Hal ini telihat garis pada metode PageRank 0.3 selalu berada di atas kiri garis-garis yang lain. Sedangkan tabel V.2. menunjukkan peningkatan sebesar 30% pada kinerja metode PageRank 0.3 dibanding metode BackLink.


Metode PageRank dengan dumping factor sebesar 0.3 ini mempunyai kinerja yang baik disebabkan karena metode tersebut sesuai dengan bentuk struktur web yang terdapat pada tc.its-sby.edu. Berdasarkan hasil tersebut terlihat bahwa metode BackLink bertingkah laku seperti depth-first search. Sedangkan metode PageRank merupakan kombinasi breath-first search dan depth-first search.

Gambar V.3. Urutan penelusuran dengan PageRank ordering. Garis putus-putus berarti belum ditelusuri, sedangkan garis lurus berarti sudah ditelusuri.

Dengan kata lain, selama proses penelusuran, penggunaan metode BackLink akan bias jika menemukan sekelompok dokumen yang saling berkaitan (lihat gambar V.2.). Jika crawler menggunakan metode BackLink maka crawler akan menelusuri dokumen-dokumen penting dalam kelompok tertentu terlebih dahulu dibanding menelusuri dokumen-dokumen secara global. Sedang pada metode PageRank, crawler tidak hanya menelusuri dokumen-dokumen dalam kelompok tertentu saja, tetapi juga mengunjungi dokumen-dokumen secara global (lihat gambar V.3.). Pada percobaan selanjutnya akan digunakan dataset yang sama, namun target G yang digunakan dinaikkan menjadi 10. Pada percobaan ini juga digunakan metode dan metric yang sama dengan percobaan pada tc.its-sby.edu dengan target G=3 yang lalu.

Paper 19 - 5


Percobaan pada tc.its-sby.edu (target G=10) Dataset yang digunakan percobaan tersebut sama dengan dataset pada percobaan sebelumnya. Namum nilai target G diubah menjadi 10. Dari penelusuran tersebut diperoleh data seperti pada tabel V.3. Tabel V.3. Dataset tc.its-sby.edu hasil penelusuran dengan backlink metric dengan target G sebesar 10 Tanggal percobaan Dataset Jumlah Doc Jumlah URL tidak valid Lama Pengukuran %Hot Page Target G

18 Oktober 2002 tc.its-sby.edu 194 46 10 14% (28 doc) 10

Uji Coba dengan PageRank Metric Bagian tersebut menguraikan sejumlah percobaan yang kinerjanya diukur dengan menggunakan PageRank metric. Pada PageRank metric, sebuah dokumen yang mempunyai nilai IR(p) lebih besar atau sama dengan nilai target G akan dikatakan penting. Percobaan pada tc.its-sby.edu (target G=0.5) Tabel V.4. Dataset tc.its-sby.edu hasil penelusuran dengan PageRank metric dengan target G sebesar 0.5

PageRank vs BackLink Target 10

100

Tanggal percobaan Dataset Jumlah Doc Jumlah URL tidak valid Lama Pengukuran %Hot Page Target G

90 80 70 60 % Hot

metode PageRank terdapat dumping factor yang menyebabkan metode ini kadang-kadang mempunyai sifat breadth-first search.

18 Oktober 2002 tc.its-sby.edu 194 46 10 28% (54) 0.5

Tabel v.5. Peningkatan PageRank 0.9 terhadap BackLink

50 40 30 20 10 0 1

3

5

pageRank 0.95

7

9

11

13

15

17

19

% Crawled

pageRank0.8 pageRank0.3 Backlink

Gambar V.4. Grafik BackLink vs PageRank dengan dumping factor 0.95, 0.8, dan 0, 3 pada dataset tc.itssby.edu dengan target G sebesar 10.

Pada percobaan tersebut terjadi peningkatan sebesar 30% pada kinerja metode PageRank 0.3 dibanding metode BackLink. Dari grafik pada gambar V.4. dapat dilihat bahwa hanya metode PageRank dengan dumping factor sebesar 0.3 mempunyai kinerja paling baik. Hal ini terlihat pada garis dari metode PageRank 0.3 yang selalu berada di atas dibanding dengan garis-garis yang lain yang mengalami perubahan yang tidak beraturan. Garis dari metode PageRank 0.3, 0.8, dan 0.95 mengalami perbaikan dibanding percobaan sebelumnya. Terlihat bahwa PageRank dengan nilai dumping factor yang besar mempunyai pola yang mirip bahkan sama dengan BackLink. Hal ini disebabkan karena metode PageRank merupakan turunan dari metode BackLink. Bedanya pada Kerjasama antara Lemlit dan PIKTI ITS

%hot %hot pageRank(x) BackLink (y) ?(x-y) ?(x-y)/y 0 0 0 0 15 15 0 0 15 15 0 0 19 22 4 20 19 22 4 20 19 22 4 20 31 22 -9 -29,412 37 33 -4 -10 37 44 7 20 37 50 13 35 37 54 17 45 41 65 24 59,091 39 70 31 80,952 44 80 35 79,167 44 85 41 91,667 54 87 33 62,069 74 85 11 15 87 87 0 0 98 98 0 0 100 100 0 0 %peningkatan 26,765

Untuk menghindari data yang sangat sensitif, maka pada percobaan tersebut digunakan target G sebesar 0.5. Percobaan tersebut menghasilkan data yang dapat dilihat pada tabel V.4. Percobaan tersebut dilakukan sebanyak 2 kali dengan menggunakan metode BackLink dan metode PageRank. Metode PageRank dilakukan dengan nilai dumping faktor sebesar 0.9. Kedua metode tersebut menggunakan target G yang sama yaitu 0.5. Angka 0.5 disini berarti semua dokumen yang mempunyai nilai pagerank lebih Paper 19 - 6


%Hot

80 60 40 20

98

82

67

52

36

21

5

0

pagerank0.9

%Crawled

Gambar V.5. Grafik BackLink vs PageRank dengan dumping factor 0.9 dan 0.5 pada dataset tc.its-sby.edu dengan target G sebesar 0.5

Percobaan pada its.ac.id dan its-sby.edu (target G=10) Tabel V.6. Dataset its-sby.edu hasil penelusuran dengan PageRank metric dengan target G sebesar 0.5. Tanggal percobaan Dataset Jumlah Doc Jumlah URL tidak valid Lama Pengukuran %Hot Page Target G

80 60 40 20 0 0 10 21 31 41 51 61 71 82 92 pagerank 0.9

%Crawled

Gambar V.6. Grafik PageRank dengan dumping factor 0.9 pada dataset its-sby.edu dan its.ac.id dengan target G sebesar 10.

PageRank vs BackLink

100

Backlink

PageRank

100

%Hot

besar atau sama dengan 0.5 dianggap sebagai dokumen yang penting. Tabel V.5. menunjukkan peningkatan kinerja pada metode PageRank 0.9 sebesar 27% dibanding dengan metode BackLink. Sedangkan grafik yang menggambarkan kedua tabel tersebut dapat dilihat pada gambar V.6. Dari gambar tersebut terlihat jelas bahwa PageRank mampu memperoleh dokumen penting lebih dahulu dibanding dengan metode BackLink, meskipun kinerja tersebut terlihat tidak begitu baik. Hal ini disebabkan pada host yang kecil terdapat banyak cross link yang sangat sensitive.

12-Oct-02 its.ac.id & its-sby 3932 182 10 15% (587) 10


Pada percobaan tersebut, dataset yang digunakan adalah its.ac.id dan its-sby.edu. Percobaan tersebut menghasilkan data yang dapat dilihat pada tabel V.6. Percobaan tersebut dilakukan sebanyak satu kali dengan menggunakan metode PageRank. Metode PageRank dilakukan dengan nilai dumping faktor sebesar 0.9. Dari gambar tersebut terlihat bahwa dengan metode PageRank, Crawler mempunyai kinerja yang baik dibanding percobaan-percobaan sebelumnya. Hal ini disebabkan pada jumlah situs yang terlibat lebih bervariasi. 3. KESIMPULAN DAN SARAN Kesimpulan Kesimpulan yang dapat diuraikan dari penelitian tersebut adalah sebagai berikut: ?? Penelusuran suatu struktur web sangat dipengaruhi oleh dumping factor. Dimana jika dumping factor naik, maka pola penelusuran akan mendekati pola penelusuran breath-first search. Sedangkan jika dumping factor turun, maka pola penelusuran akan mendekati pola penelusuran depth-first search. ?? Urutan dokumen-dokumen berdasarkan nilai PageRank mencerminkan tingkat relevansi terhadap dokumen-dokumen lain yang mengacunya. ?? Fungsi PageRank yang lain adalah PageRank dapat digunakan untuk menduga URL-URL mana yang berkualitas yang perlu dikunjungi terlebih dahulu. Paper 19 - 7


?? Berdasarkan uji coba yang dilakukan pada dataset tc.its-sby.edu, PageRank dengan dumping factor 0.3 mempunyai rata-rata peningkatan kinerja 30% dari BackLink. Saran ?? Perangkat lunak tersebut dapat diintegrasikan dengan sebuah mesin pencari (Search Engine). ?? Diharapkan crawler dapat melakukan penelusuran dan perhitungan secara pararel. ?? Diharapkan crawler tersebut dilengkapi dengan algoritma penjadwalan. 4. DAFTAR PUSTAKA [1] Brin, Sergey, Lawrence Page, “The Anatomy of a Large-Scale Hypertextual Web Search Engine”, California, 1998. [2] Cho, Junghoo, Hector Gracia -Molina, Lawrence Page, “Efficient Crawling Through URL Ordering”, New York,1998. [3] Cho, Junghoo. “Crawling the Web: Discovery and Maintenance of Large-Scale Web Data”, California, 2001. [4] Google Inc, www.google.com , 1998. [5] Henzinger, Monika R., “Hyperlink Analysis for The Web. California: IEEE Internet Computing, 2000. [6] Henzinger, Monika R., “Link Analysis in Web Information Retrieval”, California, 2001. [7] Kleinberg, Jon., “Authoritative Sources in a Hyperlinked Environment”, ACM-SIAM Symposium on Discreate Algorithms, 1998. [8] Page, Lawrence, Sergey Brin, Rejeev Motwani, Terry Winograd, “The PageRank Citation Ranking: Bringing Order to the Web”, California, 1998. [9] Salton, Gerard, “Introduction to Modern Information Retrieval”, McGrawHill, 1995. [10] Agus Zainal Arifin dan Ari Novan Setiono, “Klasifikasi Dokumen Berita Kejadian Berbahasa Indonesia dengan Algoritma Single Pass Clustering”, Teknik Informatika, Institute Teknologi Sepuluh Nopember, Surabaya, 2002.


Paper 19 - 8

PERANCANGAN DAN PEMBUATAN PERANGKAT LUNAK PENELUSUR WEB (WEB CRAWLER) MENGGUNAKAN ALGORITMA PAGERANK

Recommend Documents