🔍 문서를 그래프를 사용하여 표현
- 중요도(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 알고리즘이다.
- 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 값을 업데이트
