웹 그래프 (Web Graph)

 

네트워크의 구조

- 네트워크란 링크에 의해 연결된 개체 쌍들이 있는 객체들의 집합

- 네트워크 구조

• Objects: nodes, vertices → N
• Interactions: links, edges → E
• System: network, graph → G(N, E)

- 네트워크는 종종 실제 시스템을 표현한다. 예를 들어, 웹(Web), 소셜 네트워크(Social network), Metabolic network 가 있다.

• Network, node, link

- 그래프는 네트워크의 수학적인 표기법이다. 예를 들어, 웹 그래프(Web graph), 소셜 그래프(Social graph in facebook)이 있다.

• Graph, vertex, edge

 

적절한 표현의 선택

- 적절한 네트워크 표현법을 선택하는 것이 성공적으로 네트워크를 사용하는 능력을 결정한다.

• 몇몇 경우에 유일하고 모호하지 않은 표현법이 있다.
• 다른 경우에 그 표현법이 결코 유일하지 않다.
• 링크를 할당하는 방식이 공부할 질문의 본질을 결정할 것이다.

- 서로서로 동작하는 개체를 연결하면, 전문적인 네트워크(professional network)를 탐구할 것이다.

- 성적 관계를 가지는 사람들을 연결해보면, 성적인 네트워크(sexual networks)를 탐구하고 있을 것이다.

• 예를 들어, 사람들의 관계를 표현했을 때 중간 노드는 성병에 걸리면 안쪽으로 퍼져나갈 수 있어서 실제 성병에 걸리면 안되는 경우 등을 판단할 수 있다.

- 서로서로 인용하는 논문들을 연결해보면, 인용 네트워크(citation network)를 공부할 것이다.

 

Undirected vs Directed Networks

- Undirected Example: Collaborations, Friendship on Facebook, 상호간의 동일한 관계

- Directed Example: Phone calls, Following on Twitter, 비대칭적인 관계

 

그래프의 연결성(Connectivity of Graphs)

- Connected Component: 연결된 노드의 집합

- Connected (undirected) graph: 방향성 없이, 모든 노드가 연결되어 있는 그래프 (Connected Components가 존재하지 않음)

- Disconnected (undirected) graph: 방향성 없이, 둘 이상의 connected components가 존재

여기서 H 노드 하나만 보면 connected components로 볼 수 있다.

- Bridge Edge: 제거되면, connected component 개수가 늘어나는 edge

- Articulation point: 제거되면, disconnected graph가 되버리는 node(point)

- Connected (directed) graph: 두 노드간 이동이 가능한 방향이 존재하며, 각 노드로부터 모든 노드로 이동할 수 있는 경로가 존재하는 그래프

- Weakly connected directed graph: 그래프 중 모든 노드가 연결된 그래프 (양방향으로 도달되지 않는 노드들이 존재)

 

그래프로서의 웹

- Nodes = web pages

- Edges = hyperlinks

- 초기 웹 링크는 방향을 알려주는 역할(navigational)이었다.

- 오늘날 많은 링크는 교류하는 역할(transactional)이다.

- Web as a directed graph: 노드 v가 주어졌을 때 들어오는 링크는 incoming link, 나가는 링크는 outcoming link로 정의된다.

- Directed Graph

• Strongly connected: 어떤 노드도 다른 노드에 도달할 수 있는 path가 존재
  • In Set = Out Set (동일)

• Directed Acyclic Graph(DAG): 사이클이 없는 그래프, 노드 u는 v에 도달해도 노드 v는 u에 도달하지 않음

 

Strongly Connected Component (SCC)

- 집합 S에서 노드들의 모든 쌍이 서로 도달할 수 있다.

- SCC이면서 집합 S를 포함하는 더 큰 집합은 존재하지 않는다.

- 예제: {A, B, C}는 첫번째 조건을 만족하나, {A, B, C, G}가 존재하므로 두번째 조건은 만족하지 못한다. (not SCC)

- 모든 directed graph 는 SCC들의 DAG이다. 즉, 모든 쌍들이 서로 도달할 수 있는 작은 그래프들이 모인 것이라고 볼 수 있다.

• SCC는 그래프 G의 노드들을 분할한다.(partition) → 각 SCC를 노드로 본다.
• SCC를 노드로 보는 그래프 G`이 있을 때, G`은 DAG 이다.

- 증명1: SCC는 그래프 G의 노드들을 분할한다. 각 노드는 정확히 1개의 SCC의 멤버이다.

• 대우명제(Proof by contradiction): 2개의 SCC를 가지는 그래프 S와 S`이 있을 때, 두 그래프에 동시에 멤버가 되는 노드 v가 존재한다. 그러나, S와 S`의 합집합은 하나의 큰 SCC가 된다. 이것은 모순이다.

- 증명2: SCC들의 그래프 G`은 DAG 이다. G`에는 사이클(cycle)이 없다.

• 대우명제(Proof by contradiction): 그래프 G`이 DAG가 아니라고 가정했을 때, G`은 directed cycle을 가진다. cycle 에 있는 모든 노드들은 서로 도달가능하며 같은 SCC의 일부이다. 그러나 G`은 SCC 사이에 순환가능한 그래프가 아니다. SCC는 최대 순환가능한 노드의 집합으로 정의되므로 이는 모순이다.

 

웹에서의 그래프 구조

- 웹의 큰 스냅샷을 살펴보면, 어떻게 SCC들이 DAG로 서로 맞춰있는지 이해할 수 있다.

- Computational Issues: SCC가 노드 v를 포함하는 것을 어떻게 발견?

• In(v): 노드 v로 들어오는 노드들의 집합
• Out(v): 노드 v로부터 도달가능한 노드들의 집합
• SCC 에 노드 v가 포함되면, Out(v)와 In(v)의 교집합에 노드 v가 있다.
• 단, 위의 방법은 연산이 많이 걸리므로 Out(v,G)와 Out(v, 방향을 뒤집은 G)의 교집합으로 노드 v를 찾는다.

전체 SCC의 개수는 {A, B, D, E, F, G} 와 {C}로 2개이다.

- 웹은 매우 큰 SCC 이다. 2개의 매우 큰 SCC는 존재하지 않을 것이다.

- 귀납적 논쟁

1. 하나의 SCC에서 다른 SCC로 가는 link는 1 페이지만 소요된다.
2. 만약 2개의 SCC가 몇 백만 페이지를 가진다면, 이 일이 일어나지 않을 가능성은 매우 적다.

 

웹의 구조

- 초기 웹은 데이터베이스에 링크나 url을 저장해둔 형태로 서버는 12GB의 메모리를 가졌었다.

- Undirected version of the Web graph

• 가장 큰 weakly connected component 에서 91% 노드가 존재
• hubs는 웹 그래프를 연결되도록 했는가?
  • 들어오는 link의 개수(in-degree) > 10 인 페이지들에 대한 link를 삭제한다면 WCC는 여전히 그래프의 50%가 남아있다.

- Directed version of the Web graph

• 가장 큰 SCC: 노드들 중 28%가 해당된다. (56 million)
• 랜덤으로 노드 v를 가져오는 것은 Out(v) ~ 50% (100 million), In(v) ~ 50% (100 million) 이 되게 한다.
  • 즉 성능이 랜덤으로 가져오는게 더 좋다.

Conceptual Organization (ex: bowtie)