[Social Network] HITS

HITS

Link-based object ranking (LBR)의 방법 중 하나이다.

타겟 : Object = 1종류, link = 1종류

 

Authority & Hub

Authority와 hub의 개념을 도입하여 object를 순서화한다.

• Authority
  • 다른 페이지로부터 참조를 많이 당하는 페이지(노드)
  • in-link가 많은 페이지
• Hub
  • 다른 페이지를 많이 참조하는 페이지
  • out-link가 많은 페이지

 

Authority와 hub는 상호 보완적인 측면을 가지고 있다.

일반 페이지로부터 in-link가 들어오는 것보다는 hub로부터 in-link가 들어오는 것이 더 좋은 authority이고,

일반 페이지로 out-link가 가는 것 보다는 authority로 out-link가 가는 것이 더 좋은 hub이기 때문이다.

 

 

알고리즘

각 페이지는 hub score($h(d_i)$)와 authority score($a(d_i)$)를 갖는다.

• Hub score
  • $h(d_i) = \sum _{d_j \in OUT(d_i)}a(d_j)$ 
  • 자신이 가리키는(out-link로 나가는) 페이지들의 authority score의 합
• Autority score
  • $a(d_i) = \sum _{d_j \in IN(d_i)}(h(d_j))$
    
    • 자신을 가리키는(in-link로 들어오는) 페이지들의 hub score의 합

 

방법

아래 과정을 반복하면 네트워크의 구조가 반영되어 수렴하게 된다.

다만 계속 증가하지 않고 수렴 하는 것을 위해서 normalize 과정이 필요하다.

1. 그래프를 adjacency matrix로 표현한다.
2. 모든 node에 대해 동일한 hub score와 authority score를 부여한다.
3. 자신의 hub score와 authority score를 업데이트하고 각 점수를 normalize한다.
4. 수렴할 때 까지 3의 과정을 반복한다.

 

예시

아래 과정은 한번 iteration을 돌았을 때 hub score와 authority score가 update 된 모습이다.

파란색이 authority score, 빨간색이 hub score이다.