Analiza linków w celu  

rankingu odpowiedzi

1

 

 

 

 

Web jako Graf Skierowany

Założenie 1: hyperlink między stronami 
oznacza uznanie przez autora relewancji 
(znak jakości)

Założenie 2: Tekst w kotwicy linku opisuje 
wskazywaną stronę (kontekst tekstowy)

Strona A

hyperlink

Strona B

Kotwica

2

 

 

 

 

Tekst kotwicy

 

WWW Worm - McBryan [Mcbr94]

 



Jak rozróżnić dla ibm między:



Strona domowa IBM (głównie graficzna)



Strona copyright IBM (wysoka częstość termów 
dla ‘ibm’)



Rywalizujące strony spamerów (wysoka 
częstość termów)

www.ibm.com

“ibm” 

“ibm.com”

“IBM home page”

Milion części 
tekstu kotwic z  
“ibm” wysyła 
mocny sygnał

3

 

 

 

 

Indeksowanie tekstu kotwicy



W trakcie indeksowania dokumentu D, 
włącz tekst kotwicy z linków wskazujących 
na 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

4

 

 

 

 

C.D. Indeksowanie tekstu 
kotwicy



Czasami mogą być niespodziewane efekty 
uboczne  - np.: evil empire.



Czy może wynik tekstu kotwicy z wagą 
zależną od autoryzacji strony, na której 
jest ta kotwica



Np.: Jeśli założymy, że treść z cnn.com or 
yahoo.com jest autoryzowana to zaufamy 
tekstom kotwicy z nich

5

 

 

 

 

Tekst kotwicy



Inne aplikacje



Ważenie/filtrowanie linków w grafie



Generowanie opisu stron z tekstu 
kotwicy

6

 

 

 

 

Analiza cytowań



Częstość cytowań



Częstość łączna współcytowań



Współcytowania dla danego autora mierzą  

“wpływ”



Analiza współcytowań



Bibliograficzna łączna częstość



Artykuły, które są łącznie cytowane są podobne 



Indeksowanie cytowań



Kto jest autorem cytowanym? (Garfield 1972)



Wstępny pomysł Pagerank: Pinsker and Narin ’60s

7

 

 

 

 

Uporządkowanie niezależne od 
pytania



Pierwsza generacja: wykorzystanie 
zliczania linków jako prostej miary 
popularności.



Dwie podstawowe propozycje:



Nieskierowana popularność:



Każda strona otrzymuje wynik = liczba linków 
wejściowych plus liczba linków wyjściowych 
(3+2=5).



Skierowana popularność:



Wynik strony = liczba jej linków wejściowych (3).

8

 

 

 

 

Przetwarzanie pytań



Najpierw wyszukaj wszystkie strony 
pasujące do  tekstu pytania (powiedzmy: 
venture capital kapitał wysokiego 
ryzyka).



Uporządkuj je wg popularności linków 
(jakiś wariant z poprzedniego slajdu).



Więcej niuansów – użyj liczby linków jako 
miary statycznej dopasowania (wykład 7), 
połączonej z wynikiem dopasowania 
tekstowego

9

 

 

 

 

Wyniki pagerank



Wyobraźmy sobie przeglądarkę 
wykonującą błądzenie losowe po stronach 
Web:



Start z losowej strony



W każdym kroku, wyjście ze strony po linkach 
do kolejnych stron z jednakowym 
prawdopodobieństwem



“W stanie ustalonym” każda strona ma 
długoterminową intensywność wizyt – użyj 
ją jako wynik dla strony.

1/3
1/3
1/3

10

 

 

 

 

Nie całkiem dobre



Web jest pełny nieaktywnych elementów.



Błądzenie losowe może utknąć w nieaktywnym 
elemencie.



Nie ma sensu mówić o długoterminowej 
częstości wizyt

??

11

 

 

 

 

Teleporting



W nieaktywnym elemencie, skocz 
do losowej strony webowej.



W każdym aktywnym elemencie, z 
prawdopodobieństwem 10%, skocz 
do losowej strony.



Z pozostałym 
prawdopodobieństwem (90%), 
przejdź na losowy link.



10% - to parametr.

12

 

 

 

 

Wyniki teleportacji



Teraz nie może utknąć lokalnie.



