ANALISIS LINK Budi Susanto

Text dan Web Mining - TI UKDW 1

Tujuan

• memahami karakteristik link antar laman yang dapat

dimodelkan sebagai graf.

• memahami algoritma PageRank

• memahami Hubs and Authority

Text dan Web Mining - TI UKDW 2

Struktur Web

• struktur hypertextual memberikan sebuah jaringan informasi • node mewakili laman yang berisi informasi

• link menyatakan relasi antar node.

• Bentuk hypertextual pertama adalah konsep citation di antara book atau artikel ilmiah. • node mewakili buku/artikel

• edge mewakili citation dari satu karya ke lainnya.

• perbedaan utama dengan web: citation dikelola lebih kuat berdasar waktu.

• citation mengarah pada karya sebelumnya.

• Bentuk hypertextual lain adalah cross-references dalam ensiklopedia

Text dan Web Mining - TI UKDW 3

Contoh citation hypertextual

Text dan Web Mining - TI UKDW 4

Contoh Cross Reference network

Text dan Web Mining - TI UKDW 5

Pemikiran Vannevar Bush

• Bush menyatakan bahwa informasi yang tersimpan pada

buku, perpustakaan, atau bahkan memori komputer

adalah linear.

• berisi koleksi item yang diurutkan dalam urutan tertentu.

• Bush membayangkan sebuah hypothetical prototype,

disebut Memex, yang fungsinya serupa dengan Web

• berisi bentuk digital dari pengetahuan manusia yang saling

berhubungan dengan associative link.

• Pemikiran tentang Web:

• web sebagai ensiklopedia universal,

• web sebagai sistem socio-economic raksasa,

• web sebagai otak global.

Text dan Web Mining - TI UKDW 6

Web sebagai Directed Graph

• Tautan navigasi membentuk struktur backbone dari Web,

daripada memperkaya isi.

• tautan antar laman Web diterapkan sebagai bentuk graf

berarah, mengingat bentuk tautan dapat bersifat

asimetrik.

• blog Anda memiliki link ke UKDW, namun tidak tentu UKDW

memiliki link ke blog Anda.

Text dan Web Mining - TI UKDW 7

Contoh Web Directed Graph

Text dan Web Mining - TI UKDW 8

Strongly Connected

• Sebuah directed graph dikatakan terhubung kuat jika

terdapat sebuah jalur dari setiap node ke setiap node

lainnya.

• Contoh pada slide 8 bukanlah directed graph yang

terhubung kuat. Mengapa?

• Jika sebuah directed graph tidak terhubung kuat, maka

perlu diperhatikan atribut lain, yaitu: reachability.

• mengenali node mana saja yang “reachable” dari node lain melalui

jalur-jalur yang terbentuk.

Text dan Web Mining - TI UKDW 9

Strongly Connected Component

• SCC dalam directed graph adalah sebuah subset node

sedemikian rupa, sehingga:

• setiap node dalam subset memiliki sebuah jalur ke node lainnya,

dan

• subset bukan merupakan bagian himpunan yang lebih besar

lainnya dengan properti bahwa setiap node dapat mencapai setiap

node lainnya.

Text dan Web Mining - TI UKDW 10

Strongly Connected Component

Text dan Web Mining - TI UKDW 11

Link

• Link dapat menjadi sumber keaslian dan

pengakuan/otoritas.

• mail spam

• phone call log

• host quality

Text dan Web Mining - TI UKDW 12

?

?

?

? Good Bad

Link

• Node Good tidak akan menunjuk ke node Bad.

• Jika sebuah node menunjuk ke node Bad, maka node

tersebut Bad.

• Jika node Good menunjuk sebuah node, maka node

tersebut juga Good.

Text dan Web Mining - TI UKDW 13

? Good Bad

Link dan IR

• Sebagian besar sistem IR didasarkan pada isi dari teks.

• Link dapat digunakan untuk:

• scoring dan ranking

• link-based clustering

• struktur topik dari link

• Link sebagai feature dalam klasifikasi

• dokumen yang bertautan dengan dokumen lain dikatakan mungkin

