1-1 네트워크와 그래프
1. 네트워크란?
: 링크로 연결된 objects의 집합
2. 네트워크의 요소(3)
- Object (N): nodes, verices
- Interactions (E): links, edges
- System (G(N,E)): network, graph
3. 네트워크와 그래프 비교
| 네트워크 | 그래프 | |
| 의미 | 종종 실제 시스템을 지칭 | 네트워크의 수학적 표현법 |
| 예시 | Web graph, Social network, Metabolic network | Web, Social graph |
| 사용하는 용어 | Network, node, link | Graph, vertex, edge |
(사실상 용어는 모두 혼용해서 사용함.)
(ex. Social network: node: 사람, link: 팔로우, dm 등)
4. 적절한 표현법의 선택(3)
- professional networks: 개개인 간의 연결
- sexual networks: 성적 관계가 있는 것들 간의 연결
- citation network: 서로 인용하는 과학 논문 간의 연결
-> 적절한 네트워크 표현법을 선택하는 것이 성공적으로 네트워크사용 능력을 결정.
5. 방향에 따른 네트워크 분류(2)
- Undirected Network: (ex) Collaborations, Friendship on Facebook
(1) Connected graph: 임의의 두 정점은 경로로 연결되어 있다.
(2) Disconnected graph: 두 개 이상의 connected components로 이루어져있다.
+ bridge edge: 지워지면 disconnected 그래프가 되는 edge.
+ articulation point: 지워지면 disconnected 그래프가 되는 vertex.
+ giant component: 가장 큰 component(: 연결된 덩어리).
+ Isolated node: 어떤 노드와도 연결되어 있지 않은 노드.
- Directed Network: (ex)Phone calls, Following on Twitter
(1) Strongly connected directed graph: 임의의 두 노드가 양 방향으로 오갈 수 있는 그래프
: In(A) = Out(A)
(2) Weakly connected directed graph: strongly가 아닌 그래프
(3) DAG - Directed Acyclic Graph: cycle이 존재하지 않는! 그래프
6. 어떤 directed graph도 다 만들 수 있다!(2)
: Strongly connected graph와 DAG를 조합하면!
7. SCC(Strongly Connected Componet)조건(2)
- SCC 내부의 임의의 한 쌍은 모두 서로 도달할 수 있다.
- SCC보다 더 큰 SCC는 존재하지 않는다.
8. SCC에 대한 사실과 증명(2)
- 각각의 노드는 하나의 SCC에만 포함된다.
(proof) 두 개의 SCC에 동시에 포함되는 노드가 있다고 가정하자.
S∪S'은 하나의 더 큰 SCC가 되어버린다.
따라서 SCC보다 더 큰 SCC가 존재하게 되므로 이는 SCC 조건을 만족하지 못한다.
- 각각의 SCC를 하나의 노드로 보는 그래프(G)를 그리면 그 그래프는 DAG이다.
(proof) G'이 DAG가 아니라고 가정하자. 그러면 G'에는 cycle이 존재한다.
그러나 G'은 SCC간의 연결 그래프가 아니게 된다. (SCC는 maximal 집합으로 정의되어야 하기 떄문)
1-2 웹
1. 웹과 그래프
- Nodes = web pages
- Edges = hyperlinks
(+ dark matter: 데이터베이스가 만들었지만 노드로는 만들 수 없는 페이지)
2. 웹 링크의 과거와 현재
: 과거에는 navigational했지만, 오늘날에는 transactional(여러 과정을 하나로 보는 것)하다.
(과거에는 주로 정보 탐색을 위한 "navigational(탐색적)" 목적으로 사용되었지만, 현재는 웹 링크를 통해 온라인 쇼핑, 예약, 결제 등 다양한 트랜잭션(transactional) 활동을 수행하는데 사용된다)
3. 웹은 어떻게 생겼냐?
: Web as a directed graph - Broder et al. 2000-
: There is a giant SCC(There won't be 2 giant SCCs)
(proof) 엄청나게 방대한 페이지가 있는데 두 개의 giant SCC를 연결하는 한 쌍이 하나도 없을까..?
-> 존재할 확률이 높다!
4. v를 포함하는 SCC를 찾는 방법
: Out(v) ∩ In(v)
( 더 쉬운 방법: Out(v, G) ∩ Out(v,~G) ) -> ~G는 모든 링크들의 방향을 뒤집어 놓은
5. Web의 구조
(1) Undirected version of the Web graph: 가장 큰 WCC에서 91%의 노드가 존재.
Q. hubs는 웹 그래프를 연결되도록 했는가?
A. No! 들어오는 link의 개수가 10 이상인 페이지들의 link를 삭제해도 WCC에는 그래프의 50% 노드가 남아 있었다.
(2) Directed version of the Web graph: 가장 큰 SCC에서 28%의 노드가 존재.(56million)
-> 랜덤으로 v를 가져오면 Out(v) ~ 50% (100 million), In(v) ~ 50% (100 million) 이 되게 한다.
'Computer Science > Software Application' 카테고리의 다른 글
| [소응] 15장 Sponsored Search Markets (0) | 2023.12.15 |
|---|---|
| [소응] 10장 Matching Markets (0) | 2023.12.15 |
| [소응] 9장 Auctions(경매) (0) | 2023.12.15 |
| [소응] 3장 부호있는 네트워크 (0) | 2023.10.11 |
| [소응] 2장 네트워크의 커뮤니티 구조 (0) | 2023.09.23 |
