analisis link -...

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


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


Contoh citation hypertextual


Contoh Cross Reference network


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.


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.


Contoh Web Directed Graph


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.


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.


Strongly Connected Component


Link

• Link dapat menjadi sumber keaslian dan

pengakuan/otoritas.

• mail spam

• phone call log

• host quality


?

?

?

? 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.


? 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.



• 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)


Page A hyperlink

Page B Anchor


• 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


Evu ),(

Pengindeksan Teks Anchor

• Ketika mengindeks dokumen D, teks anchor disertakan

dari link yang menunjuk ke D.


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.


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.


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).


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.


Ad

1

A

B

C 1

2

2

CBA

CAB

BC

BA

Contoh


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


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


)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.


PageRank: Contoh


A

B

C

D

0 0 1 ½

1/3 0 0 0

1/3 ½ 0 ½

1/3 ½ 0 0

H=

PageRank: Contoh


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


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:


TeN

edHH1

))1((

PageRank Google Matrix


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.


HITS


AT&T

Alice

ITIM

Bob

O2

Mobile telecom companies

Hubs

Authorities

Algoritma HITS


Contoh HITS


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


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


analisis link -...

Documents