웹 그래프
웹 그래프(web graph)는 웹의 페이지나 사이트를 정점으로, 그 사이의 하이퍼링크를 방향 간선으로 표현하는 그래프 모델이다. 여러 페이지가 서로 연결되는 구조를 정량적으로 분석할 수 있으며 검색 엔진의 문서 발견과 링크 분석, 커뮤니티 검출 등에 활용된다. 실제 인터넷의 라우터와...
| 분류 | 방향 그래프 모델 |
|---|---|
| 정식 명칭 및 정의 | 웹 문서와 링크의 연결 분석 |
| 관련 기술 | World Wide Web, HTTP, 웹 브라우저, 웹 서버 |
| 기술 참고 | Broder et al.: Graph Structure in the Web |
웹 그래프(web graph)는 웹의 페이지나 사이트를 정점으로, 그 사이의 하이퍼링크를 방향 간선으로 표현하는 그래프 모델이다. 여러 페이지가 서로 연결되는 구조를 정량적으로 분석할 수 있으며 검색 엔진의 문서 발견과 링크 분석, 커뮤니티 검출 등에 활용된다. 실제 인터넷의 라우터와 케이블을 나타내는 네트워크 토폴로지와는 다른 대상을 표현한다.
웹 그래프에서는 한 문서가 다른 문서를 링크하면 출발 문서에서 대상 문서로 향하는 간선을 만든다. 하나의 문서가 여러 문서를 참조할 수 있고 많은 문서가 같은 문서를 참조할 수도 있다. 진입 차수와 진출 차수는 각각 들어오는 링크와 나가는 링크의 수를 나타내며, 실제 웹 데이터에서는 링크 분포가 균일하지 않다.
웹 문서는 사이트 내부의 밀접한 연결과 외부 사이트로의 연결을 동시에 가진다. 강하게 연결된 요소는 서로 링크를 따라 도달할 수 있는 문서 집합을 나타내며, 거대한 웹 그래프에서 발견되는 일부 구조는 나비넥타이 모형으로 설명되어 왔다. 그러나 수집 시점과 크롤링 범위가 다르면 관찰되는 그래프의 크기와 연결 구조도 변한다.
검색 기술은 링크 구조를 이용해 특정 문서의 중요도나 관련성을 추정할 수 있다. PageRank와 같은 알고리즘은 연결이 전달하는 가중치를 반복 계산하는 대표적인 예다. 링크만으로 실제 정보의 품질을 보장할 수는 없으므로 문서 내용, 신뢰도와 사용자 질의 등의 여러 신호를 함께 고려한다.
웹 그래프의 수집은 웹 크롤러가 발견한 페이지와 링크를 기반으로 하므로 접근할 수 없는 문서와 생성이 제한된 페이지는 모델에서 누락될 수 있다. 리디렉션과 정규 URL, 링크 부패 및 같은 문서의 여러 주소는 그래프 분석에 영향을 준다. 웹 그래프는 정보가 연결되어 분포하는 방식을 연구하는 모델이며 개별 사이트의 메뉴와 링크 구조를 개선하는 데도 활용할 수 있다.[1]