Web & Directed graphs
Web을 그래프로 봐보자
실세계의 여러 네트워크 데이터 중, 웹도 그 중 하나다! 심지어 엄청 큰
→ 짚고 넘어갈만 하다.
웹의 구성 - Graph
- Node ← 웹 페이지
- Edge ← 하이퍼링크 (페이지 간의 연결)
웹의 변화 - Process
- 이전에는 사람들이 웹에서 목적을 가지고 무언가는 탐색했던 반면, 요즘에는 수 많은 연결이 하이퍼링크보단 트랜잭션이다. 트랜잭션이란 여러 스탭이지만 한 과정으로 봐야하는 것
웹의 구조 - Structure - Directed Graph
- 웹은 방향 그래프이다.
- 하나의 페이지로부터 나가는 링크도 있고, 들어오는 링크도 있다.
→ 어느정도의 비율일까 → In, Out 집합
방향 그래프의 연결성은 → Strongly, Weakly
In(v) : v에 도달할 수 있는 노드 w들의 집합
Out(v) : v에서 나가서 도달할 수 있는 노드 w들의 집합
노드 v는 In, Out 모두에 들어간다
모든 방향 그래프는 이 두가지로 나타낼 수 있다.
→ 강한 연결 그래프거나, 사이클이 없거나
- Strongly connected
- 각 노드는 모든 노드에 도달 가능 하다.
- 모든 노드에 대해
In(A) = Out(A)
- DAG - Directed Acyclic Graph
- 사이클이 없는 방향 그래프 !
- 사이클이 있으면: (u→v) 길이 있으면 (v→u) 가는 길도 있다
- 모든 노드로 갈 수 있다.
- 강한 연결 그래프면 - 사이클이 반드시 존재한다.
Strongly connected component (SCC)
: node S들의 집합이다
- S의 모든 노드들은 모두 강하게 연결되어 있다.
- S를 포함하는 더 큰 컴포넌트는 없다.
- 노드 하나짜리도 SCC이다.
모든 방향 그래프는 SCC들로 이루어진 DAG이다
증명) proof by contradiction
만약 DAG가 아니면 → 사이클이 존재 한다. 그럼 연결된 상태 → 더 큰 SCC가 가능
- 큰 강한 연결 컴포넌트들이 사이클 없이 연결된 상태 !
- 만약 SCC들 간의 사이클이 있다? → 그럼 더 큰 SCC를 만들 수 있었음. — 위반
- 방향 그래프 G는 SCC들로 나누어질 수 있다. (partioning된다)
- 모든 노드는 오직 하나의 SCC의 요소이다!
노드 v를 포함하는 SCC 찾기
scc의 노드들 : strongly connected
→ v로 올 수 있고, v가 갈 수 있는 애들
→ In(v) 교 Out(v)
근데 In(v)는 구하기 어렵다 → 그래프 방향을 다 뒤집어서 G’ 여기서 In(v)를 찾자
→ Out(v, G) 교 Out(v, G') = SCC !!
web의 SCC
→ 웹은 하나의 Giant SCC로 이루어지지 않을까!?
웹은 엄청 많은 노드들과 링크들 → 엄청 큰 SCC → Giant SCC!
경험적으로, 웹의 SCC는 엄청 큼 100만개 정도의 페이지
만약에 이렇게 큰 Giant SCC 2개가 있다고 해보자.
→ 그럼 이 많은 페이지들간의 연결이 하나만 있어도 하나의 SCC로 합쳐지는데, 이거 하나가 없을까?
→ 링크가 없을 확률은 매우 작다.
→ 고로 웹은 하나의 큰 Giant SCC일 확률이 크다
Web 네트워크의 구조
WEB
- 203백만 개 노드
- 15억 개 링크
WEB - 무방향 그래프
- 91% 노드들은 weakly connected component (WCC)
- 무방향 그래프로 보자면, 91%는 연결되어 있음.
- 연결을 엄청 많이 가지고 있는 허브 역할을 하는 노드들이 얘네들을 다 연결시키는 게 아닌가?
- 이 허브 노드들을 지워도 50% 노드들은 여전히 WCC임
WEB - 방향 그래프
- 가장 큰 SCC: 전체 노드의 28%(56백만)를 포함하고 있음
- 대략적으로 어떤 노드 v에 대해
- Out(v) ~ 50%
- In(v) ~ 50% (100백만)