[CS246] TrustRank vs. LinkFarms

TrustRank: Bias Random Walk to trustworthy pages

Link Farms: Create link to boost PageRank of particular page

spammer들은 구글의 PageRank를 역이용하여 특정 페이지의 pagerank score를 극대화시켜 페이지 상단에 노출시키려 한다. spammer의 시각에서 웹페이지는 3개의 종류가 있다.

• Owned pages: spammer가 소유권을 가지고 있어서 무엇이든 할 수 있는 페이지. (completely control)
• Accessible pages: 소유권은 없지만, 댓글 등으로 자신의 링크를 post할 수 있는 페이지. 블로그 댓글, 뉴스 댓글 또는 위키피디아의 링크 등이 있다.
• Inaccessible pages: 대부분의 웹페이지에 해당하고, spammer가 어떠한 것도 할 수 없는 페이지다

Link Farms (Stanford CS246)

위 그림에서 보듯이, Owned page는 서로 링크를 걸어서 bidirectional link를 형성하고, accessible page에서는 target page $t$로 향하는 spam link가 있다.

 

spammer는 자신의 target page $t$의 pagerank score를 높이는 것이 목적이다.

 

Notation

$N$: web에 존재하는 모든 페이지 수. $N$의 값은 매우 크다.

$M$: spammer가 소유권을 갖고 있는 페이지 수. 

$x$: Accessible page에서 기여되는 pagerank

$y$: target page $t$의 pagerank

 

Owned page의 pagerank score는 $\cfrac{\beta y}{M} + \cfrac{1 - \beta}{N}$이므로 

\begin{align} y &= \beta M \left[ \cfrac{\beta y}{M} + \cfrac{1 - \beta}{N} \right] + \cfrac{1 - \beta}{N} \\ &\approx \cfrac{x}{1-\beta^2} + \cfrac{\beta}{(1+\beta)} \cfrac{M}{N} \ (\because \cfrac{1-\beta}{N} \approx 0) \end{align}

 

만일 $\beta=0.85$면, $y=3.6x + 0.46(\frac{M}{N})$이 된다. 이때 $\frac{M}{N}$은 pagerank score를 boosting하는 역할을 하게 된다. spammer의 owned pages가 많을 수록 $M$의 값이 커지게 된다.

 

TrustRank: Topic-Specific PageRank with a teleport set of trusted pages

topic-specific pagerank에서 제안된 teleport set $S$를 set of trustworthy pages로 만들어 해결한다. 문제는 teleport set을 구성하는 방법이다.

1. Human: 사람이 직접 고르는 방법. 밑바닥부터 모든 페이지를 살펴보는 것은 아니고, PageRank 값이 높은 페이지는 대부분 신뢰할 만하다고 할 수 있다. link spam이 설령 특정 페이지의 score를 올릴지라도 밑바닥에서 중간정도로 올릴 수는 있으나, 완전히 pagerank score가 제일 높은 상위 페이지로는 가지 못한다.
2. Domain: membership이 관리되는 도메인을 trustworthy teleport set으로 간주한다. .edu, .mil, .gov 등의 도메인은 소유권이 매우 엄격하게 관리되기 때문에 trustworthy하다고 할 수 있다.