[Structure of the Web Graph] 1주차

Object(정점) : nodes, vertices

Interaactions(선) : links, edges

System : network, graph

-> 네트워크는 현실 시스템을 반영. 그래프는 네트워크의 수학적 표현.

 

- 적절한 네트워크 표현의 선택은 네트워크를 성공적으로 사용할 수 있는 능력을 결정한다.

 

- Undirected : 방향이 없는 것. 연결되지 않은게 아니다!

- Directed : 방향이 있는 연결. 두 노드 사이의 관계가 일방향(정보의 흐름이 한 방향).

 

- Connected graph : 어떤 두 정점을 선택하든 두 정점을 잇는 path가 있음.

- Bridge edge : 지워지면 그래프가 disconnected 되는 엣지 = A-F

- Articulation point : 지워지면 그래프가 disconnected 되는 정점 - A, F

 

- Strongly connected direct : 모든 노드 상에 양방향의 경로가 존재

ex) A->B가 있다면 B->A도 존재해야함.

- Weakly connected direct : Undirect로 가정했을 때 그래프 내의 모든 노드들이 연결되어 있음

 

초기엔 웹 링크가 navigational 했으나,

→ 특정 사이트의 홈페이지나 카테고리 섹션으로 이동하는데 사용되었음

요즈음엔 많은 링크들이 transactional하다

→ 구매, 다운로드, 구독과 같은 행동을 유도하는 링크가 트랜잭션 링크인데, 많은 링크들이 이런 목적을 가지고 있음

 

In(v) → v에 닿을 수 있는 모든 노드, 자기 자신 포함

Out(v) → v가 닿을 수 있는 모든 노드, 자기 자신 포함

 

Strongly connected direct : 이미 알고있지? 모든 노드가 서로 양방향으로 도달할 수 있음

DAG(directed Acyclic Graph) : 순환 경로가 없는 그래프(자기 자신에게 돌아올 수 없는 그래프)

-> 모든 Direct 그래프는 이 둘 중 하나!

 

SCC : 이 컴포넌트 내부에서는 서로 이동할 수 있는 경로가 존재한다.

-> 다른 SCC의 노드와는 양방향 도달이 불가

 

각각의 SCC를 독립적인 단위로 취급하면, 순환 경로가 없는 그래프가 됨.

(1) : SCC들이 그래프의 노드들을 분할 -> 각 노드들은 최대 1개 SCC의 구성원이다

-> 만약 노드 v가 두 개 SCC의 구성원이라면 2개의 노드는 합쳐서 하나의 큰 SCC다.(모순증명)

(2) : G' 그래프의 각 노드가 SCC, 그 사이에 엣지가 존재한다면 G'은 DAG이다 -> 사이클이 없음. 돌아올 수 없음.

-> DAG가 아니라면 G'은 사이클이 존재. 그럼 모든 노드는 같은 SCC의 구성원이 됨
BUT G'은 하나의 SCC로 연결된 그래프가 아니다!(모순증명)

 

 

DAG가 어떻게 서로 맞물려 있는지 확인해보자

SCC : 내부에서는 서로 어디든 도달할 수 있지? Out(v) ∩ In(v)

= Out(v,G) ∩ Out(v,G\var) : 여기서 G\var 은 방향이 반전된 것.

이미지 참고. SCC(A)의 정의 = Out(A) ∩ In(A).

 

 

- Giant SCC 에서의 추론

1. 한 SCC에서 다른 SCC로 연결하려면 한 페이지만 있으면 된다

2. 2개의 SCC에 수백만 페이지가 있는 경우 이런 일이 발생하지 않을 가능성은 매우 적다

-> 결과 : degree가 10을 초과하는 녀석들을 삭제해도 WCC는 그래프의 50%이상 을 차지 = 50% 이상 연결되어있다.

 

SCC가 처리하는게 56 밀리언 노드로 크긴 큰데, 그렇다고 전부는 아니기에 다른 것도 고려해야 한다.