🔍 Graph based IR

🔍 문서를 그래프를 사용하여 표현

• 중요도(weight)(authority)를 이용

• (예시)

  • Web
    • 각 노드는 웹 페이지, edge는 링크, 방향이 있는 그래프가 된다. (구글 검색엔진에서 사용)

• 중요도를 사용하여 더 중요한 정보를 보여줄 수 있게됨

• Text based IR과 차이점 : text based는 단어가 완전 똑같지 않으면 검색 결과로 안나올 수 있다. text에 의존하므로 한계가 있다.

✔ 용어

• Directed / Undirected

• Weighted / Unweighted

• Graph - Adjacency Matrix : 그래프에서 가중치가 있는 부분을 인접행렬로 표현

• In_degree : 현재 노드로 들어오는 edge 갯수

• Out_degree : 현대 노드에서 나가는 edge 갯수

• 

  • 좋은 노드는 나쁜 노드를 링크하지 않을 것이다.
  • 나쁜 노드는 좋은 노드를 링크할 가능성이 있다.
  • 이 정보를 사용하여 중간 노드의 정체를 알 수 있다.

🔍 Link 분석

• Link를 많이 받고 있는 웹페이지 일수록 중요도(authority)가 높아진다.
• 중요도가 높은 페이지도 중요하지만, 새로 들어오는 query와 해당 문서가 얼마나 관련있는지도 중요하다.
• 이것을 반영한 것이 PageRank 알고리즘이다.

✔ PageRank 알고리즘 (Google에서 만듬)

• offline based : 사용자의 질의와 상관없이 미리 Link 분석을 함

• online : 사용자의 질의를 적용한 것. 사용자가 query를 던질 시, query relevance를 사용해서 관련있는 page를 찾아냄

• offline과 online을 모두 혼합하여 사용한 것이 PageRank 알고리즘

• page의 중요도 : page에 방문할 확률

• 

  • E(u) : 링크를 타고 가는 것이 아닌, 중간에 다른 페이지로 점핑하는 경우 (random으로 들어올 확률)

  • j : 페이지로 들어오고있는 페이지

  • PR(Vj) : Vj로 들어올 확률 값

  • Out(Vj) : Vj에서 나가고 있는 link 갯수

  • 처음에는 모든 페이지를 공평하게 확률을 부여

  • 반복을 통해 각 페이지의 PageRank 값을 업데이트