dalam satu subjek.

• Crawling menggunakan link untuk mengambil dokumen

lainnya.

Text dan Web Mining - TI UKDW 14

Web sebagai Directed Graph

• Assumption 1: sebuah hyperlink antar halaman

menyatakan sebuah pengakuan otoritas (sinyal kualitas)

• Assumption 2: teks dalam anchor dari sebuah hyperlink

mengambarkan halaman sasaran (textual context)

Text dan Web Mining - TI UKDW 15

Page A hyperlink

Page B Anchor

Web sebagai Directed Graph

• G = (V, E)

• G adalah directed graf

• V adalah himpunan halaman web

• N adalah jumlah halaman web

• |V| = N

• Jika halaman u memiliki link ke halaman v, maka

Text dan Web Mining - TI UKDW 16

Evu ),(

Pengindeksan Teks Anchor

• Ketika mengindeks dokumen D, teks anchor disertakan

dari link yang menunjuk ke D.

Text dan Web Mining - TI UKDW 17

www.ibm.com

Armonk, NY-based computer

giant IBM announced today

Joe’s computer hardware links

Sun

HP

IBM

Big Blue today announced

record profits for the quarter

Pengindeksan Teks Anchor

• Namun terkadang tidak semua teks anchor adalah benar.

• Dapatkah memberi bobot terhadap teks anchor?

• bobot dapat dilakukan dengan memberikan tanda pada setiap

halaman yang memiliki teks anchor.

• jika web tersebut dipercaya, misalnya Google, Yahoo!, maka teks

anchor memiliki bobot tinggi.

• Aplikasi lainnya

• pembobotan terhadap link dalam graf

• menghasilkan deskripsi halaman dari teks anchor.

Text dan Web Mining - TI UKDW 18

PageRank

• Mengukur kualitas dari sebuah halaman web tidak dapat

hanya menggunakan in-links.

• Sebuah web page dikatakan memiliki reputasi baik, jika

halaman web bereputasi baik menunjuk web page

tersebut.

• PageRank merupakan metode pembobotan setiap

halaman dengan nilai antara 0 – 1.

Text dan Web Mining - TI UKDW 19

1Vv

v 0, Vv

PageRank

• Setiap halaman web akan memiliki bobot PageRank,

dengan notasi:

• menyatakan:

• berapa banyak halaman lain yang menunjuk ke halaman u.

• PageRank sebuah halaman adalah jumlah dari semua PageRank

dari setiap halaman yang menunjuk ke halaman tersebut (in-

degree).

Text dan Web Mining - TI UKDW 20

U

EVU

UV

),(

Naïve PageRank

• Jika halaman A menunjuk halaman B, A berkontribusi

dari PageRanknya untuk halaman B.

• Halaman B mengumpulkan kontribusi dari semua

halaman yang menunjuk ke B, untuk menentukan

PageRank B.

Text dan Web Mining - TI UKDW 21

Ad

1

A

B

C 1

2

2

CBA

CAB

BC

BA

Contoh

Text dan Web Mining - TI UKDW 22

A

B

C

A

B

C

D

E

A

B

C A

Kelemahan Naïve PageRank

• vulnerable to collision • apa yang disebut sebagai link spam.

• pada slide 22, node C, D, dan E adalah link spam.

• dapat menghasilkan solusi tak terbatas

• tidak menemukan solusi

Text dan Web Mining - TI UKDW 23

A

B

C P

Q

R

PageRank

• Menurut Page dan Brin (1998), untuk menghindari masalah

naïve pagerank, diasumsikan pemakai mengunjungi tautan

secara random dengan suatu probability tertentu.

• Nilai λ pada umumnya bernilai 0.85

• P1 adalah probabilitas mengunjungi v dari halaman lain

• P2 adalah probabilitas mengunjungi v secara acak

Text dan Web Mining - TI UKDW 24

)1(2

),(

1

21

P

dP

PP

EVU U

U

V

PageRank

• Karena pada kenyataannya jumlah halaman web yang

dihitung sangatlah banyak, maka dilakukan pendekatan

iteratif untuk setiap nilai PageRank halaman.

• Dalam tiap iterasi, digunakan formula:

• p(k+1) = p(k) * H

• p adalah vektor PageRank tiap halaman web

• Untuk inisialisasi, p(0), digunakan nilai 1/n untuk tiap

halaman.

• n adalah jumlah halaman dalam graf.

• kemudian dilakukan perulangan sampai nilai perbedaan

antar kedua vektor terakhir cukup kecil.

• ditentukan dengan sebuah threshold.

Text dan Web Mining - TI UKDW 25

PageRank: Contoh

Text dan Web Mining - TI UKDW 26

A

B

C

D

0 0 1 ½

1/3 0 0 0

1/3 ½ 0 ½

1/3 ½ 0 0

H=

PageRank: Contoh

Text dan Web Mining - TI UKDW 27

p0=

0.25

0.25

0.25

0.25

p1=

0.25

0.25

0.25

0.25

0 0 1 ½

1/3 0 0 0

1/3 ½ 0 ½

1/3 ½ 0 0

0.38

0.08

0.33

0.21

=

…

p7=

0.38

0.13

0.29

0.20

0 0 1 ½

1/3 0 0 0

1/3 ½ 0 ½

1/3 ½ 0 0

0.39

0.13

0.29

0.19

=

PageRank

Text dan Web Mining - TI UKDW 28

p8=

0.39

0.13

0.29

0.19

0 0 1 ½

1/3 0 0 0

1/3 ½ 0 ½

1/3 ½ 0 0

0.39

0.13

0.29

0.19

=

|p8-p7| = abs(0.39-0.39)+abs(0.13-0.13)+abs(0.29-0.29)+abs(0.19-0.19)=0

Sehingga p8 adalah vektor v* (equilibrium value)

yang merupakan nilai PageRank untuk tiap

halaman yang diharapkan.

PageRank

• Untuk mencegah adanya hasil PageRank adalah 0 jika

ditemukan adanya dangling nodes, maka matrix

teleporation H, harus diubah dengan langkah:

• Buat matrix untuk Dangling Node

• dij = 0 jika Hij > 0

• dij = 1 jika Hij = 0

• Update matrix H dengan G (Google) Matrix:

Text dan Web Mining - TI UKDW 29

TeN

edHH1

))1((

PageRank Google Matrix

Text dan Web Mining - TI UKDW 30

0 0 1 ½

1/3 0 0 0

1/3 ½ 0 ½

1/3 ½ 0 0

H=

0.04 0.04 0.89 0.46

0.32 0.04 0.04 0.04

0.32 0.46 0.04 0.46

0.32 0.46 0.04 0.04

G=

Algoritma HITS

• HITS singkatan dari Hypertext Induced Topic Search.

• Ketika pemakai memberikan query, HITS pertama akan

mendapatkan hasil dokumen yang relevan dengan query

oleh mesin pencari dan menghasilkan 2 rangking:

• authority ranking

• hub ranking

• Authority adalah sebuah halaman dengan in-links

• Hub adalah sebuah halaman dengan out-links.

Text dan Web Mining - TI UKDW 31

HITS

Text dan Web Mining - TI UKDW 32

AT&T

Alice

ITIM

Bob

O2

Mobile telecom companies

Hubs

Authorities

Algoritma HITS

Text dan Web Mining - TI UKDW 33

Contoh HITS

Text dan Web Mining - TI UKDW 34

A

B

C

0 0 1

0 0 1

0 0 0

A=

0 0 0

0 0 0

1 1 0

AT=

u=

1

1

1

Contoh HITS

Text dan Web Mining - TI UKDW 35

v= AT.u =

1

1

1

0 0 0

0 0 0

1 1 0

=

0

0

2

Update vector hub

u= A.v =

0

0

2

0 0 1

0 0 1

0 0 0

=

2

2

0

Halaman C paling authoritative,

sedangkan A, dn B hub penting.

TERIMA KASIH budi susanto

Text dan Web Mining - TI UKDW 36