링크내역을 이용한 페이지점수법 알고리즘

Abstract

웹은 정보의 저장 및 검색에 있어서 보편적인 매체가 되고 있다. 웹에서 정보 검색은 검색엔진 을 출발점으로 이용하는 것이 대부분이지만, 그 결과는 사용자의 요구와 늘 일치하는 것은 아니며 때로는 의도적으로 조작된 검색 결과가 제시되기도 한다. 검색엔진의 데이타를 의도적으로 조작하는 것을 스패밍 (spamming)이라고 부르며, 다양한 스패밍과 방지기술이 있지만, 최근에 각광을 받고있는 링크기반 검색 방식에는 스패밍이 쉽지 않은 것으로 알려져 있다. 그러나 이러한 방식에서도 구글폭탄(Google Bombing) 과 같이 페이지점수법(PageRank)을 조작할 수 있는 약점이 있다. 본 논문에서는 이러한 약점을 방지할 수 있는 알고리즘을 제시한다. 기본적으로 링크 기반 검색 방식을 기초로 하여 웹을 하나의 유향 레이블 그래프로 인식하여 각 웹 페이지들은 하나의 노드로, 하이퍼링크는 에지로 표현함에 있어서 본 연구에서는 링크구조를 기반으로 링크내역(link context)을 부여하고 이를 에지의 레이블로 사용한다. 링크내역과 대상 페이지 사이의 유사도를 구하고, 이것을 이용하여 페이지점수법의 인접행렬을 재구성하는 방법을 취했다. 결과로써 기존의 방법 및 특이값 추출기법(SVD)에 기반한 새로운 기준을 도입해 그 효과를 입증했다. ; The World Wide Web has become an entrenched global medium for storing and searching information. Most people begin at a Web search engine to find information, but the users pertinent search results are often greatly diluted by irrelevant data or sometimes appear on target but still mislead the user in an unwanted direction. One of the intentional, sometimes vicious manipulations of Web databases is Web spamming as Google bombing that is based on the PageRank algorithm, one of the most famous Web structuring techniques. In this paper, we regard the Web as a directed labeled graph that Web pages represent nodes and the corresponding hyperlinks edges. In the present work, we define the label of an edge as having a link context and a similarity measure between link context and the target page. With this similarity, we can modify the transition matrix of the PageRank algorithm. A motivating example is investigated in terms of the Singular Value Decomposition with which our algorithm can outperform to filter the Web spamming pages effectively.