Mamy długoterminową 
częstość wizyt każdej strony 
(niekoniecznie, co będzie 
pokazane).



Jak możemy obliczyć 
intensywność odwiedzin?

13

 

 

 

 

Łańcuchy Markowa



Łańcuch Markowa składa się z n stanów, 
oraz stochastycznej macierzy przejść P o 
rozmiarze nxn . 



W każdym kroku, jesteśmy dokładnie w 
jednym ze stanów.



Dla 1  i,j  n, elementy P

ij

 macierzy 

mówią nam, z jakim 
prawdopodobieństwem  j będzie 
następnym stanem jeśli aktualnie 
jesteśmy w stanie i. 

i

j

P

ij

P

ii

>0

is OK.

14

 

 

 

 

.

1

1







ij

n

j

P

c.d. Łańcuchy Markowa



Oczywiście,                              dla każdego 
i.



 Łańcuchy Markowa są abstrakcyjnym 
modelem błądzenia losowego.



Ćwiczenie: przedstaw teleportacyjne 
błądzenie losowe ze slajdu nr 12 jako 
łańcuch Markowa dla tego przypadku: 

15

 

 

 

 

Ergodyczne łańcuchy Markowa



Łańcuch Markowa jest ergodyczny jeśli



Istnieje ścieżka z każdego stanu do 
każdego



Dla każdego stanu początkowego, po 
skończonym czasie przejścia T

0

, 

prawdopodobieństwo pobytu w 
dowolnym stanie dla ustalonego czasu 
T>T

0

 jest niezerowe.

Nie 

ergodycz-ny

(parzysty/

nieparzysty)

.

16

 

 

 

 

c.d. Ergodyczne łańcuchy 
Markowa



Dla każdego ergodycznego łańcucha 
Markowa istnieje długoterminowa 
częstość odwiedzin dla każdego stanu.



Stacjonarny rozkład 
prawdopodobieństwa.



W trakcie długiego okresu czasu, każdy 
stan jest odwiedzany proporcjonalnie do 
tego rozkładu.



Nie ma znaczenia z którego stanu 
wystartujemy.

17

 

 

 

 

Wektory prawdopodobieństwa



Wektor prawdopodobieństwa (wiersz) x 
= (x

1

, … x

n

) pokazuje  w którym punkcie 

jest błądzenie.



Np.: (000…1…000) oznacza, że jest w 
stanie i.

i

n

1

Bardziej ogólnie, wektor x = (x

1

, … x

n

) 

oznacza, że błądzenie jest w stanie i z 
prawdop. x

i

.

 

.

1

1







n

i

i

x

18

 

 

 

 

Zmiany w wektorze 
prawdopodobieństwa



Jeśli wektor prawdop. jest  x = (x

1

, 

… x

n

) w danym kroku to jaki będzie 

w kroku następnym?



Przypomnijmy, że wiersz i 
stochastycznej macierzy przejść  P 
mówi nam gdzie przejdziemy ze 
stanu i.



Więc z x, następny stan ma rozkład 
prawdop. xP.

19

 

 

 

 

Przykład stanu ustalonego



Stan ustalony wygląda jak wektor 
prawdopodobieństw a = (a

1

, … a

n

):



a

i

 jest prawdop. że łańcuch jest w stanie  

i.

1

2

3/4

1/4

3/4

1/4

Dla tego przykładu, a

1

=1/4 and a

2

=3/4.

20

 

 

 

 

Jak możemy obliczyć wektor 
prawdopodobieństw 
stacjonarnych? 



Niech a = (a

1

, … a

n

) oznacza wektor wierszowy 

prawdopodobieństw stacjonarnych.



Jeśli aktualny stan łańcucha oznaczymy przez a, 
wtedy rozkład w następnym kroku jest aP.



Ale a jest stanem ustalonym, więc a=aP.



Rozwiązanie tego równania macierzowego daje 
nam a.



Więc a jest (lewym) wektorem własnym P.



(Odpowiada “głównemu” wektorowi własnemu P 
największą wartością własną.)



Macierze prawdopodobieństw przejść zawsze mają 
największą wartość własną 1.

21

 

 

 

 

Jeden ze sposobów obliczenia 
a



Przypomnijmy, że niezależnie od stanu 
początkowego możemy „ewentualnie” osiągnąć 
stan ustalony a.



