정보검색론 공부 - 링크 분석

 

 

21.2 PageRank

• 웹 그래프에 있는 모든 정점에 대해 0과 1 사이의 수치화된 점수를 할당하는 것
• 용어 근접성(Term proximity)과 코사인 유사도(Cosine similarity) 계산 방법 등을 이용하여 웹 페이지의 합산 점수를 계산함
• 텔레포트(Teleport)
• 웹 서퍼가 어떤 정점에서 웹 그래프 내의 다른 어떤 정점으로든지 이동할 수 있음
• 텔레포트 연산
• 서퍼는 정점 내에 인출-링크가 있을 때에 텔레포트 연산을 지시함
• 서퍼는 외부로 나가는 링크를 갖는 정점에서 0~1 사이의 확률로 텔레포트 연산을 수행함

 

21.2 Markov 연쇄

• Markov 연쇄(Markov chain)
• 이산 확률 과정(discrete-time stochastic process)임
• N 개의 상태(State)로 구성되며, 각 웹 페이지가 Markov 연쇄 내의 한 상태와 대응됨
• [0, 1] 사이 값을 갖는 N X N 전이 확률 행렬(Transition probability matrix) P에 의해 구축됨
• 확률 행렬(Stochastic matrix)의 중요한 성질은 최대 고유치가 1에 상응하는 주요 왼쪽 고유 벡터(Principal left eigenvector)를 가지고 있음
• 완전 전이 Markov 연쇄(Ergodic Markov chain)
• 상당한 기간이 지난 후, 하나의 체계가 최초의 상태와 거의 비슷한 상태로 돌아가는 조건 하에 있는 것
• 조건
• 기약성(Irreducibility)
• 한 상태에서 다른 상태로 0이 아닌 확률로 전이하는 과정을 보장함
• 비주기성(Aperiodicity)
• 모든 상태의 전이는 순환되는 상태들로 나눌 수 없음
• 주제 중심 PageRank(Topic-specific PageRank)
• 개인화된 PageRank(Personalized PageRank)

 

21.3 허브와 전문성

• 허브 점수(Hub score)
• 전문성 점수(Authority score)
• 좋은 허브 페이지는 많은 권위 있는 페이지를 지시하고 있으며, 전문성이 높은 페이지는 많은 허브 페이지를 갖음
• HITS(Hyperlink-Induced Topic Search)
• 링크 분석에 따라 허브 점수와 전문성 점수를 계산하는 방법

 

 

참고: Introduction to Information Retrieval