Pagerank, HITS, Cocitation+ algorithm

Text-based ranking function의 문제점

1. 유명한(Authoritive) 페이지라고 해서 주제에 대한 단어가
   많이 나오는 것은 아니다.
   (전혀 안 나올 수도 있음.)
   text를 count해서 유명한 곳인지 별 볼 일 없는 지 판단할 수 없다.
   (not sufficiently self-descriptive)

Link의 종류

1. Navigational purposes
   ("Click here to return to the main menu")
2. Paid advertisements
3. Recommmendation

Pagerank

Page A가 Page B에 link를 하면 추천(recommendation)으로 봄
(A->B)

1. 계산 방법
   T1 ~ Tn : Page A를 link하는 모든 Page
   PR(A) : Page A의 Pagerank
   D : dampening factor (page간의 거리가 1칸 늘때마다 감소되는 지수)
   C(T1) : Page T1이 link하는 문서의 갯수

   PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

   모든 Page의 pagerank가 서로 맞물려서 계산되기 때문에
   식을 한 개 계산해서 한 개의 값을 구할 수 없음.
   Matrix를 만들어서 방정식을 풀면 됨
   => 수학(linear algebra)적 의미 : Matrix의 Eigenvector
   => 해결책 iteration을 통해 수렴하게 해도 됨
   => Matrix의 size가 N x N 이 되나 다행히도 sparse matrix

문제점

1) 추천이 아니라 단지 저작권상의 문제, 서로 주고 받는 식으로 link하는 것 등..
2) PageRank를 올리기 위해 link를 함(악용)
3) 유명한 page라서 그냥 link해 봄
   => yahoo 등.. www에 직접 관련된 page들이 Pagerank가 높음.
   해결책 => 금칙어(stop word) 도입

Pagerank가 높은 페이지들

1) Link가 많은 페이지
2) 문서의 분량이 많은 페이지(페이지끼리 서로 link함)
   => 해결책 : local link(자신의 domain내에서 건 link는 무효로 함)

Cocitation+ Algorithm

1. Web graph does not resemble a random graph.

2. Web is a sparse graph with local dense regions.

3. Zip's distribution 특성 (n번째 원소의 weight가 1/n)

4. bipartite graph 특성(subgraph enumeration)
   (유사한 page는 그들이 가리키는 page도 유사하다.)

5. Cocitation Algorithm

   전제조건 : 관련 Node를 몇 개 알고 있어야 함.(Node u)
   Node u가 있을 때

   c -> s -> u and c -> u 이면 ++weight(s)

   weight(s)가 가장 큰 것들을 출력

6. Cocitation+ Algorithm

   전제조건 : 관련 Node를 몇 개 알고 있어야 함.(Node u)
   Node u가 있을 때
   1. local link가 적을 때.
      u -> s and o -> s 이면 ++weight(o)

      weight(o)가 가장 큰 것들을 출력

      (o = u와 같은 곳을 가리키는 것 중 가장 weight가 큰 것)

   2. local link가 많을 때
      p -> u and p -> o 일 때 ++weight(o)

      weight(o)가 가장 큰 것들을 출력

      (u와 같은 link로부터 가리켜지는 node 중 가장 weight가 큰 것)

Netscape-Alexa Algorithm

1. Netscape 4.06 이후 버젼에 내장되어 있음.
   (일종의 검색 Client)
2. User의 surfing path를 추적하여 검색에 반영

Friend Algorithm

1. User의 bookmark를 이용해서 그 User와 가장 web 사용 패턴이
   비슷한 User를 찾는 다.
2. 그 User와 다른 User들 간의 bookmark의 intersection(교집합)의
   크기를 구해서 가장 큰 사람 순서로 보여준다.

HITS Algorithm

1. Directed graph
2. Root set(200여개)를 가지고 시작
3. Root set이 가리키는 Node들과, Root set을 가리키는 Node들을 추가해서
   Base set을 만든다.
4. hub page와 authority page를 구한다.
   authority weight x(p) = sum(y(q)) where q->p
   hub weight y(p) = sum(x(q)) where p->q

   (Mutually reinforcing relationship)
  
   x = AT * y
   y = A * x
   (A : adjacency matrix)

   x = AT * y = AT * A * x
   y = A * x = A * AT * y
   따라서 x, y는 각각 AT * A와 A * AT의 eigenvector

5. 이 방법의 특징
   . 주제가 좁을 경우 확장된다.
     (Topic Generalization, Convergent Generalization, Tree of Topics)
   . 주제가 여러개일 때는 약간 혼란이 있다.
   . Root set에 관계없이 같은 topic이면 결과가 안정적이다.

Query의 종류
1. Specific queries - Scarcity Problem
2. Broad-topic queries - Abundance Problem
3. Similar-page queries

Impact factor
1. 논문의 중요도 평가에 이용
2. 단순히 지난 2년간 인용도를 weight로 함

관련된 주제들
. social networks, citation analysis

관련 논문
http://www.iprcom.com/papers/pagerank/
http://plg.uwaterloo.ca/~aeehassa/home/papers/cocitation/cocitation+.htm
http://www.fred.jabadabadoo.nl/PageRank.pdf
http://www.cs.cornell.edu/home/kleinber/ht98.ps
http://www.cs.cornell.edu/home/kleinber/auth.pdf
http://www.almaden.ibm.com/cs/k53/ieeecomp.ps