Startuj z dowolnego rozkładu (np.: x=(10…0)).



Po jednym kroku jesteśmy w xP;



Po dwóch krokach w xP

2

 , następnie xP

3

 itd.



“Ewentualnie” znaczy dla “dużego” k, xP

k 

= a.



Algorytm: mnóż  x przez wzrastające potęgi P 
aż iloczyn będzie wyglądał stabilnie.

22

 

 

 

 

Zarys algorytmu Pagerank 



Przetwarzanie wstępne:



Dla danego grafu linków zbuduj macierz P.



Dla tej macierzy oblicz a.



Składowa a

i

 jest liczbą między 0 i 1: to 

pagerank strony  i.



Przetwarzanie pytania:



Wyszukaj strony odpowiednie dla pytania.



Uporządkuj wg ich pagerank.



Porządek jest niezależny od pytania.

23

 

 

 

 

Rzeczywistość 



Pagerank jest używany w google, ale jego 
zastosowania bardzo liczne



Wiele bardzo specyficznych cech jest 
używanych



Pewne adresy określają klasy pytań



Ranking z wykorzystaniem maszynowego 
uczenia jest b. często stosowany



Pagerank jest ciągle b. użyteczny dla 
takich rzeczy jak strategia crawlingu

24

 

 

 

 

Pagerank: Problemy i 
warianty



Jak realistyczny jest model surfowania 
przypadkowego?



(Czy jest ważny?)



Co jeśli zamodelujemy backspace?



Zachowanie jest mocno zniekształcone dla krótkich 
ścieżek



Silniki wyszukiwawcze, zakładki & słowniki powodują 
skoki nielosowe.



Specjalne modele surfowania



Ważone prawdop. przejść bazujące na dopasowaniu do 
tematu/pytania (nierównomierny wybór krawędzi)



Specjalne skoki do stron wg tematu (np.: bazujące na 
osobistym zainteresowaniu zakładkami & kategoriami)

25

 

 

 

 

Pagerank uwzględniający temat



Cel – wartości pagerank zależne od tematu 
pytania 



Koncepcyjnie, stosujemy losowe surfowanie, 
które przechodzi z np.: z prawdop. 10% 
probability, stosując następującą zasadę:



