[데이터마이닝] 5.링크분석(Link analysis) 5.4절 연습문제(Exercise 5.4 )

연습문제 5.4.1

그림1

스팸 팜 분석을 실시해보자. 

a) 각 지원 페이지는 목표 페이지가 아닌 자기 자신으로 연결된다. 

 지원 페이지가 자기 자신으로 연결된다면 목표 페이지의 페이지 랭크 값은 어떻게 될 것인가?

y = x + 1-beta/N 이렇게 되겠네 

 

b) 각 지원페이지는 어디로도 연결되지 않는다

이래도 a)와 마찬가지지 y = x + 1-beta/N 이렇게 되겠네 

 

c) 각 지원 페이지는 자기 자신과 목표 페이지로 연결된다. 

이렇게 되면 어떻게 되려나?

own page 1개가 보유하게 되는 점수는 다음과 같다.

다음과 같고 자기 자신과 목표페이지로 연결되면 그대로인가(목표페이지로만 연결되는경우를 뜻함)?.. 해깔리네. 

아니면 나가는 랭크 값이 절반으로 줄어들게 되는 것인가?

그렇다면 들어오는 랭크 값은 하나 늘었기 때문에 가지고 있는 랭크값이 커지니까 결국 나가는 랭크 값도 같아지는게 아닌가?

수렴 한 상황에서 tartget page rank에 관한 식이 그림 1에 나와있다.
own pages들이 outgoing link가 하나 더 생기면.

이 값이 절반으로 될 터이고 
그에따라 t의 rank값도 줄어들게 될 것이다. 


random sufffer가 owned page에 있을때 t로 갈 확률이 줄어드는 것이므로 t의 rank가 줄어든는 것.

 

연습문제 5.4.2

신뢰할 수 있는 페이지는 오직 B뿐이라는 가정 하에

 

a) 각 페이지의 트러스트랭크를 계산하여라.

트러스트 랭크란.(trust rank) teleport set = trusted pages로 놓고 topic-sensitve pagerank를 실행하는것. 

M = matrix(c(0, 1/3 ,1/3 ,1/3,
             1/2,0,0,1/2,
             1,0,0,0,
             0, 1/2 , 1/2, 0),nrow = 4)
r = matrix(c(1/4,1/4,1/4,1/4))
beta = 0.8

es = matrix(c(0,1,0,0),nrow=4)
s = 1
pre_r = r
r = (beta*M)%*%r + (1-beta)/s * es
while(pre_r != r ){
  pre_r = r
  r = (beta*M)%*%r + (1-beta)/s * es
}
r

trusted rank(when truested page is only B)

#######################################################################
#page rank - method 1
M = matrix(c(0, 1/3 ,1/3 ,1/3,
             1/2,0,0,1/2,
             1,0,0,0,
             0, 1/2 , 1/2, 0),nrow = 4)
r = matrix(c(1/4,1/4,1/4,1/4))
beta = 0.8
matrix_N = matrix(c(1/4,1/4,1/4,1/4,1/4,1/4,1/4,1/4,1/4,1/4,1/4,1/4,1/4,1/4,1/4,1/4) ,nrow=4)
matrix_N
A = beta * M + (1-beta) * matrix_N

pre_r = r
r = A%*%r

while(pre_r != r ){
  pre_r = r
  r = A%*%r
}
r

#####################################################
#page rank - method 2
M = matrix(c(0, 1/3 ,1/3 ,1/3,
             1/2,0,0,1/2,
             1,0,0,0,
             0, 1/2 , 1/2, 0),nrow = 4)
r = matrix(c(1/4,1/4,1/4,1/4))
beta = 0.8

es = matrix(c(1,1,1,1),nrow=4)
s = 4
pre_r = r
r = (beta*M)%*%r + (1-beta)/s * es
while(pre_r != r ){
  pre_r = r
  r = (beta*M)%*%r + (1-beta)/s * es
}
r

페이지 랭크

b) 각 페이지의 스팸 매스를 계산하여라 

(r-t)/r

스팸 매스

! Exercise 5.4.3 : Suppose two spam farmers agree to link their spam farms. How would you link the pages in order to increase as much as possible the PageRank of each spam farm’s target page? Is there an advantage to linking spam farms?

1) M의 값이 올라가므로 y값이 올라간다. 즉 target의 page rank값이 올라간다.

2) 스팸 매스도 잘 피할 수 있을가? (r-t)/r의 값을 줄일 수 있는가? r의 값이 증가하므로  스팸 매스의 값이 줄어들 것이라고 추측할 수 있다. r-t의 값은 유지가 될 것이다. r의 값이 증가함에 따라 t의 값도 증가할 것이기 때문.

t의 값은 다음과 같은 방법으로 구한다.

텔레포트에만 적용이 되는 것이므로 스팸 페이지로 인해 더해지는 랭크값이 완전히 줄어들수는 없다.