국내 웹 그래프의 링크 구조 분석 7 국내 웹 그래프의 링크 구조 분석 (Link Structure Analysis of Korean Web Graph) 서 정 주 김 진 일 김 은 상 김 영 호 (Jungjoo Seo) (Jinil Kim) (Eunsang Kim) (Daniel Kim) 정 하 웅 김 성 렬 박 근 수 (Hawoong Jeong) (Sung-Ryul Kim) (Kunsoo Park) 요 약 웹을 구성하는 웹 페이지들과 페이지들 사이의 하이퍼링크들은 방향성을 지니는 그래프로 표 현될 수 있으며, 웹 그래프가 가지는 독자적인 링크 구조의 특성은 다양한 분야의 연구에서 활용되고 있 다. 현재 검색 엔진들이 수집한 웹 페이지들은 그 규모가 수십억 개로 방대한 양을 이루고 있다. 본 논문 에서는 약 3억 개의 국내 웹 페이지들을 수집하고, 이들 간의 약 137억 개의 하이퍼링크들을 추출하여 생 성한 웹 그래프의 구조에 대해 분석한다. 또한 그래프 알고리즘을 이용하여 웹 그래프를 구성하는 요소들 로 나눈 후 전체적인 구조를 도식화한 보우타이 다이어그램을 도출한다. 국내 웹 페이지들은 링크의 진입 차수와 연결 요소들의 크기 분포에서 멱법칙을 따르며, 웹 페이지의 진출 차수는 특정 차수 이상에서 멱 법칙을 따른다. 또한 웹 그래프는 평균 연결 거리가 매우 짧은 약 12 정도로 small-world network의 성 질을 가지고 약 40%의 웹 페이지 쌍 사이에 경로가 존재하며, 국내 웹 그래프는 해외의 경우보다 연결도 가 더 높다. 키워드 : 웹 그래프, 보우타이 다이어그램, 링크 분석 Abstract 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. Key words : Web graph, Bow-tie diagram, Link analysis 이 논문은 2012년도 정부(교육과학기술부)의 재원으로 한국연구재단(No. 20120006492, 2011-0028908)과, 2012년 두뇌한국21 사업의 지원을 받아 수행 된 연구임 비 회 원 : 서울대학교 컴퓨터공학부 jjseo@theory.snu.ac.kr 비 회 원 : SAP Labs Korea jinil.kim@sap.com eunsang.kim@sap.com 비 회 원 : KAIST 물리학과 lovely0day@gmail.com 비 회 원 : KAIST 바이오융합연구소 교수 hjeong@kaist.edu 종신회원 : 건국대학교 인터넷미디어공학부 교수 kimsr@konkuk.ac.kr 종신회원 : 서울대학교 컴퓨터공학부 교수 kpark@theory.snu.ac.kr (Corresponding author임) 논문접수 : 2012년 7월 16일 심사완료 : 2012년 11월 10일 CopyrightC2013 한국정보과학회ː개인 목적이나 교육 목적인 경우, 이 저작 물의 전체 또는 일부에 대한 복사본 혹은 디지털 사본의 제작을 허가합니다. 이 때, 사본은 상업적 수단으로 사용할 수 없으며 첫 페이지에 본 문구와 출처 를 반드시 명시해야 합니다. 이 외의 목적으로 복제, 배포, 출판, 전송 등 모든 유형의 사용행위를 하는 경우에 대하여는 사전에 허가를 얻고 비용을 지불해야 합니다. 정보과학회논문지: 컴퓨팅의 실제 및 레터 제19권 제1호(2013.1)
8 정보과학회논문지 : 컴퓨팅의 실제 및 레터 제 19 권 제 1 호(2013.1) 1. 서 론 웹은 수많은 웹 페이지들로 구성되어 있고, 웹 페이지 들은 하이퍼링크의 형태로 서로 간의 링크 구조를 형성 하고 있다. 근래 웹이 인간 삶의 영역 전반에 미치는 영 향이 커짐에 따라 정보 전달의 효율성이라는 측면에서 많은 사람들이 웹의 구조에 대해 관심을 가지고 연구를 진행하고 있다. 웹의 링크 구조를 이해함으로써 얻는 이점은 여러 가 지가 있다. 최근 이슈가 되고 있는 소셜 네트워크에서 생성되는 컨텐츠들 간의 관계를 이해하는데 활용될 수 있으며, 웹에 존재하는 커뮤니티를 파악하고 분석하는데 유용한 정보를 제공할 수 있다[1]. 또한 웹 페이지들을 수집하는 효율적인 크롤링 알고리즘 설계하거나[2], 웹 의 링크 정보를 사용하는 알고리즘에 대해 분석할 때 활용할 수도 있다[3,4]. 본 논문에서는 국내 웹 페이지들을 대규모로 수집하 고 이들의 하이퍼링크 구조를 추출하여 생성한 그래프 의 구조적 특성에 대해 분석한다. 2장에서는 웹 페이지 의 수집 대상과 수집 시기에 대해 설명하고, 추출한 웹 그래프에 대해 설명한다. 3장에서는 웹 페이지의 진입 및 진출 차수에 따른 분포를 살펴보고, 4장에서는 그래 프의 연결 요소를 산출하여 그 크기에 따른 분포에 대 해 분석한다. 5장에서는 웹 그래프를 구성하는 요소들을 파악하고 각 요소들의 크기와 관계를 도식화한 보우타 이 다이어그램에 대해 설명한다. 관련 연구 멱법칙 어떠한 사건의 빈도수가 사건의 어떠한 특성 의 멱수에 따라 변화할 때 사건의 빈도수는 멱법칙을 따른다고 말한다. 경제학, 사회학, 자연과학 등의 여러 분야에서 멱법칙을 따르는 현상들이 발견되었으며, 웹 페이지들이 이루는 구조가 웹 페이지의 링크의 차수 혹 은 연결 요소의 크기 등에서 멱법칙을 이룬다는 것이 알려져 있다[5-8]. Small-World Network 그래프를 구성하는 대부분 의 정점들이 서로 인접하고 있지 않으나, 서로 간에 상 대적으로 적은 수의 다른 정점들만을 거쳐 도달할 수 있을 때 그 그래프를 small-world 네트워크라 한다. R. Albert 등은 웹 그래프 또한 small-world 현상을 가진 다는 것을 보였으며[9], A. Broder 등[5]과 R. Kumar 등[6]은 1999년 Altavista가 수집한 웹 페이지들을 대상 으로 두 페이지 간 경로가 존재할 때 방향성을 고려할 경우 평균적으로 약 16, 방향성을 고려하지 않은 경우 약 7개의 링크를 거쳐서 도달할 수 있음을 보였다. 해당 실험군에서 두 페이지 사이의 경로가 존재하는 비율은 약 25%이다. 커뮤니티 웹은 산발적으로 생성된 웹 페이지들로 구 성되어 체계적이고 조직적인 구조를 가지고 있지 않으 나, 연관된 컨텐츠를 지닌 페이지들이 링크 구조를 통하 여 커뮤니티를 이루고 있다는 것이 알려져 있다[10]. G. W. Flake 등은 최대흐름 알고리즘을 이용하여 커뮤니 티를 찾는 방안을 제안하였으며[10], R. Kumar 등은 그 래프의 bipartite core를 구함으로써 웹의 커뮤니티를 찾았다[1]. 2. 웹 그래프 본 연구를 위해서 자체 보유 중인 서버 클러스터와 직접 개발한 프로그램을 이용하여 웹 페이지들을 수집 하였다. 웹 페이지 수집 프로그램인 크롤러(crawler)는 특정 웹 페이지들을 SEED로 하여 수집을 시작한다. 수집한 페이지들로부터 하이퍼링크들을 추출하고, 추출한 링크 의 도메인을 키 값으로 하여 적당한 수의 해쉬 버킷들 에 링크들을 나누어 저장한다. 이 해쉬 버킷들은 큐 자 료구조이며, 크롤러들은 이 버킷들을 순환 순서 방식 (round-robin)으로 돌아가면서 접근하여 저장된 링크를 얻어 다시 웹 페이지를 수집하고, 이 과정을 반복하게 된다. 도메인을 키로 하여 링크들을 해쉬 버킷에 나누어 저장하는 이유는 크롤러들이 동시에 다양한 도메인의 페이지들을 수집할 수 있도록 하기 위함이다. 또한 크롤 러들이 한 사이트에 집중적으로 접근하여 과도한 트래 픽을 유발하지 않도록 도메인별로 최근 수집 시간을 저 장하여 도메인마다 최소 수집 간격을 지키도록 하였으 며, 한 사이트 내에서 너무 많은 양의 페이지를 수집하 는 것을 막기 위해서 사이트의 메인 페이지에서 일정 깊이 이상의 페이지들은 수집하지 않도록 하였다. 수집에 사용한 기계는 수집용 15대, 수집된 웹 페이지 들의 URL DB를 위한 28대 및 기타 1대로 총 44대가 사용되었으며, 100 Mbit/sec의 대역폭을 가진 네트워크 를 이용하였다. 수집기간은 2008년 5월부터 약 20일 동 안이며 대형 포털사이트들을 수집 알고리즘의 SEED로 하였다. 수집 대상은 국내 웹 페이지들이며 규모는 약 3 억 개의 웹 페이지이다. 본 논문에서의 연구 대상은 웹 페이지들 간의 하이퍼 링크로부터 생성한 방향성 그래프로, 이를 웹 그래프라 한다. 웹 그래프에서의 각 정점(vertex)은 수집한 각 웹 페이지들을 나타내며, 간선(edge)은 웹 페이지들 사이의 하이퍼링크를 나타낸다. 웹 그래프는 수집한 3억 개의 웹 페이지들로부터 하이퍼링크 쌍(u, v) 약 137억 개를 추출하여 구축하였다. 3억 개의 웹 페이지 중 어떠한 링 크 쌍에도 존재하지 않는 웹 페이지들과 중복되는 하이 퍼링크들은 그래프에서 제외하였다. 이렇게 제외된 웹
국내 웹 그래프의 링크 구조 분석 9 페이지들의 수는 약 3천만 개, 하이퍼링크들의 수는 약 22억 개다. 3. 웹 페이지의 차수 분포 네트워크를 구성하는 노드들이 가진 차수들의 확률 분포는 그 네트워크의 물리적인 특성을 반영한다는 것 이 알려져 있다. 평균보다 훨씬 큰 차수를 가진 허브 (hub)의 존재 때문에 차수의 확률 분포가 멱법칙을 따 르는 척도 없는 네트워크(scale free network)가 주목 받았으며 웹 역시 척도 없는 네트워크라는 것이 알려져 있다[11]. 웹 그래프에서 하이퍼링크는 방향성을 가지므로 각 웹 페이지들은 진입 차수(in-degree)와 진출 차수(outdegree), 두 가지 종류의 차수를 가진다. 진입 차수는 해당 웹 페이지로 들어오는 링크의 수이며 진출 차수는 웹 페이지에서 다른 웹 페이지로 나가는 링크의 수로 정의된다. 진출 차수는 웹 페이지의 하이퍼링크들로부터 바로 계산이 가능하며, 진입 차수는 하이퍼링크를 역방 향으로 뒤집어(link invert) 추출하였다. 그림 1은 진입 차수에 대한 분포 그래프이다. 그래프 의 가로축은 진입 차수이며 세로축은 해당 차수를 가지 는 웹 페이지의 비율이다. 가로축과 세로축은 모두 로그 스케일로 표시되어 있다. 그래프를 살펴보면 낮은 차수 를 지닌 페이지 수가 굉장히 많고 높은 차수를 지닌 페 이지 수는 상대적으로 매우 적음을 알 수 있다. 이러한 분포는 차수가 인 웹 페이지들의 비율이 에 비례 하는 멱법칙으로 분석할 수 있으며 이때 는 1보다 큰 수이다. 웹 페이지들의 진입 차수를 기준으로 분포를 확 인한 결과 지수를 1.92로 가지는 멱법칙을 따른다. 이 지수는 [6]에서의 결과인 해외 웹 그래프의 진입 차수에 대한 멱법칙의 지수 2.09와 근소한 차이를 보이며 비슷 함을 알 수 있다. 기존의 결과 및 이론적 모델과 일치하 는 결과이다[11]. 그림 2는 진출 차수에 대한 분포도이다. 진출 차수의 경우 진입 차수와 달리 낮은 차수의 페이지 수에 대한 분포가 멱법칙과는 차이를 보임을 알 수 있다. 이러한 현상을 설명하기 위해 그래프에 정점이 추가되면서 링 크가 생성되는 메커니즘과 정점의 차수 분포에 대한 연 구가 진행된 바 있다. Peterson 등은 과학 논문의 참조 관계를 나타내는 그래프에서 새로운 논문이 기존의 어 떤 논문을 직접 참조하는 경우와 그 논문의 참조목록의 논문을 참조하는 경우의 두 메커니즘을 고려하였다[12]. 전자의 확률을 1-c, 후자의 확률을 c 라 하고 정점들의 평균 차수를 n 이라 했을 때, 차수 의 분포확률은 가 된다. 이때 이다. 위의 식을 그래프로 나 타낼 경우 가 낮을 때 분포가 비슷하다가 특정 차수, 를 기점으로 분포가 급격히 줄어들며 멱법칙을 이 루게 된다[12]. 이 때 멱법칙의 지수는 가 된다. 본 논문에서는 국내 웹 그래프의 진출 차수의 분포를 위의 모델로 분석하였다. 이때 에서 진출 차수의 분포에 가장 가깝게 됨을 확인하였고 을 기점으로 분포율이 감소하여 지수 3.18 로 멱법칙을 이룬다. 은 추출한 웹 그래프에서 웹 페 이지의 평균 진출 차수이며 의 값은 non-linear least square fitting을 통해 산출하였다. [6]의 진출 차수가 이루는 멱법칙 분포의 지수 2.72은 앞서 언급한 두 메커 니즘을 고려한 분석이 아닌 멱법칙만을 고려한 결과이 나, 본 연구에서는 낮은 차수에서의 분포를 설명하기 위 해 [12]의 방법을 활용하였다. 차수 약 45 이상에서 보 이는 멱법칙의 지수는 3.18로, 다른 웹 페이지들로 하이 퍼링크를 45개 이상 가지는 웹 페이지들의 비율은 링크 수가 증가함에 따라 급격히 감소함을 알 수 있다. 지수 가 [6]보다 높은 것은 앞서 설명한 바와 같이 모든 차수 가 아닌 특정 차수 이상에서 멱법칙 지수를 산출하였기 때문이다. 표 1은 웹 페이지를 진입 차수의 크기로 정렬하여 상 위 3개를 추려낸 목록이다. 예상했던 대로 대형 포털 사 이트가 많은 진입 링크를 가짐을 알 수 있었다. 가장 큰 그림 1 웹 페이지의 진입 차수에 따른 분포 그림 2 웹 페이지의 진출 차수에 따른 분포
10 정보과학회논문지 : 컴퓨팅의 실제 및 레터 제 19 권 제 1 호(2013.1) 표 1 진입 차수에 따른 상위 3개의 웹 페이지 순위 웹 페이지 진입 차수 1 http://www.zeroboard.com 26812817 2 http://corp.nate.com 4818019 3 http://www.daum.net 4565655 차수의 페이지는 제로보드로, 이는 많은 웹 페이지 및 커뮤니티에서 이용되고 있는 제로보드가 홈페이지로의 링크를 가지기 때문이라 추측된다. 네이버는 9번째로 많 은 진입차수를 가지고 있었다. 4. 연결요소 웹 그래프의 연결요소가 그래프를 구성하는 형태와 크기에 대한 연구는 [5,6]에서 진행된 바 있으며 웹의 보우타이 형태에 대해 제시하였다. 본 연구에서는 수집 한 국내 웹 페이지들의 연결요소들을 찾고 그 규모에 대해 살펴본다. 4.1 강한 연결요소 그래프의 강한 연결요소는 모든 노드의 쌍들 사이에 방향성을 가진 경로가 존재하는 최대 연결 부분 그래프 로 정의된다. 즉, 웹 그래프의 강한 연결요소 내의 모든 웹 페이지들은 서로에게 도달할 수 있는 방향성을 가진 경로들을 가지고 있다. 그래프의 연결요소를 찾는 과정 에서는 Tarjan 알고리즘을 비재귀적으로 변형한 [13]을 참조하였다. 연결요소에 대한 첫 번째 실험으로, 연결요소를 찾고 그 크기, 즉 연결요소에 포함된 웹 페이지의 수를 계산 한 후 크기에 따른 연결요소의 분포에 대한 통계를 산 출하였다. 강한 연결요소에 대한 실험 결과 웹 그래프는 약 1.25억 개의 페이지, 즉 수집한 웹 페이지들 전체의 약 47%로 이루어진 매우 큰 하나의 강한 연결요소를 가지며, 이외의 강한 연결요소들은 이에 비해 상당히 작 은 크기를 가짐을 알 수 있었다. 이 가장 큰 강한 연결 요소를 SCC로 부르기로 하자. 강한 연결요소들의 크기 분포를 살펴보았을 때 웹 페 이지의 진입/진출 차수와 마찬가지로 멱법칙을 따름을 확인할 수 있었다(그림 3). 이때 멱법칙의 지수는 약 1.8이다. 국내 웹에서 SCC가 차지하는 비율은 [5]에서 구한 해외 웹의 경우인 27.7%보다 높은 47%로, 절반 가까이의 국내 웹 페이지들이 서로 도달할 수 있어 연 결도가 상당히 높음을 알 수 있다. 한편, 강한 연결 요 소들의 크기에 대한 멱법칙은 지수가 1.8로 [5]의 2.54 보다 낮다. 즉, 국내 웹 페이지들이 이루는 강한 연결 요소들의 크기가 해외보다 높게 분포하여 연결도가 높 음을 알 수 있다. 4.2 약한 연결요소 강한 연결요소에 이어 웹 그래프의 링크들의 방향성 을 고려하지 않고 약한 연결요소를 산출하였다. 그래프 의 약한 연결요소는 간선의 방향을 고려하지 않았을 때 서로에게 도달할 수 있는 노드들로 이루어진 부분 그래 프를 일컫는다. 분석 결과 웹 그래프는 강한 연결 요소 와 마찬가지로 굉장히 큰 하나의 약한 연결요소를 가짐 을 알 수 있었다. 이 가장 큰 하나의 약한 연결요소를 WCC라 부르기로 한다. 본 논문에서는 웹 그래프를 방 향성을 고려하지 않고 메모리에 로드한 후에 너비 우선 탐색 알고리즘을 적용하여 약한 연결요소를 산출하였다. 분석 결과 WCC의 크기는 전체 웹 페이지의 약 88% 를 차지하고 있기 때문에, 대부분의 웹 페이지들이 링크 를 정방향 및 역방향으로 따라갔을 때 서로에게 도달할 수 있다. 즉, 웹은 연결도가 상당히 높은 그래프라 할 수 있다. 약한 연결 요소들 역시 강한 연결 요소들과 마 찬가지로 크기에 의한 분포가 멱법칙을 따르며 지수는 약 2.2이다(그림 4). 국내 웹의 WCC 크기의 비율은 [5] 에서의 해외 웹의 WCC 비율 91%보다 조금 낮으며, 크 기에 대한 멱법칙의 지수는 [5]의 2.54보다 조금 낮은 2.2를 가짐을 알 수 있다. 5. 보우타이 구조 웹 그래프는 웹 페이지들을 임의로 선택하여 링크의 정방향 및 역방향으로 너비 우선 탐색함으로써 그 전반 그림 3 강한 연결 요소들의 크기에 따른 분포 그림 4 약한 연결 요소들의 크기에 따른 분포
국내 웹 그래프의 링크 구조 분석 11 적인 구조를 도식화할 수 있다[5]. 본 연구에서는 추출 한 웹 페이지로부터 구한 WCC를 더 정밀히 분석하고 그 결과로부터 웹 그래프의 전체적인 구조를 보여주는 보우타이 다이어그램을 구한다. 5.1 SCC, IN, OUT 4장에서 분석한 대로 전체의 88% 가량인 약 2.36억 개의 웹 페이지가 방향성을 고려하지 않았을 때 서로 연결되어 있으며, 이를 서로 다른 특성을 지닌 네 가지 그룹으로 더욱 세부적으로 분류할 수 있다. 그 가운데 4.1장에서 얻은 SCC는 웹 그래프의 중심부를 이루고 있다. 그 다음으로 SCC와 연결된 IN, OUT이라 불리는 요소가 있다. IN은 SCC에 포함되지 않은 웹 페이지들 로서 링크의 정방향을 고려했을 때 SCC의 한 웹 페이 지로의 경로가 존재하는 웹 페이지들의 집합이다. 즉, IN에 속한 웹페이지로부터 웹 그래프를 탐색하면 SCC 의 모든 웹 페이지들로 도달할 수 있다. 반면, OUT의 웹페이지들은 SCC의 웹 페이지들로부터 링크의 정방향 으로 도달 가능하지만, 그 역으로 SCC로는 도달할 수 없는 웹 페이지들이다. 즉, OUT의 웹 페이지부터 웹 그래프를 탐색할 경우 짧은 시간 내에 더 이상 탐색할 수 없게 된다. 5.2 TENDRIL 외 네 번째로 TENDRIL이라 불리는 요소의 웹 페이지 들은 하이퍼링크를 통해 SCC로 도달할 수 있는 경로를 가지지 않으며, 반대로 SCC로부터도 도달할 수 없다. 이는 WCC에서 IN, OUT, SCC를 제외한 웹 페이지들 로, SCC의 페이지들은 TENDRIL로의 링크를 가지고 있지 않으며, TENDRIL 또한 SCC로의 링크를 가지고 있지 않다. 마지막으로 DISCONNECTED는 앞선 네 가지 그룹에 속하지도 연결되지도 않는 웹 페이지들의 집합이다. 그림 5 국내 웹 그래프의 보우타이 다이어그램 5.3 보우타이 다이어그램 분석 지금부터는 수집한 웹 페이지들을 5.1에서 언급한 다 섯 가지의 그룹으로 분류하고 웹 그래프의 보우타이 다 이어그램을 도출하도록 한다. 각 세부 그룹에 속하는 웹 페이지들의 수를 구하기 위한 알고리즘은 다음과 같다. 1. WCC를 링크의 정방향으로 메모리에 올린다. 2. SCC에 속하는 임의의 웹 페이지부터 링크의 정방 향으로 너비 우선 탐색을 수행하고 SCC에 포함되 지 않는 웹 페이지들의 수를 누적한다. 3. WCC를 링크의 역방향으로 메모리에 올린다. 4. 2를 수행한다. SCC의 한 웹 페이지에서 너비 우선 탐색을 링크의 정방향으로 수행할 경우 SCC와 OUT의 모든 웹 페이 지들을 탐색할 수 있다. 따라서 위의 알고리즘의 단계 2 로부터 얻은 웹 페이지들의 누적수는 SCC와 OUT을 합한 크기이다. SCC의 크기는 5.1에서 구하여 이미 알 고 있으므로 OUT의 크기를 쉽게 계산할 수 있다. 마찬 가지로 단계 4로부터 SCC와 IN의 크기의 합을 알 수 있고 이로부터 IN의 크기를 알 수 있다. WCC는 SCC, IN, OUT 그리고 TENDRIL로 구성되어 있으며 앞선 세 그룹의 크기와 5.2에서 구한 WCC의 크기를 알고 있으므로 TENDRIL의 크기를 계산할 수 있다. 마지막 으로 DISCONNECTED의 크기는 전체 웹 페이지에서 WCC의 크기를 뺀 값으로 구할 수 있다. 각 그룹의 크 기는 아래의 표 2에 정리되어 있다. 표 2 보우타이 다이어그램의 각 요소의 크기 비율 그 룹 크 기 비 율 IN 36,226,722 13.5 % SCC 125,474,724 46.6 % OUT 55,030,922 20.5 % TENDRILS 22,060,386 8.2 % DISCONN 30,285,182 11.3 % TOTAL 269,077,936 100 % 위의 분석 결과 약 3600만 개(13.5%)의 웹 페이지들 이 하이퍼링크를 따라 웹 그래프의 중심인 SCC로의 경 로를 가지는 IN에 속하였다. 이 IN에 속한 웹 페이지들 은 상대적으로 최근에 생긴 웹의 다른 페이지들로만 관 련 링크를 가진 새로운 웹 페이지들이나 아직 다른 페 이지들에게 알려지지 않은 것으로 추측할 수 있다. 반면 SCC로의 경로를 가지고 있지 않은 그룹인 OUT에 속 한 웹 페이지들은 전체의 약 20.5% 가량을 차지하고 있 으며, 이는 기업의 웹사이트 등 내부로의 하이퍼링크만 가진 것으로 추측할 수 있다[6]. 5.4 웹 페이지 쌍의 연결도 웹 그래프의 보우타이 구조에서 IN, OUT, SCC의 상 호 관계와 그 크기 비율을 통해 웹 페이지 간의 연결도 를 산출할 수 있다. 그래프의 방향성을 고려하였을 때 웹 페이지 쌍(u, v)에 대하여 u가 IN SCC에, v가 OUT
12 정보과학회논문지 : 컴퓨팅의 실제 및 레터 제 19 권 제 1 호(2013.1) SCC에 위치할 경우 두 페이지 사이에 경로가 존재한 다. TENDRIL에 속한 페이지들의 연결비율은 낮으므로 무시한다. u가 IN SCC에 있을 확률은 60.1%이고 v가 OUT SCC에 있을 확률은 67.1%이다. 따라서 두 사건 이 독립적이라는 가정 하에[6] 임의의 웹 페이지 쌍에서 경로가 존재하는 비율은 40.3%이며 59.7%의 페이지 쌍 사이에는 경로가 존재하지 않는다. [6]에서 해외 웹 페 이지 쌍들의 약 25%가 경로를 가진 것에 비해, 국내 웹 페이지들 사이의 경로 사이의 연결도가 매우 높은 것을 알 수 있다. 이는 국내 웹 페이지들이 인터넷 포털을 중 심으로 연결되거나 소수의 대형 웹 사이트에 집중되어 있기 때문이라 추정된다. 다음으로 경로가 존재하는 약 40%의 웹 페이지 쌍들 의 경로들의 평균 거리를 산출한다. 웹 페이지 쌍 거리는 에서 까지의 경로가 존재할 경우 최단 경로 가 가지는 간선(하이퍼링크)의 수로 정의되며, 경로가 존재하지 않는 경우 무한대로 정의된다. 그리고 경로가 존재하는 모든 웹 페이지 쌍들의 평균 거리를 평균 연 결 거리로 정의한다. 본 논문에서는 웹 그래프의 SCC의 하이퍼링크들의 정방향을 기준으로 경로가 존재하는 웹 페이지의 순서 쌍들에 대해 평균 연결 거리를 측정하였다. SCC는 모 든 웹 페이지 쌍에 대해 무한대가 아닌 거리가 정의되 어 있으며, 평균 연결 거리를 측정하는 데에는 기본적으 로 그래프의 너비 우선 탐색 알고리즘을 활용하였다. 실 험 방법으로 SCC에 속한 임의의 웹 페이지를 기점으로 선택한 후 너비 우선 탐색을 수행하여 각 페이지까지의 거리를 측정하였다. 그림 6은 SCC의 평균 연결 거리 측정 실험에 대한 결과를 나타낸 그래프이다. 가로축 step은 너비 우선 탐 색의 수행 회수이며, 세로축은 step이 진행됨에 따라 측 정된 거리를 누적하여 평균 거리를 산출한 것을 세로축 에 나타내었다. 그래프를 살펴보면 step이 증가함에 따 라 평균 거리가 약 11.8로 수렴하는 것을 알 수 있다. 이 평균 거리는 구성하는 웹 페이지들의 수에 비해 매 우 낮은 수치로 웹 그래프가 small-world 네트워크임을 알 수 있다. 즉, 웹은 멱법칙을 따르는 small-world 네 트워크로 임의의 웹 페이지가 제거되어도 평균 연결 거 리는 크게 영향을 받지 않는 견고한 구조를 가지고 있 다. 참고로 WCC에서는 IN에 속한 웹 페이지들에서 출 발하는 모든 페이지 쌍은 무한대가 아닌 거리가 정의되 어 있으며, 이들의 평균거리 역시 약 12정도로 측정되었 다(그림 7). [5]의 평균 연결 거리 약 16은 전체 웹 그 래프에서 임의로 추출한 570개의 웹 페이지로부터 너비 우선 탐색을 수행한 결과이며 본 연구와의 직접적인 비 교는 어려우나 평균 거리를 증가시킬 수 있는 IN과 OUT의 웹 페이지들을 고려하여도 [5]의 웹 그래프보다 짧은 평균거리를 가져 국내 웹의 연결도가 더 높을 것 으로 예상할 수 있다. 6. 결 론 본 논문에서는 3억 개의 국내 웹 페이지들과 이들 간 의 약 137억 개의 하이퍼링크들을 수집하여 웹 그래프 를 생성하고 그 링크 구조에 대해 분석하였다. 국내 웹 그래프에 대한 연구는 [14]에서 진행된 바 있으며, 약 1 억 1천만개의 웹 페이지들을 수집하고 이들 간의 약 27 억 개의 하이퍼링크들을 추출하여 웹 그래프를 생성하 였다. 이 때 웹 그래프의 SCC는 전체의 86%를 차지하 여 본 연구의 SCC의 비율 46.6%보다 월등이 높은데, 이는 수집된 약 1억 페이지의 웹 페이지 대부분이 웹 페이지가 서로 도달할 수 있는 SCC에서 주로 수집되어 충분히 많은 웹 페이지들이 수집되지 않았음을 알 수 있다. 반면 본 연구에서는 3억 개의 대규모 웹 페이지들 을 수집하였으며, 분석하여 얻은 보우타이 구조의 구성 요소의 비율은 SCC 외의 웹 페이지들 역시 충분히 수 집되었음을 말해주고 있다. 또한 [14]의 저자들은 웹 페 그림 6 SCC의 평균 연결 거리 그림 7 WCC의 평균 연결 거리
국내 웹 그래프의 링크 구조 분석 13 이지들의 낮은 진출차수에 대한 분포가 멱법칙과는 차 이가 있어 새로운 분석 모델이 필요함을 언급하고 있다. 본 논문에서는 특정 차수 이상에서 멱법칙을 보이는 모 델을 통해 분석하여 차수 122 이상에서 지수 4.2의 멱 법칙을 이룸을 확인하였다. 국내 웹 그래프는 전체 웹 페이지의 88%가 하나의 큰 약한 연결 요소에 포함되어 전체적으로 높은 연결도 를 가진다. 또한 small-world 네트워크의 특성을 보이 며, 임의의 두 웹 페이지 사이에 경로가 존재하는 약 60%의 웹 페이지 쌍들의 평균 연결 거리가 약 12 정도 로 견고한 구조를 가지고 있다. 국내 웹 그래프는 해외 의 웹 그래프보다 높은 비율의 SCC, 높은 강한 연결 요소들의 크기에 대한 멱법칙 지수를 가지며, 더 짧은 평균 연결거리를 가져 연결도가 더 높음을 확인하였다. 참 고 문 헌 [1] R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, Trawling the Web for Emerging Cyber- Communities, Computer Networks, vol.31, no.11-16, pp.1481-1493, 1999. [2] J. Cho, H. Garcia-Molina, "Synchronizing a Database to Improve Freshness," Proc. of the 2000 ACM SIGMOD, vol.29, Issue 2, pp.117-128, 2000. [3] S. Jeromy Carrière, R. Kazman, WebQuery: Searching and Visualizing the Web Through Connectivity, Computer Networks (CN), vol.29, no.8-13, pp.1257-1267, 1997. [4] J. Han, Y. Yu, G. Liu, G.-R. Xue, An Algorithm for Enumerating SCCs in Web Graph, APWeb 2005 Lecture Notes in Computer Science, pp.655-667, 2005. [5] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener, "Graph structure in the Web," In Computer Networks, vol.33, Issues.1-6, pp.309-320, Jun. 2000. [6] R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tompkins, E. Upfal, "The Web as a graph," Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, May. 15-17, 2000. [7] A. Barabasi, R. Albert, "Emergence of Scaling in Random Networks," Science, vol.286, no.5439, pp.509-512, Oct. 1999. [8] M. Faloutsos, P. Faloutsos, C. Faloutsos, "On Power-law Relationships of the Internet Topology," Proc. of the SIGCOMM '99, pp.251-262, 1999. [9] R. Albert, J. Hawoong, A.-L. Barabasi, "The diameter of the world wide web," Nature, 401, pp.130-131, 1999. [10] G. W. Flake, S. Lawrence, C. Lee Giles, F. Coetzee, "Self-Organization and Identification of Web Communities," IEEE Computer, vol.35, no.3, pp.66-71, 2002 [11] B. Kahng, Y. Park, H. Jeong, "Robustness of the in-degree exponent for the World-Wide Web," Phys. Rev. E 66 046107, vol.66, Issue 4, 2002. [12] G. J. Peterson, S. Pressé, K. A. Dill, "Nonuniversal power law scaling in the probability distribution of scientific citations," Proc. of the National Academy of Science of the United States of America (PNAS), pp.207-237, 2010. [13] E. Nuutila, E. Soisalon-Soininen, "On finding the strongly connected components in a directed graph," Information Processing Letters, vol.49, pp.9-14, 1994. [14] I. K. Han, S. H. Lee, "Graph Structure and Evolution of the Korea web," The KIPS Transactions : Part D, vol.14-d, no.3, 2007. 서 정 주 2009년 성균관대학교 컴퓨터공학과 학사 2009년 현재 서울대학교 전기컴퓨터공 학부 석사박사 통합과정, 관심분야는 알 고리즘, 컴퓨터이론, 암호 및 보안 김 진 일 2005년 서울대학교 전기공학부 학사. 2007 년 서울대학교 전기컴퓨터공학부 석사 2007년 현재 서울대학교 전기컴퓨터공 학부 박사과정. 2010년 11월 현재 SAP Labs Korea, Senior engineer. 관심분야 는 암호학, 웹 검색, 컴퓨터이론 김 은 상 2005년 서울대학교 컴퓨터공학부 학사 2005년 2012년 서울대학교 전기 컴퓨터 공학부 박사과정. 2010년 11월 현재 SAP Labs Korea, Senior engineer. 관심분야 는 컴퓨터이론, 알고리즘, 웹 검색, 암호 및 보안 김 영 호 2008년 KAIST 물리학과 학사. 2008년 현재 KAIST 물리학과 석박사 통합과 정. 관심분야는 복잡계 네트워크, 전산 및 통계물리, 데이터과학
14 정보과학회논문지 : 컴퓨팅의 실제 및 레터 제 19 권 제 1 호(2013.1) 리, 데이터과학 정 하 웅 1991년 서울대학교 물리학과 학사. 1998 년 서울대학교 물리학과 석,박사. 1998년 2001 미국 U. of Notre Dame 포닥/ 연구교수. 2001년 현재 한국과학기술원 물리학과 KAIST-지정 석좌교수. 관심 분야는 복잡계 네트워크, 전산 및 통계물 김 성 렬 1993년 서울대학교 컴퓨터공학과 학사 1995년 서울대학교 컴퓨터공학과 석사 2000년 서울대학교 컴퓨터공학과 박사 2000년 2002년 WiseNut Inc., Engineering Manager. 2002년 현재 건국대 학교 인터넷미디어공학부 교수. 관심분야 는 알고리즘, 컴퓨터이론, 웹 검색, 분산처리 박 근 수 1983년 서울대학교 컴퓨터공학과 학사 1985년 서울대학교 컴퓨터공학과 석사 1992년 미국 Columbia 대학교 전산학 박사. 1991년 11월 1993년 8월 영국 런 던대학교 King's College 조교수. 1993 년 8월 현재 서울대학교 컴퓨터공학부 교수. 관심분야는 컴퓨터이론, 생물정보학, 암호학, 웹 검색