Wybierz temat (np.: jeden z 16 najwyższych 
kategorii z ODP (Open Directory Project) oparty 
na pytaniu & podanym przez użytkownika 
rozkładzie dla kategorii



Przejdź losowo do strony dla wybranego tematu



Wygląda na trudne w implementacji: nie 
możemy obliczyć PageRank w trakcie 
odpowiedzi na pytanie!

26

 

 

 

 



Offline:Oblicz pagerank dla poszczególnych 

tematów



Niezależnie od pytania jak poprzednio



Każda strona ma wiele wyników pagerank – jeden 

dla każdej kategorii ODP, z przejściem tylko do tej 

kategorii



Online: Kontekst pytania klasyfikowany dla 

tematów (rozkład wag dla tematów) 



Generuj dynamiczny wynik pagerank dla każdej strony – 

suma ważona specyficznych dla tematu wartości pagerank

Cd. Pagerank uwzględniający 
temat

27

 

 

 

 

Modyfikowany PageRank 
(“Personalizacja”)



Wejście: 



Graf webowy W



Wektor wpływu v dla tematów

v : (strona  stopień wpływu)



Wyjście:



Wektor rankingu r: (page  znaczenie 

strony wrt v)



r

 

= PR(W , v)

Wektor ma jedną

 składową dla każdego 

tematu

Wektor ma jedną

 składową dla każdego 

tematu

28

 

 

 

 

Przejście nierównomierne 

Przejście z prawdop.10% do strony Sporty

Sporty

29

 

 

 

 

Interpretacja złożonego wyniku



Dla danego zbioru personalizowanych 
wektorów {v

j

}

 

j 

[w

j

 · PR(W , v

j

)] = PR(W , 

j 

[w

j

 · v

j

]) 

Dla danych preferencji użytkownika dla 

tematów, wyraża kombinację  “bazowych” 
wektorów v

j

30

 

 

 

 

cd. Interpretacja

10% przejście do Sports

Sports

31

 

 

 

 

cd. Interpretacja

Health

10% przejście do stron Health

32

 

 

 

 

cd. Interpretacja

Sports

Health

pr = (0.9 PR

sports

 + 0.1 PR

health

) daje:

9% przejście do sports, 1% przejście do health

33

 

 

 

 

Hyperlink-Induced Topic Search 
(HITS)



W odpowiedzi na pytanie, zamiast 
uporządkowanej listy stron, znajduje dwa  
zbiory powiązanych stron:



Strony Hub są dobrymi listami linków dla tematu.



Np.: “Bob’s list of cancer-related links.”



Strony Authority pojawiają się rekurencyjnie na 
dobrych hubach dla tematu.



Najbardziej odpowiednie dla pytań 
“szerokiego tematu” niż dla pytań 
szukających stron.



Daje szeroki wycinek popularnej opinii.

34

 

 

 

 

Hubs i autorytety



Więc, dobra strona hub dla tematu 
wskazuje na wiele autorytatywnych 
stron dla tego tematu.



Dobra autorytatywna strona dla 
tematu jest wskazywana  przez 
wiele dobrych hubów dla tego 
tematu.



Taka powiązana definicja prowadzi 
nas do obliczeń iteracyjnych.

35

 

 

 

 

Oczekiwanie

                                     

               AT&T        

 Alice                     
 
                                  I TI M  
Bob 
                                  O2 

Mobile telecom companies

Huby

Autorytety

36

 

 

 

 

Schemat wysokiego poziomu



Wybierz z Web bazowy zbiór 
stron, które mogą być dobre 
jako huby lub autorytety.



Z nich określ, mały zbiór 
najważniejszych stron hubów i 
autorytetów;



Algorytm iteracyjny.

37

 

 

 

 

Zbiór bazowy



Dla danego pytania tekstowego (np.: 
browser), zastosuj indeks tekstowy 
aby otrzymać wszystkie strony 
zawierające browser.



Nazwij je zbiorem korzeniowy stron. 



Dodawaj strony które



Wskazują na ten zbiór, lub 



Są wskazywane przez strony z tego 
zbioru.



Nazwij go zbiorem bazowym.

38

 

 

 

 

Wizualizacja

Zbiór 

korzeniowy

Zbiór bazowy

39

 

 

 

 

Gromadzenie zbioru bazowego



Zbiór korzeniowy to zwykle 200-1000 
węzłów.



Zbiór bazowy może zawierać tysiące 
węzłów



Zależy od tematu



Jak znajdujemy bazowy zbiór węzłów?



Postępuj za linkami wyjściowymi przez 
parsowanie stron zbioru korzeniowego.



Pobieraj linki wejściowe (i linki wyjściowe) z 
serwera połączeń

40

 

 

 

 

Wybieranie hubów i 
autorytetów



Oblicz dla każdej strony x w zbiorze 
bazowym wynik dla huba h(x) i wynik dla 
autorytetu a(x).



Inicjuj: dla wszystkich x, h(x)



1; a(x) 



1;



Iteracyjnie aktualizuj wszystkie h(x), a(x);



Po iteracjach



Wynikowe strony z najwyższymi h() jako 
huby



 najwyższe  a() jako autorytety.

Kluczowe

41

 

 

 

 

Iteracyjna aktualizacja



Powtarzaj poniższe aktualizacje dla 
wszystkich  x:





y

x

y

a

x

h



)

(

)

(





x

y

y

h

x

a



)

(

)

