국내 웹 그래프의 링크 구조 분석 (Link Structure Analysis of Korean Web Graph)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회 컴퓨팅의 실제 논문지 / 19권 / 1호 / 7 ~ 14페이지
· 저자명 : 서정주, 김진일, 김은상, 김영호, 정하웅, 김성열, 박근수

초록

웹을 구성하는 웹 페이지들과 페이지들 사이의 하이퍼링크들은 방향성을 지니는 그래프로 표현될 수 있으며, 웹 그래프가 가지는 독자적인 링크 구조의 특성은 다양한 분야의 연구에서 활용되고 있다. 현재 검색 엔진들이 수집한 웹 페이지들은 그 규모가 수십억 개로 방대한 양을 이루고 있다. 본 논문에서는 약 3억 개의 국내 웹 페이지들을 수집하고, 이들 간의 약 137억 개의 하이퍼링크들을 추출하여 생성한 웹 그래프의 구조에 대해 분석한다. 또한 그래프 알고리즘을 이용하여 웹 그래프를 구성하는 요소들로 나눈 후 전체적인 구조를 도식화한 보우타이 다이어그램을 도출한다. 국내 웹 페이지들은 링크의 진입 차수와 연결 요소들의 크기 분포에서 멱법칙을 따르며, 웹 페이지의 진출 차수는 특정 차수 이상에서 멱법칙을 따른다. 또한 웹 그래프는 평균 연결 거리가 매우 짧은 약 12 정도로 small-world network의 성질을 가지고 약 40%의 웹 페이지 쌍 사이에 경로가 존재하며, 국내 웹 그래프는 해외의 경우보다 연결도가 더 높다.

영어초록

The World Wide Web consisting of web pages and hyperlinks amongst them can be represented as a directed graph. The structural and evolutional properties of the Web graph are useful in a variety of research area such as sociology and computer science. In this paper, we crawled 0.3 billion Web pages and 13.7 billion hyperlinks amongst them from Korean Web and built the Web graph by extracting the link structure. We show the bow-tie diagram which visualizes the overall structure of the Web graph. In-degrees and sizes of connected components of web pages of Korean web follow power law distributions whereas out-degrees shows power law distribution when the degree is higher than a particular value. Also, 40% of pairs of the Korean web graph have a path between them with average distance around 12 demonstrating that the Korean web graph shows a small-world phenomenon. The Korean web graph shows a higher degree of connectivity compared to the global web graph.

참고자료

· 없음