(

x

x

42

 

 

 

 

Skalowanie



Aby zapobiec zbyt dużemu 
wzrostowi h() i a() , można 
skalować w dół po każdej iteracji.



Współczynnik skalowania nie ma 
znaczenia:



Zależy nam jedynie na względnych 
wartościach wyników.

43

 

 

 

 

Ile iteracji?



Twierdzenie: relatywne wartości wyników 
będą zbieżne po kilku iteracjach:



faktycznie, odpowiednio skalowane  h() i a() 
powodują, że wyniki dążą do stanu 
ustalonego!



Dowód będzie pokazany później.



Potrzebujemy tylko względny porządek  
wyników h() i  a() – nie ich absolutne 
wartości.



W praktyce, ~5 iteracji zbliża nas do 
stabilności.

44

 

 

 

 

Japan Elementary Schools



The American School in Japan 



The Link Page 



‰ªès—§ˆä“c¬ŠwZƒz[ƒƒy[ƒW 



Kids' Space 



ˆÀés—§ˆÀé¼•”¬ŠwZ 



‹{é‹³ˆç‘åŠw•‘®¬ŠwZ 



KEIMEI GAKUEN Home Page ( Japanese ) 



Shiranuma Home Page 



fuzoku-es.fukui-u.ac.jp 



welcome to Miasa E&J school 



_“ލ쌧E‰¡•ls—§’†ì¼¬ŠwZ‚̃y



http://www...p/~m_maru/index.html 



fukui haruyama-es HomePage 



Torisu primary school 



goo 



Yakumo Elementary,Hokkaido,Japan 



FUZOKU Home Page 



Kamishibun Elementary School...

 



schools 



LINK Page-13 



“ú–{‚ÌŠwZ 



a‰„¬ŠwZƒz[ƒƒy[ƒW 



100 Schools Home Pages (English) 



K-12 from Japan 10/...rnet and Education ) 



http://www...iglobe.ne.jp/~IKESAN 



‚l‚f‚j¬ŠwZ‚U”N‚P‘g•¨Œê 



ÒŠ—’¬—§ÒŠ—“Œ¬ŠwZ 



Koulutus ja oppilaitokset 



TOYODA HOMEPAGE 



Education 



Cay's Homepage(Japanese) 



–y“썬ŠwZ‚̃z[ƒƒy[ƒW 



UNIVERSITY 



‰J—³¬ŠwZ DRAGON97-TOP 



Â‰ª¬ŠwZ‚T”N‚P‘gƒz[ƒƒy[ƒW 



¶µ°é¼ÂÁ© ¥á¥Ë¥å¡¼ ¥á¥Ë¥å¡¼ 

Huby

Autorytety

45

 

 

 

 

Rzeczy do zapamiętania



Zbierane są razem dobre strony 
niezależnie od języka strony zawartości.



Używa się tylko analizy linków po 
zbudowaniu zbioru podstawowego



iteracyjne określanie wyniku jest 

niezależne od pytania.



Iteracyjne obliczenia po przeszukiwaniu 
indeksu tekstowego – znaczny narzut.

46

 

 

 

 

Dowód zbieżności



nn macierz sąsiedztwa A:



Każde z n stron w  zbiorze bazowym ma 
wiersz i kolumnę w macierzy.



Element  A

ij

 = 1 jeśli strona i wskazuje na 

stronę  j, w przeciwnym przypadku = 0.

1

2

3

 1      2     
 3

1

2

3

 0      1     
 0

 1      1     
 1

 1      0     
 0

47

 

 

 

 

cd. Dowód zbieżności: wektory 
hub/autorytet



Rozpatruj  wyniki habów  h() i autorytetów 
a() jako wektory z n składowymi.



Stosuj iteracyjne aktualizacje





y

x

y

a

x

h



)

(

)

(





x

y

y

h

x

a



)

(

)

(

48

 

 

 

 

cd. Dowód zbieżności: przejście 
do postaci macierzowej



h=Aa.



a=A

t

h.

A

t

 jest 

transpozycj

ą A. 

Podstawienie, h=AA

t

h i a=A

t

Aa.

Więc, h jest wektorem własnym dla AA

t

 i  

a jest wektorem własnym dla A

t

A.

Dalej, nasz algorytm jest szczególnym przypadkiem 
znanego algorytmu dla obliczania wektorów własnych: 
metody iteracji potęgowej.

Gwarantuje to zbieżność.

49

 

 

 

 

Problemy



Zniekształcenie tematu



Strony z poza tematu mogą generować 
„autorytety” z poza tematu



Np.: sąsiedni graf może być uznany za 
“super temat”



Wzajemnie wzmacniające się wyniki 



 Przypisane strony/witryny mogą 
wzmacniać wzajemnie swoje wyniki 



Linki pomiędzy przypisanymi stronami nie są 
użytecznymi sygnałami

50

 

 

 

 

Literatura



IIR Chap 21



http://www2004.org/proceedings/docs/1p3
09.pdf



http://www2004.org/proceedings/docs/1p5
95.pdf



http://www2003.org/cdrom/papers/referee
d/p270/kamvar-270-xhtml/index.html



http://www2003.org/cdrom/papers/referee
d/p641/xhtml/p641-mccurley.html

51